Diskussion:Berechenbare Zahl

Der folgende Textteil ist unpräzise:

"Da es nur abzählbar viele Turing-Maschinen, aber überabzählbar viele reelle Zahlen gibt, sind die berechenbaren Zahlen eine echte Teilmenge von $\mathbb {R}$."

Es suggerriert, als gäbe es eine Menge der berechenbaren Zahlen. Sonst kann man ja nicht von Teilmenge sprechen. - Das ist aber nicht der Fall. Jede Zahl, von der nachgewiesen werden kann, dass sie reell aber nicht berechenbar sei, ist berechenbar. Aus dem Nachweis kann man nämlich eine Turing-Maschine machen. PaCo 15:31, 9. Aug 2005 (CEST)

Die von Dir zitierte Aussage ist korrekt und der Beweis steht gleich dabei. --Rtc 22:01, 9. Aug 2005 (CEST)

Nein. Man kann keine einzige reelle Zahl angeben, die keine berechenbare Zahl ist. Gerade das Cantorverfahren liefert die Bauanweisung für die gesuchte Turing-Maschine. Es gibt sie nicht, die Menge der berechenbaren Zahlen als echte Teilmenge von $\mathbb {R}$. Schwer für Dich zu akzeptieren, aber es stimmt.

Nochmal: Nenne mir eine einzige unberechenbare reelle Zahl. Du schaffst es nicht, es sei denn, Du versuchst es mit der mit Gunther besprochenen Donnerstag-Zahl, dass man sich auf Dinge in der Zukunft bezieht oder auf die Lösung bisher noch nicht bewiesener Sätze oder so was.PaCo 01:50, 10. Aug 2005 (CEST)

Die diagonalisierte Zahl bei Cantor ist z.B. eine nicht berechenbare Zahl. Anderes Beispiel: Die Turingmaschinen sind abzählbar. Also gibt es eine Bijektion f, die natürliche Zahlen auf Turingmaschinen abbildet. Betrachte die Zahl z, deren xte Binärdarstellungs-Nachkommastelle angibt ob die Turingmaschine f(x) auf der leeren Eingabe jemals hält. Die Zahl z ist offensichtlich eine reelle Zahl. Sie ist aber keine berechenbare Zahl. Angenommen sie wäre berechenbar. Dann könnte ich jede beliebig genaue Annäherung daran berechnen und entscheiden, ob die xte Turingmaschine auf der leeren Eingabe hält (einfach Genauigkeit $\varepsilon :=2^{-x}$ wählen und xte Nachkommastelle betrachten). Nun ist aber wohlbekannt, dass das Halteproblem nicht entscheidbar ist, also ist z nicht berechenbar.

Natürlich kann ich keine solche Zahl (konstruktiv) 'angeben', weil nicht berechenbare Zahlen eben nicht berechenbar, also nicht konstruierbar sind. Ich kann nur manche anhand ihrer Eigenschaften beschreiben und mit tertium non datur ihre Existenz beweisen.

Vorsicht vor einigen Fallen: Es gibt durchaus berechenbare Folgen die gegen eine nicht berechenbare Zahl konvergieren, z.B. für die Zahl z (Algorithmus für eine solche Folge etwas länglich, aber glaub mir, dass so etwas existiert). Allerdings enthält die Definition die zusätzliche Einschränkung $|z-q|<\varepsilon$.

Dies sind alles ziemlich grundlegende Kenntnisse auf dem Gebiet der Grundlagen der Berechenbarkeitstheorie. Ich empfehle Dir ein gutes Buch darüber zu lesen, Lewis/Papadimitriou soll ganz okay sein, auch wenn ich nur einmal reingeschaut und auch einige Kritik darüber gehört habe. --Rtc 02:41, 10. Aug 2005 (CEST)

Ich wusste, dass Du das schreiben würdest. Sehr konsequent vorgetragen. Aber falsch. Bewiesen wird jeweils nur, dass die Ausgangsmenge nicht alle berechenbaren Zahlen enthielt. Du bist - ich wette um einen Kasten Weizenbier - nicht in der Lage eine reelle Zahl (die Gunther als reelle Zahl akzeptiert, also ohne Schlunsens mit Zukunft und so) anzugeben, die nicht berechenbar ist. Der Cantor Beweis (und auch Gödel und Turing-Halteproblem) beweist nur, dass die ursprüngliche Menge noch nicht vollständig war. PaCo 08:55, 10. Aug 2005 (CEST)

Es ist nicht falsch. Ich habe nun mehrfach bewiesen, dass es Zahlen gibt, die nicht berechenbar sind. Ich weiß nicht, was Du noch willst. Die von mir angegebenen Beweise sind korrekt bezüglich klassischer Mathematik. Ich empfehle Dir nochmals dringend, Dich in die Thematik einzuarbeiten, und dann stichhaltige Begründungen zu nennen statt einfach unbegründet und mit unklarer Formulierung immer nur das Gegenteil in den Raum zu stellen. Wäre sensationell, wenn Du beweisen könntest, dass das alles falsch ist -- damit würdest Du auf einen Schlag die gesamte Berechenbarkeitstheorie wie sie heute existiert in ihren Grundfesten erschüttern. Ich glaube aber, das Fundament wird Dir standhalten. Viel glück. --Rtc 21:17, 10. Aug 2005 (CEST)

Das ist also Klassische Logik: Meins ist falsch, weil wenn es richtig wäre, wäre es sensationell. ;) Diese Auffassung, den Cantorschen Beweis als Beweis dass die Mengen reeller (=berechenbarer) Zahlen immer vervollständigbar bleiben zu verstehen, stammt nicht von mir. Sie ist auch von Lorenzen nur aufgenommen worden und stammt von H. Poincarè und H. Weyl. Soll ich auf zwei Kästen Weizenbier erhöhen? PaCo 00:55, 11. Aug 2005 (CEST)

Dies ist ein Artikel zur Mathematik, Bereich Berechenbarkeitstheorie, keiner zur KM. In der KM mag stimmen was Du gesagt hast weil dort der Begriff der reellen Zahlen anders ist; in der Mathematik jedoch nicht. --Rtc 01:05, 11. Aug 2005 (CEST)

Das Problem liegt darin, dass Berechenbarkeit in gewisser Weise ein schwacher Begriff ist. Das cantorsche Diagonalverfahren auf der Menge der berechenbaren Zahlen ist zwar intuitiv nachvollziehbar, überfordert aber offenbar eine Turing-Maschine ;-) Siehe auch en:Chaitin's constant, eine nicht berechenbare Zahl, von der man sogar einige Stellen kennt.--Gunther 01:49, 11. Aug 2005 (CEST)

Es gibt kein Problem. Nimm ne beliebige nicht berechenbare Zahl, füge als erste n Nachkommastellen Nullen ein und Du hast immer noch eine nicht berechenbare Zahl. Trotzdem kennst Du nun die ersten n Nachkommastellen. --Rtc 16:28, 11. Aug 2005 (CEST)

Ich wollte damit nur ausdrücken, dass es keine abstrakte Zahl ist, über die man nichts weiß.--Gunther 16:34, 11. Aug 2005 (CEST)

Also, da hier keiner drauf eingeschlagen hat, ziehe ich erstmal mein Wettangebot zurück. PaCo 20:30, 11. Aug 2005 (CEST)

Und jetzt nochmal. Gunther, heißt das, diese Chaitin's constant ist eine reelle Zahl? Wie ist die genau definiert? PaCo 20:33, 11. Aug 2005 (CEST)

Falls ja, worin unterscheidet sie sich vom Typ her von unseren Donnerstagszahlen (einbindung von zukünftigen Ereignissen in die Wahl von Nachkommasequenzen)? PaCo 20:56, 11. Aug 2005 (CEST)

Ja, die Chaitin-Konstante ist eine reelle Zahl, und sie unterscheidet sich von Donnerstagszahlen dadurch, dass sie unter ausschließlicher Verwendung der Sprache der Mathematik/Mengenlehre charakterisiert werden kann.--Gunther 10:40, 21. Aug 2005 (CEST)

OK, danke für die Info. Und wenn ich die Zahlen abhängig mache, von der Lösung bisher ungelöster Probleme? Dann habe ich mathematische Sprache, aber zukünftige heute nicht bestimmte Ereignisse. PaCo 10:52, 21. Aug 2005 (CEST)

Das ist kein Problem. Du kannst reelle Zahlen sogar von unentscheidbaren Aussagen abhängig machen: Die Zahl, die 1 ist, falls die Kontinuumshypothese "wahr" ist (als Formel des verwendeten Systems), ansonsten 0, ist eine reelle Zahl. Das hat dann mit dem Heute und der Zukunft nichts zu tun.--Gunther 11:01, 21. Aug 2005 (CEST)

Die Mathematiker wissen heute nicht, welche Zahl es ist, 1 oder 0. PaCo 11:25, 21. Aug 2005 (CEST)

Spielt doch keine Rolle, da sowohl 1 als auch 0 beides reelle Zahlen sind. --83.169.149.162 20:29, 21. Aug 2005 (CEST)

@PaCo: Mit "heute" hat das nichts zu tun. Die Kontinuumshypothese ist unabhängig von ZFC, sie ist also "in der realen Welt" weder wahr noch falsch (d.h. weder beweisbar noch widerlegbar).--Gunther 20:42, 21. Aug 2005 (CEST)

Ich glaube wir kennen unsere gegenseitigen Standpunkte. Ich würde halt sagen: Nehmen wir ein noch nicht gelöstes mathematisches Problem (Goldbach-Vermutung, was weiß ich) nun bestimme ich Nachkommaentwicklungen von reellen Zahlen (etwa alle durch 3 teilb. Nachkommastellenindizes) abhängig von der Lösung des Problems. Also etwa Quadratwurzel 2 wenn es stimmt, Qw 3 wenn nicht. Die Nachkommastellen der Wurzeln werden auf die genannten Nachkommastellen verteilt... Dies läßt sich nicht mehr von den "Donnerstagszahlen" unterscheiden, obwohl es nun mathematisch formulierbar wird. Mit der Kontinuumshypothese ist es anders, da hast Du recht. PaCo 11:38, 22. Aug 2005 (CEST)

Ich hatte die CH gewählt, weil ich dachte, dass Du damit tendenziell noch mehr Probleme hast als mit lediglich bislang unbewiesenen Vermutungen. Mal anders, weg von Dezimaldarstellungen: Würdest Du auch sagen, dass die minimale Zahl $k$, so dass sich jede gerade Zahl $>2$ als Summe von $k$ Primzahlen schreiben lässt, keine natürliche Zahl ist, solange ihr exakter Wert unbekannt ist? (Laut en:Goldbach's conjecture ist sie jedenfalls kleiner als $10^{50000}$.) Oder einfacher: Die Zahl, die 1 ist, falls Goldbach wahr ist, und 0 andernfalls?--Gunther 12:10, 22. Aug 2005 (CEST)

Ja, die Goldbachvermutung ist ja einschlägig in dieser Sache :) Zählt man 0 zu den natürlichen Zahlen, so sind 1 und 0 natürliche Zahlen. Deswegen habe ich es ja so bestimmt, dass Goldbach "ja" zu einer anderen Nachkommaentwicklung (einer ansonsten reellen Zahl z) führt als Goldbach "nein". Da es doch sein kann, dass jemand das Goldbach-Problem in Zukunft löst, wird hier also etwas von einem zukünftigen Ereignis abhängig gemacht. - Nein, wirst du sagen, es steht ja fest, wir wissen es nur noch nicht. Stimmt das? Das wirst Du doch sagen, oder? - Und da sagt nun die intuitionistische Logik, es steht nicht fest. :) PaCo 09:15, 23. Aug 2005 (CEST)

Ja, das würde ich sagen. Und Du würdest also sagen, dass die beschriebenen Zahlen keine nichtnegativen ganzen Zahlen ;-) sind? Was sind sie denn dann überhaupt?--Gunther 09:51, 23. Aug 2005 (CEST)

Na ja, nein nicht ganz, ich bin gar nicht Intuitionist. Ich bin an der Dialogischen Logik interessiert. Philosophen wie L. Wittgenstein (Bemerkungen über die Grundlagen der Mathematik) und Lorenzen würden Dich fragen, welche Zahlen Du denn nun *meinst*. W. sagt dann: worüber man nicht reden kann, darüber soll man schweigen. - ... Ich? - Ich habe halt bei der Beschäftigung mit diesem Kram jedenfalls die Sicherheit verloren, darüber so zu sprechen, dass es diese Zahlen (mit der Faust auf den Tisch hauend) *gibt* oder *nicht gibt* (stampfend mit den Füssen) :) PaCo 10:45, 23. Aug 2005 (CEST)

Ich bin schon sehr versucht, mich auf den formalen Standpunkt zu stellen: Wenn ich eine Eigenschaft $A(x)$ betrachte, die nur auf genau ein x zutrifft, und ich zeigen kann, dass für dieses x die Aussage $x\in \mathbb {R}$ wahr ist, warum soll x dann keine reelle Zahl sein?

Ob es die Zahl gibt... muss mich das interessieren? Ich kann sie denken, das genügt mir, allerdings trifft das auch auf viele Dinge zu, die es nicht gibt (nach allgemeiner Auffassung ;-) --Gunther 11:43, 23. Aug 2005 (CEST)

Ja insofern unterscheidet es sich wieder nicht von den Donnerstagszahlen, weil ich mich da auch auf den Standpunkt stellen könnte: Wenn ich eine Eigenschaft $A(x)$ betrachte, die nur auf genau ein x zutrifft, und ich zeigen kann, dass für dieses x die Aussage $x\in \mathbb {R}$ wahr ist, warum soll x dann keine reelle Zahl sein? PaCo 10:04, 25. Aug 2005 (CEST)

Weil die Eigenschaft A(x) in der Sprache der Mengenlehre nicht formulierbar ist. Deshalb kannst Du auch $A(x)\Rightarrow x\in \mathbb {R}$ nicht formal beweisen.--Gunther 10:15, 25. Aug 2005 (CEST)

Absatz entfernt

Ich habe einen Satz entfernt mit folgendem Inhalt: "Da es nur abzählbar viele Turing-Maschinen, aber überabzählbar viele reelle Zahlen gibt, sind die berechenbaren Zahlen eine echte Teilmenge von $\mathbb {R}$." Dieser Satz war falsch formuliert, weil nur Mengen Teilmengen von Mengen sein können und "die berechenbaren Zahlen" keine Menge ist.

---

und wieso hast du den Satz nicht einfach *verbessert*: "Da es nur abzählbar viele Turing-Maschinen, aber überabzählbar viele reelle Zahlen gibt, ist die Menge der berechenbaren Zahlen eine echte Teilmenge von $\mathbb {R}$."
btw.: "die Menge der berechenbaren Zahlen" ist sogar ein Körper, keine Ahnung, ob das jemand interessiert. 88.217.19.33 03:33, 25. Jul. 2007 (CEST)

---

Nachtrag: Anmerkung zur "Definition" im Artikel:
Zitat: "genau dann berechenbar, wenn es eine Turing-Maschine gibt"
[a] der Begriff Turing-Maschine ist insofern irreführend, als daß eigentlich eine "Typ2-Maschine" gemeint ist, die im Gegensatz zur "normalen" Turing-Maschine nicht nur unbegrenzte, sondern auch unendliche Werte auf den Eingabebändern und dem Ausgabeband zuläßt.
[b] die Definition über Turing/Typ2-Maschinen ist *eine* von mehreren Definitionen, andere Definitionen führen zu einer anderen Menge der berechenbaren Zahlen.
88.217.19.33 03:46, 25. Jul. 2007 (CEST)

Penrose

Ich habe mal in Penrose Computerdenken nachgesehen und seine Definition im Artikel wiedergegeben, inklusive Literaturangabe und Beispiel für eine nicht-berechenbare Zahl.--AlfonsGeser 18:09, 24. Mai 2008 (CEST)

fast alle

Der Ausdruck "fast alle" wird hier falsch verwendet. "Alle bis auf endlich viele" kann nicht auf "Überabzählbar bis auf abzählbar" übertragen werden. Abzählbar unendlich ist trotzdem unendlich.--Pacogo7 21:32, 3. Mai 2009 (CEST)

Berechenbare Zahlen invertierbar?

Berechenbare Zahlen sind mit Sicherheit nicht berechenbar invertierbar. Beispiel: Betrachte eine diophantische Gleichung P(x,y,...)=0, eine Aufzaehlung der Tupel, und definiere f(i)=1, falls das i-te Tupel eine Loesung ist, und f(i)=0 sonst. Dann beschreibt f eine berechenbare Zahl x (Testen ob ein gewisses Tupel eine Gleichung loest ist berechenbar). Die erste Ziffer von (1+x)^(-1) ist 1 genau dann, wenn die Gleichung keine Loesung besitzt. Da das Loesen von diophantischen Gleichungen zum Halteproblem aequivalent ist, gibt es also berechenbare Zahlen, deren Inverses eine nicht berechenbare erste Stelle haben. Will man einen Koerper haben, muss man reelle Zahlen ueber beliebige Cauchyfolgen definieren. (nicht signierter Beitrag von 91.23.97.199 (Diskussion) 16:33, 2. Jan. 2014 (CET))

Es heißt auch, die Addition wäre berechenbar. Zumindest stimmt das nicht im Sinne der Definition. Die i-te Stelle einer Addition kann nicht immer berechnet werden (Beispiel r = 0,101... + 0.010...: Ist die erste Stelle von r 1 oder 0?). Ich denke, hier müssten entweder Definition oder die Aussage über die Berechenbarkeit von Summe, Produkt und Inverses verändert werden. --130.133.8.114 00:43, 20. Jan. 2016 (CET)

Vorsicht: Es heißt nicht, dass die Addition berechenbar ist, sondern nur, dass die Summe wiederum eine berechenbare Zahl ist. Und das stimmt, auch in deinem Beispiel (und wie du dann leicht siehst, immer). Allerdings ist die Definition, die angegeben war, eher unüblich, ich hab mal ersetzt. Dann ist auch die Addition berechenbar. -Chricho ¹ ² ³ 00:58, 20. Jan. 2016 (CET)

Die Gleichheit berechenbarer Zahlen ist nicht berechenbar, daran liegt es. --Chricho ¹ ² ³ 01:02, 20. Jan. 2016 (CET)