Nerd lost in Cantor-Diagonale

11/04/2010 - 01:42 von Sebastian L. Baltes | Report spam
Hallo zusammen,

ich habe mal wieder eine Verstàndnisfrage und entschuldige mich
vorweg, weil es wieder einmal inhaltlich grauenhaft sein dürfte oder
wenigstens kopiert sein mag, aber mir kam gerade dieser Gedanke, und
ich würde gerne Wissen, warum es falsch ist, oder warum es trivial ist
und nichts zeigt.

Sei Rd die Menge der definierbaren reelen Zahlen. Sei x die
Antidiagonale einer definierbaren Aufzàhlung von Rd. Somit ist x e Rd.
Da x Antidiagonale ist, ist Rd überabzàhlbar. Aber zugleich ist Rd
abzàhlbar, denn N~Rd.

Ich bin mir nicht sicher, ob "definierbar" nicht zu esotherisch wird,
aber "berechenbar" sollte es auch tun, oder?

Danke für Eure Antwort
Sebastian
 

Lesen sie die antworten

#1 Carsten Schultz
11/04/2010 - 07:37 | Warnen spam
Am 11.04.10 01:42, schrieb Sebastian L. Baltes:
Hallo zusammen,

ich habe mal wieder eine Verstàndnisfrage und entschuldige mich
vorweg, weil es wieder einmal inhaltlich grauenhaft sein dürfte oder
wenigstens kopiert sein mag, aber mir kam gerade dieser Gedanke, und
ich würde gerne Wissen, warum es falsch ist, oder warum es trivial ist
und nichts zeigt.

Sei Rd die Menge der definierbaren reelen Zahlen. Sei x die
Antidiagonale einer definierbaren Aufzàhlung von Rd. Somit ist x e Rd.
Da x Antidiagonale ist, ist Rd überabzàhlbar. Aber zugleich ist Rd
abzàhlbar, denn N~Rd.

Ich bin mir nicht sicher, ob "definierbar" nicht zu esotherisch wird,
aber "berechenbar" sollte es auch tun, oder?



Du siehst genau das Problem: Der Begriff muss zunàchst exakt definiert
werden. Einen Widerspruch erhàltst Du nur, wenn zwei Dinge beweisbar
sind, die Du oben anscheinend als klar vorausgesetzt hast:

1) Es gibt eine berechenbare Aufzàhlung aller berechenbaren Zahlen.
2) Für jede gegebene berechenbare Aufzàhlung von Zahlen ist die
Antidiagonale berechenbar.

Wenn der Begriff der Berechenbarkeit konkretisiert ist, wird (2)
wahrscheinlich richtig sein, das Argument zeigt dann, dass (1) falsch
ist. Das ist dicht am Halteproblem: Wenn Berechenbarkeit irgendwie via
Programmen definiert ist, so wird es nicht schwer sein, ein Programm
anzugeben, das alle syntaktisch korrekten Programme auflistet, die eine
reelle Zahl (wahrscheinlich würden wir einfacher 0-1-Folgen betrachten)
berechnen könnten, aber wir können aus diesen nicht die terminierenden
aussieben.

Vielleicht findest Du auch
http://terrytao.wordpress.com/2009/...-argument/
interessant, dort Abschnitt 3.

Gruß

Carsten
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