nicht-berechenbare Mengen

[tomS]

Ich denke, wir sind (und ich war) hier sprachlich unpräzise.

Eine Aussage ist beweisbar, wenn innerhalb eines Axiomensystems ein endlicher Beweis für diese Aussage existiert.
Eine Zahl ist berechenbar, wenn ein endlicher und in endlich vielen Schritten terminierender Algorithmus (eine Turingmaschine) existiert, der diese Zahl als Ergebnis ausgibt.

D.h. dass sich Beweisbarkeit auf Aussagen und Berechenbarkeit auf Zahlen (u.a. mathematische Objekte) bezieht. Damit sind beide Begriffe m.E. nicht identisch, sie sind jedoch verwandt und für bestimmte Probleme unter bestimmten Voraussetzungen äquivalent.

Es gibt jedoch auch Fälle, anhand derer man explizit erkennt, dass diese Begriffe i.A. nicht identisch sind. Z.B. kann man in ZFC die Existenz bestimmter Zahlen und Objekte beweisen, ohne sie berechnen bzw. konstruieren zu können. Man kann sogar beweisen, dass letzteres nicht funktioniert: es gibt überabzählbar viele reelle Zahlen jedoch nur abzählbar viele Turimgmaschinen mit Input; deswegen können nicht alle reellen Zahlen berechenbar sein; umgekehrt: "fast alle" reellen Zahlen sind nicht-berechenbar.

Ein explizites Beispiel für eine nicht-berechenbare Zahl ist die Chaitinsche Konstante, die beweisbar existiert jedoch ebenso beweisbar nicht berechenbar ist.

[Skeltek]

Wetten wir, man kann durch ein Diagonalargument beweisen, dass es zu jeder beliebigen abzählbar unendlichen Menge an Algorithmen, immer mindestens einen Algorithmus gibt, welcher die Termination aller Algorithmen in der Liste voraussagen kann?
Egal welche Algorithmen man aufzählt, es bleibt immer mindestens ein möglicher Algorithmus übrig, welcher die Termination aller aufgezählten vorhersagen kann.
So gesehen wäre beweisbar, dass ein Algorithmus existiert, allerdings kann man ihn nicht benennen oder angeben, er ist sozusagen 'transzendent'.

[tomS]

Du meinst einen reinen Existenzbeweis, aus dem sicher die Existenz folgt, jedoch gerade nicht, welcher der Algorithmen dies ist?

Ich denke, dass auch das gem. der Sätze von Gödel und Turing widerlegt ist:

https://de.m.wikipedia.org/wiki/Halteproblem

Hier wird explizit gezeigt, dass das Halteproblem auch für die reine Existenzfrage auf einen Widerspruch führt.

[seeker]

gibt es auch ein einfaches Beispiel einer nicht-berechenbaren Untermenge der natürlichen Zahlen?

Hierzu ist mir noch eingefallen, dass das auch für alle zufällig gewählten Teilmengen aus N gilt (es muss ja nicht gleichverteilt-zufällig gewählt werden).
Dass diese Zahlenmengen existieren scheint mir allerdings nicht auf einem nicht-konstruktiven Beweis zu beruhen, sondern eher auf einer Definition/Grundannahme, die da lautet: "Zahlen können zufällig gewählt werden!"
Das geht also auch, ist aber wohl nicht das, was du im Sinn hattest, jedoch in gewisser Weise das einfachste Beispiel.

Man muss hier nur unterscheiden, ob der Algorithmus nur einseitig oder auch zweiseitig funktioniert (bzw. ob ein solcher existiert), ob er also auch bei Input (geraten) = "falsch" irgendwann fertig wird und ein Ergebnis liefert.

Das hier war mir wichtig, weil der Algorithmus "alles durchprobieren" oft nur einseitig funktioniert.
Das wär dann bei der Rado-Funktion so:

10 n = 0
20 Lasse eines der Programme bb(n) laufen und stelle fest, wie viele Striche x(i) es zeichnet (und damit auch ob es hält)
30 Merke dir x(i)
30 Springe zu 20, falls noch nicht alle Programme bb(n) ausprobiert sind, sonst springe zu 40
40 Vergleiche alle gemerkten x(i) und gebe das größte x(i) aus
50 n = n+1
60 Springe zu 20

Wenn wir nur ein spezielles n von bb(n) untersuchen wollen, dann lassen wir die Zeilen 50 und 60 weg.
Für z.B. n = 4 erhalten wir:

10 n = 4
20 Lasse eines der Programme bb(n) laufen und stelle fest, wie viele Striche x(i) es zeichnet (und damit auch ob es hält)
30 Merke dir x(i)
30 Springe zu 20, falls noch nicht alle Programme bb(n) ausprobiert sind, sonst springe zu 40
40 Vergleiche alle gemerkten x(i) und gebe das größte x(i) aus

Das Problem:
Dieses Programm hält nicht, falls auch nur ein bb(4) nicht hält, es entscheidet das Problem also nur partiell und ist somit nicht sicher zur Lösung der Frage geeignet, die nach dem größten x(i) sucht.

Some Busy Beaver enthusiasts have opined that even BB(6) will never be known exactly. On the other hand, the abstract argument from before tells us only that, if we confine ourselves to (say) ZF set theory, then there’s some k—possibly in the tens of millions or higher—such that the values of BB(k), BB(k+1), BB(k+2), and so on can never be proven. So again: is the number of knowable values of the BB function more like 10, or more like a million?

This is the question that Adam and I (but mostly Adam) have finally addressed.

...

Of course, three orders of magnitude still remain between the largest value of n (namely, 4) for which BB(n) is known to be knowable in ZFC-based mathematics, and the smallest value of n (namely, 7,918) for which BB(n) is known to be unknowable.

Das muss auf einem ein nichtkonstruktiven Beweis beruhen.

Ich habe damit allerdings noch ein Problem:
Wir wissen, dass die Menge der Algorithmen bb(n) überabzählbar-unendlich groß ist, es aber bei n e N nur abzählbar-unendlich viele n gibt. Daher muss es hier nicht-berechenbare x(i) von bb(n) geben. Aber wo soll der Übergang sein? Bei n = 3 sind es abzählbar endlich viele Algorithmen bb(n), bei n = 4 auch, es kann doch nicht sein, dass es bei n = 7918 überabzählbar-unendlich viele sind, denn dann hätten wir irgendwo davor einen Unendlichkeitsübergang gehabt: z.B. wären es bei n = 7917 noch endlich viele gewesen und dann bei n = 7918 nicht mehr, das geht nicht.
Es geht mir hier um die prinzipielle Unberechenbarkeit, die praktische ist klar...

[tomS]

Das muss auf einem ein nichtkonstruktiven Beweis beruhen.

Das ist wohl so.

Wir wissen, dass die Menge der Algorithmen bb(n) überabzählbar-unendlich groß ist

Nein, die Menge der Algorithmen ist abzählbar unendlich.

Das ist recht einfach einzusehen: jeder Algorithmus ist ein Computerprogramm aus endlich vielen Zeichen bzw. eine endliche Turingmaschine; diese kann man z.B. alphanumerisch sortieren und erhält daraus eine abzählbare Liste.

[seeker]

Nein, die Menge der Algorithmen ist abzählbar unendlich.

Das ist recht einfach einzusehen: jeder Algorithmus ist ein Computerprogramm aus endlich vielen Zeichen bzw. eine endliche Turingmaschine; diese kann man z.B. alphanumerisch sortieren und erhält daraus eine abzählbare Liste.

Ja, ok, Lapsus. Die Menge aller Funktionen ist überabzählbar-unendlich.
Mein Verständnisproblem bleibt damit bestehen.

[tomS]

Mein Verständnisproblem bleibt damit bestehen.

Erklär' nochmal.

[Skeltek]

Ja, das ist der entscheidende Punkt, die betrachteten Algorithmen werden a priori auf nur endliche Algorithmen festgelegt.
Aber das ist doch dasselbe wie mit Zahlen: Jede abzählbar unendliche Liste an Algorithmen ist unvollständig, selbst wenn man diese nicht auf Algorithmen beschränkt welche aus einer endlichen Anzahl an Instruktionen bestehen.
Ein Program ist endlich... okay. Aber ein Algorithmus?
Mir ging es mehr um die Unvollständigkeit beider Mengen. Natürlich existiert kein endlicher Algorithmus; da hast du völlig recht.

[tomS]

Ja, das ist der entscheidende Punkt, die betrachteten Algorithmen werden a priori auf nur endliche Algorithmen festgelegt.

Ein Algorithmus ist per Definitionen eine endliche Anweisungslisze bzw. ein endliches Programm mit endlichem Input. Oder anders gesagt, es entspricht einer Turingmaschine mit endlich vielen Zuständen und endlichem Input aus einem endlichen Alphabet.

Jede abzählbar unendliche Liste an Algorithmen ist unvollständig, selbst wenn man diese nicht auf Algorithmen beschränkt welche aus einer endlichen Anzahl an Instruktionen bestehen.

Doch, die Liste ist eben gerade nicht unvollständig; die Liste der endlichen Algorithmen ist konstruierbar, bzw. die endlichen Algorithmen sind aufzählbar.

Mir ging es mehr um die Unvollständigkeit beider Mengen.

nein - s.o.

Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar. Man startet mit einem endlichen Alphabet, z.B. {a ... z, A ... Z, 0 ... 9} plus die Menge der erlaubten Sonderzeichen {.,;:/\-+*^%# usw}. Man generiert alle Programme der Länge 1, 2, 3, ... und lässt über jedes so generierte Programm den Compiler zwecks Syntaxprüfung darüberlaufen. Im Fehlerfall verwirft man das Programm, andernfalls fügt man es zur Menge der syntaktisch korrekten Programme hinzu. Ineffizient aber OK.

[Skeltek]

Das sagte ich doch, wenn auch nicht völlig korrekt formuliert. Die Auswahl wird per Definition von vorn herein eingeschränkt.
Welchen Begriff hätte ich denn verwenden sollen für eine nichtperiodische totalgeordnete Menge an abzählbar unendlich vielen Einzelschritten?

Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.

Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.
Auf dem PC bekommt man sowas dann nicht zum laufen.
Hier gibt es ein Trade-Off zwischen maximaler Anzahl der Befehle und der Zustände.
Man kann diese Algorithmen auch zustandslos gestalten, indem man statt einer unendlichen Anzahl potentieller Zustände eine unendlich lange Liste an Einzelschritten in den Algorithmus packt. Der Begriff Algorithmus hat erst im Laufe der Hin- und Her-Definition seine Einschränkung auf eine endliche Anzahl an Einzelschritten erhalten. Heute ist die Definition, die sich zur Zeit von Turing entwickelt hat die gebräuchlichste und vom Großteil anerkannte.

[tomS]

Das sagte ich doch, wenn auch nicht völlig korrekt formuliert. Die Auswahl wird per Definition von vorn herein eingeschränkt.

Ja, es geht hier einfach um eine Definition.

Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.

Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.

Die formale Definition gem. Turing schränkt dies ein. Die Anzahl der internen Zustände der Maschine ist endlich, und da die Maschine halten soll ist auch der Output auf dem (unendlichen) Band endlich.

Auf dem PC bekommt man sowas dann nicht zum laufen.

Es geht mir nicht um die Ausführung der Programme sondern um deren Generierung.

[Skeltek]

Die Liste der endlichen Programme ist auf jedem PC sehr einfach generierbar.

Würde ich so jetzt nicht stehen lassen. Auch endliche Programme können abzählbar unendlich viele Zustände durchlaufen.

Die formale Definition gem. Turing schränkt dies ein. Die Anzahl der internen Zustände der Maschine ist endlich, und da die Maschine halten soll ist auch der Output auf dem (unendlichen) Band endlich.

Ja, jetzt bist du aber nicht mehr bei Algorithmus, sondern schon bei endlichen Automaten usw angekommen.
Was ist mit der Berechnung von Pi, der sequentiellen Berechnung aller Nullstellen der riemanschen Zeta-Funktion oder dem einfachen Aufzählen aller natürlichen Zahlen? Hier braucht der Algorithmus in jedem Fall unendlich viele mögliche Zustände - sonst wüsste er ja nicht einmal, wie weit er bereits gezählt hat.
Hier würde ich Algorithmus und Maschinen besser getrennt behandeln.

Was ich sagen wollte war, dass man in diesem Fall sich jegliche Form von Zustandserfassung sparen könnte, indem man einfach eine unendliche Kette/Menge an Einzelschritten formuliert.

[tomS]

Ja, jetzt bist du aber nicht mehr bei Algorithmus, sondern schon bei endlichen Automaten usw angekommen.
Was ist mit der Berechnung von Pi, der sequentiellen Berechnung aller Nullstellen der riemanschen Zeta-Funktion oder dem einfachen Aufzählen aller natürlichen Zahlen? Hier braucht der Algorithmus in jedem Fall unendlich viele mögliche Zustände - sonst wüsste er ja nicht einmal, wie weit er bereits gezählt hat.

Nein.

Die Menge der erlaubten inernen Zustände der Turingmaschine bzw. des Algorithmus ist immer endlich; das Alphabet der auf das Band zu schreibenden Symbole ist ebenfalls immer endlich.

Die Ausgabe auf dem Band kann potentiell unendlich sein, und darüber kann auch eine potentiell unendliche Buchführung realisiert werden (man kann zeigen, dass man viele Freiheiten hat, was intern in der Maschine und was extern auf dem Band abgebildet / gespeichert wird, aber die präzise Definition sieht eben ausschließlich das Band. / den Speicher als unendlich vor).

Endliche Automaten können durchaus auf einem unendlichen Speicher operieren. Z.B. kann man für Conway's Game of Life beweisen, dass es Turing-vollständig ist.