Das Kalenderblatt 111026

25/10/2011 - 07:39 von WM | Report spam
The set of all possible computer programs is countable {{wenn wir
schon so konkret von Computern reden, dann können wir sogar noch
weiter einschrànkend sagen: Die Anzahl aller möglichen
Computerprogramme ist endlich und ganz sicher kleiner als 2^10^100.
Aber Turing meinte selbstverstàndlich keine richtigen Computer, und
von der Speicherkapazitàt einer ausnutzbaren Umgebung wusste er auch
noch nichts. Deswegen wollen wir hier seinen Ansatz analysieren.}},
therefore the set of all computable reals is countable, and
diagonalizing over the computable reals immediately yields an
uncomputable real. Q.E.D. {{Nun, so einfach kann man nicht über
endliche Folgen diagonalisieren. Die folgende Liste besitzt keine
Diagonale:

0
1

Deswegen muss man etwas sorgfàltiger vorgehen, was nun auch
geschieht:}}
Let's do it again more carefully.
Make a list of all possible computer programs. Order the programs
by their size, and within those of the same size, order them
alphabetically. The easiest thing to do is to include all the possible
character strings that can be formed from the finite alphabet of the
programming language, even though most of these will be syntactically
invalid programs.
Here's how we define the uncomputable diagonal number 0 < r < 1.
Consider the kth program in our list. If it is syntactically invalid,
or if the kth program never outputs a kth digit, or if the kth digit
output by the kth program isn't a 3, pick 3 as the kth digit of r.
Otherwise, if the kth digit output by the kth program is a 3, pick 4
as the kth digit of r.
This r cannot be computable, because its kth digit is different
from the kth digit of the real number that is computed by the kth
program, if there is one. Therefore there are uncomputable reals, real
numbers that cannot be calculated digit by digit by any computer
program. [...]
In other words, the probability of a real's being computable is
zero, and the probability that it's uncomputable is one. [Who should
be credited for this measure-theoretic proof that there are
uncomputable reals? I have no idea. It seems to have always been part
of my mental baggage.]

[Gregory Chaitin: "How real are real numbers?" (2004)]
http://arxiv.org/abs/math.HO/0411418

Wie in allen anderen Überabzàhlbarkeitsbeweisen auch, findet sich der
Fehler immer an derselben Stelle: Es wird die vollendet unendliche
Anzahl aller endlichen Programme vorausgesetzt. Anderenfalls würde die
gerade definierte Zahl einem endlichen Prozess samt endlichem Programm
entspringen. Die Menge aller endlichen Dinge ist aber nicht vollendet
unendlich, sondern nur potentiell unendlich. Zuletzt wurde das wieder
in KB 111017 bewiesen.

Gruß, WM
 

Lesen sie die antworten

#1 Carsten Schultz
25/10/2011 - 10:29 | Warnen spam
Am 25.10.11 07:39, schrieb WM:
[mehr vom üblichen]

Eine Menge heißt abzàhlbar (genauer abzàhlbar unendlich), wenn es eine
Bijektion zwischen ihr und der Menge der natürlichen gibt. Da Du die
Menge der natürlichen Zahlen, wie sie in der Mathematik üblicherweise
verstanden wird, ablehnst, ist es sinnlos, wenn Du über Abzàhlbarkeit
diskutierst. Also: Einfach mal still sein.




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

Ähnliche fragen