Lexicon of Arguments

Philosophical and Scientific Issues in Dispute
 
[german]


Complaints - Corrections

Table
Concepts
Versus
Sc. Camps
Theses I
Theses II

Concept/Author*  

What is wrong?
Page
Other metadata
Translation
Excerpt or content
Other

Correction: Year / Place / Page
/ /

Correction:
(max 500 charact.)

Your username*
or User-ID

Email address*

The complaint
will not be published.

 
Barrow I 78
Complexity/Decidability/Paradox/Chaitin/Barrow: Order: "Print a sequence whose complexity can be proved to be greater than the length of this program!".
The computer cannot respond to this. Each sequence that it generates must be of lesser complexity than the length of the sequence itself (and also of its program).
(Neumann: a machine can only build another machine if it is one degree less complex than this one itself. (Kursbuch 8, 139 ff)(1).
>J.v. Neumann.
In the above case, the computer cannot decide whether the number R is random or not. Thus the Goedel theorem is proved.
>Decisions, >Decidability, >Decision theory, >Decision-making process, >K. Gödel.
In the late 1980s, even simpler evidence was found for the Goedel theorem, with which it was transformed into statements about information and randomness.
Information content/Barrow: You can assign a certain amount of information to a system of axioms and rules by defining their information content as the size of the computer program that checks all the possible concluding chains.
I 78/79
If one attempts to extend the bounds of provability by new axioms, there are still larger numbers, or sequences of numbers, whose randomness remains unprovable.
Chaitin: he has proved with the Diophantic equation:

X + y² = q

If we look for solutions with positive integers for x and y, Chaitin asked,...
I 80
...whether such an equation is typically finite or has infinitely many integral solutions if we let q pass through all possible values q = 1,2,3,4 ....
At first sight it hardly deviates from the original question, whether the equation for
Q = 1,2,3 .. has an integer solution.
However, Chaitin's question is infinitely more difficult to answer. The answer is random in the sense that it requires more information than is given in the problem.
There is no way to a solution. Write for q 0 if the equation has only finitely many solutions, and 1, if there are infinitely many. The result is a series of ones and zeros representing a real number.
Their value cannot be calculated by any computer.
The individual spots are logically completely independent of each other.
omega = 0010010101001011010 ...
Then Chaitin transformed this number into a decimal number...
I 81
...omega = 0.0010010101001011010 ...
and thus had the degree of probability that a randomly chosen computer program would eventually stop after a finite number of steps. It is always not equal to 0 and 1.
Still another important consequence: if we choose any very large number for q, there is no way to decide whether the qth binary digit of the number omega is a zero or a one. Human thinking has no access to an answer to this question.
The inevitable undecidability of some statements follows from the low complexity of the computer program, which is based on arithmetic, however.
>Decision problem, >Software, >Computer programming.

1. Kursbuch 8: Mathematik. H. M. Enzensberger (Hg.), Frankfurt/M. 1967.

Found an error? Use our Complaint Form. Perhaps someone forgot to close a bracket? A page number is wrong?
Help us to improve our lexicon.
However, if you are of a different opinion, as regards the validity of the argument, post your own argument beside the contested one.
The correction will be sent to the contributor of the original entry to get his opinion about.