Das Kalenderblatt 110712

11/07/2011 - 08:23 von WM | Report spam
In 1936 Turing published a paper called "On computable numbers".
Rather than look at the real numbers which can be described in
English, Turing looked at a very precise description of a number,
namely one which can be output digit by digit by a computer. He then
took Richard's paradox and ran through it again, this time with
computable numbers. Clearly computer programs, being composed from a
finite number of symbols, are countable. Hence computable numbers are
countable. List all computer programs -- in fact {{sollte das Wort mit
Fakt zu übersetzen sein?}} they will all occur in the number c above.
Create a new real number t by Cantor's diagonal argument whose n-th
digit is defined as follows. If the n-th block is a program which
outputs a real number, make the n-th digit of t different from the n-
th digit of the computable number which is output. If the n-th block
is not a valid programme to output a real number, then make the n-th
digit of t equal to 1. Now t cannot be computable since, by
construction, it differs from each computable number in at least one
digit. However, we have just given a recipe to produce the number
which could easily be programmed to output t, so t is computable. {{Wo
liegt der Fehler? Er ist leicht erkennbar: "List all computer
programs". Offenbar ist dies unmöglich, obwohl alle Computerprogramme
abzàhlbar, also aufllistbar sein sollten, wenn "abzàhlbar" eine
sinnvolle, zumindest mögliche, Eigenschaft wàre. Also ist dies nicht
der Fall.}} Although the "English descriptions" of Richard's paradox
must hold the key to the paradox, in this case our "computable
numbers" are very precise and not subject to the same difficulties. Do
we really have the ultimate paradox which shows that the real numbers
are inconsistent? No! {{Dies Antwort ist dogmatisch vorgegeben.}} So
where is the error in our paradox? The error lies in the fact that
when we run the computer programmes we do not know whether they will
ever output an n-th digit. We can deduce from this argument that it is
impossible to tell whether a computer programme which has output k
digits will ever output a k+1-st digit. {{Dann sollten wir nur solche
Computer-Programme in die engere Auswahl nehmen, die per Definition
nach jeder Ziffer eine weitere erzeugen.}}
[J.J. O'Connor and E.F. Robertson: "The real numbers: Attempts to

Gruß, WM

Lesen sie die antworten

#1 Carsten Schultz
11/07/2011 - 10:47 | Warnen spam
Am 11.07.11 08:23, schrieb WM:
[J.J. O'Connor and E.F. Robertson: "The real numbers: Attempts to

Es ist immer wieder interessant, zu sehen, wie Du Texte ohne jeden
Erkenntnisgewinn lesen kannst.

Carsten Schultz (2:38, 33:47)
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.

Ähnliche fragen