Warum sind berechenbare Zahlen (im Sinne von Turing) aufzählbar?

Warum sind berechenbare Zahlen (im Sinne von Turing) aufzählbar? Es muss sehr offensichtlich sein, aber ich sehe es momentan einfach nicht.

Ich gehe davon aus, dass Ihre Definition einer berechenbaren Zahl folgende ist: Es gibt eine Turing-Maschine, die bei Eingabe mit dem ten Bit der Zahl anhält .$n$$n$

Angenommen, es gab eine rekursive Aufzählung von Turing-Maschinen, die berechenbare Zahlen erzeugen. Sie können die Diagonalisierung verwenden, um eine neue berechenbare Zahl zu erhalten, die nicht Teil dieser rekursiven Aufzählung ist.

Es ist verlockend, berechenbare Zahlen durch Aufzählen von Turing-Maschinen aufzulisten, aber nicht jede Turing-Maschine entspricht einer berechenbaren Zahl, und im Allgemeinen ist die Entscheidung, ob eine Turing-Maschine für alle Eingaben anhält (geschweige denn 0 oder 1 ausgeben), nicht berechenbar. Es ist jedoch möglich, alle effizienten berechenbaren Zahlen, beispielsweise diejenigen, deren Laufzeit polynomisch ist, unter Verwendung getakteter Turing-Maschinen aufzulisten.

Wenn Sie mit aufzählbar meinen, dass es eine Bijektion mit den natürlichen Zahlen gibt (dh zählbar), dann sind nein, berechenbare Zahlen nicht aufzählbar.

Definieren wir das Problem genauer: Eine "Number-Printing Turing Machine (NPTM)" ist eine Turing-Maschine, die für jeden Zustandsübergang möglicherweise nichts oder eine Dezimalstelle, das Minuszeichen oder den Punkt druckt. Dies reicht aus, um Dezimaldarstellungen von reellen Zahlen zu drucken.

Definieren wir eine berechenbare reelle Zahl als jede reelle Zahl, die von einem NPTM ausgehend von einem leeren Band mit beliebig langer Darstellung bei ausreichender Zeit gedruckt werden kann. Nehmen wir auch an, dass eine Zahl von einem gegebenen NPTM berechnet wird, wenn sie entweder nach dem Drucken einer wohlgeformten reellen Zahl anhält (in diesem Fall hat die Zahl eine endliche Dezimaldarstellung) oder in einer endlichen Zeitspanne eine wohlgeformte Zahl druckt mit einem Dezimalpunkt und erhöht immer die Genauigkeit der Zahl, indem mehr Ziffern gedruckt werden, wenn immer mehr Zeit zur Verfügung steht.

Diese spätere Bedingung ist erforderlich, weil, wenn wir eine Maschine haben, die zum Beispiel eine unendliche Folge einer Ziffer druckt, sagen wir 1111111111111111111..., keine reelle Zahl berechnet werden kann, da reelle Zahlen nur rechts eine unendliche Darstellung haben Seite der Dezimalperiode. Wenn die Maschine dagegen druckt 3.14und dann aufhört zu drucken, aber niemals anhält, kann nicht gesagt werden, dass sie eine reelle Zahl berechnet, nur weil die Genauigkeit der Zahl nicht zunimmt, so dass diese spezielle Maschine sie nicht konstruiert des Weiteren.

Dies sind Beispiele für NPTM, die eine bestimmte Zahl berechnen. Ein NPTM, der:

• druckt 1und hält dann an. Es berechnet die Nummer 1.
• druckt 1.0und hält dann an. Es berechnet auch die Nummer 1.
• druckt 1.0000000und druckt für immer Nullen. Dieser berechnet auch die Nummer 1.
• druckt 3.14und hält dann an. Es berechnet die Nummer 3.14.
• druckt 3.14159und druckt für immer Ziffern von . Dieser berechnet die Zahl .$\pi$$\pi$
• druckt -42.und hält dann an. Es berechnet die Zahl -42.

Und dies sind Beispiele für NPTM , die Sie nicht eine beliebige Anzahl berechnen. Ein NPTM, der:

• druckt 123123123und druckt dann die Sequenz 123für immer weiter. Berechnet keine Zahl, weil diese unendliche Folge keine reelle Zahl darstellt.
• druckt 1.0.0und hält dann an. Liegt nicht daran, dass diese endliche Sequenz nicht gut geformt ist.
• druckt ....-..---und hält dann an. Ist nicht, weil dies auch keine wohlgeformte reelle Zahl ist.
• druckt nie etwas, hält aber auch nie an. Es wird keine Nummer erstellt.
• druckt nie etwas und hält sofort an. Es wurde keine Nummer erstellt.
• druckt 3.14, hört nicht auf, druckt aber auch nie etwas anderes. Berechnet keine Zahl, weil ihre Genauigkeit mit der Zeit nicht zunimmt.

Du hast die Idee. Dann haben wir zwei Klassen von NPTM: diejenigen, die eine reelle Zahl berechnen, und diejenigen, die dies nicht tun.

Das Problem beim Auffinden einer Aufzählung für die berechenbaren Zahlen besteht darin, dass wir, selbst wenn die NPTM selbst zählbar sind, keine Prozedur haben können, die eine Art von NPTM von einer anderen trennt.

Betrachten Sie die Definition der zählbaren Menge: Damit eine Menge zählbar ist, muss eine bijektive Funktion .$S$$F: \mathbb{N} \rightarrow S$

Um zu "beweisen", dass die berechenbaren Zahlen zählbar sind, könnte man versucht sein, eine solche Funktion aus der Zählung des NPTM zu definieren (und dies haben die Leute oft getan, wenn sie glauben, dass die berechenbaren Zahlen zählbar sind). Etwas wie das:

Die NPTM sind zählbar, daher gibt es eine bijektive Funktion , sodass wir alle vorhandenen NPTM für immer aufzählen können. Um also ebenfalls alle berechenbaren Zahlen aufzulisten und die bijektive Funktion genau zu definieren , muss man einfach alle NPTM aufzählen, aber nur diejenigen zählen, die einige berechnen reelle Zahl. Aber woher wissen wir, dass es eine reelle Zahl berechnet?$E_\text{NPTM}: \mathbb{N} -> \text{NPTM}$$E_\text{Computabe}: \mathbb{N} \rightarrow \text{Computable}$

Nun, wir tun es nicht. Stellen Sie sich ein Gerät vor, das sofort druckt 1.0und dann den Druckvorgang beendet und versucht, eine Instanz des Post-Korrespondenzproblems zu lösen . Wenn das Problem behoben ist, wird es angehalten, und die Maschine hat gerade die Nummer eins berechnet. Dieses Problem ist jedoch unentscheidbar, sodass es möglicherweise nie zum Stillstand kommt. Wenn es niemals anhält, berechnet es niemals eine reelle Zahl. Aber wir können nicht wissen, ob es jemals aufhören wird, denn das Problem des Haltens ist auch unentscheidbar! Da es also keine Möglichkeit gibt zu wissen, ob diese bestimmte Maschine und unendlich viele andere Maschinen entweder eine reelle Zahl berechnen oder nicht, können wir unsere bijektive Funktion nicht auf diese Weise erstellen / definieren.

Die naive Art, die Bijektion zu definieren, schlägt fehl, und es ist nicht sehr schwierig zu beweisen, dass es überhaupt keine Möglichkeit gibt, dies zu tun. Wie Yuval Filmus vorgeschlagen hat, kann Diagonalisierung verwendet werden.