Goldbach-Vermutung und Busy-Beaver-Zahlen?

Hintergrund: Ich bin ein kompletter Laie in der Informatik.

Ich las über Busy Beaver Zahlen hier , und ich fand die folgende Passage:

Die Menschheit kann den Wert von BB (6) niemals genau kennen, geschweige denn den von BB (7) oder eine höhere Zahl in der Sequenz.

In der Tat entziehen sich uns bereits die Top-Fünf- und Sechs-Regel-Kandidaten: Wir können nicht erklären, wie sie in menschlicher Hinsicht „funktionieren“. Wenn Kreativität ihr Design beeinflusst, liegt es nicht daran, dass Menschen es dort platzieren. Ein Weg, dies zu verstehen, ist, dass selbst kleine Turing-Maschinen tiefgreifende mathematische Probleme kodieren können. Nehmen wir Goldbachs Vermutung an, dass jede gerade Zahl 4 oder höher eine Summe von zwei Primzahlen ist: 10 = 7 + 3, 18 = 13 + 5. Die Vermutung hat sich seit 1742 dem Beweis widersetzt. Dennoch könnten wir eine Turing-Maschine mit beispielsweise 100 Regeln entwerfen, die jede gerade Zahl prüft, um festzustellen, ob es sich um eine Summe von zwei Primzahlen handelt Vermutung. Wenn wir BB (100) kennen, können wir diese Maschine im Prinzip für BB (100) -Schritte ausführen, entscheiden, ob sie anhält, und damit Goldbachs Vermutung auflösen.

Aaronson, Scott. "Wer kann die größere Zahl nennen?" Wer kann die größere Zahl nennen? Np, nd Web. 25. November 2016.

Mir scheint, der Autor schlägt vor, dass wir die Goldbach-Vermutung, eine Aussage über unendlich viele Zahlen, in einer endlichen Anzahl von Berechnungen beweisen oder widerlegen können. Vermisse ich etwas?

Die Aussage handelt von unendlich vielen Zahlen, aber ihre Demonstration (oder Widerlegung) müsste eine endliche Übung sein. Wenn möglich.

Die Überraschung könnte von der (falschen) Annahme herrühren, dass das Auffinden von BB (100) ein "theoretisch einfacheres" Problem wäre, das nur aus praktischen Gründen unmöglich ist - da es so viele Maschinen gibt und sie so lange laufen können, bevor sie anhalten wenn überhaupt - es sind ja nur maschinen ...

Die Wahrheit ist, dass es sowohl aus theoretischen als auch aus praktischen Gründen eine unüberwindliche Aufgabe sein muss, BB (n) für n zu entdecken, das groß genug ist .

Die Idee des Autors war, dass Sie ein Programm in 100 Zeilen schreiben können (jede feste endliche Zahl hier), das Folgendes bewirkt: Nimmt die Zahl x, testet die Vermutung. Wenn dies nicht der Fall ist, hören Sie auf, sonst fahren Sie mit der nächsten Nummer fort.

Wenn Sie die Anzahl der beschäftigten Biber kennen, können Sie diese Maschine für diese Anzahl von Schritten simulieren und dann entscheiden, ob sie anhält oder nicht. Von oben, wenn es anhält - Vermutung nicht wahr, wenn es nicht anhält - Vermutung ist wahr.

Aaronson hat kürzlich in Zusammenarbeit mit Yedidia ausführlich auf diese Überlegung / Idee eingegangen. [1] Sie finden eine explizite 4888-Zustandsmaschine für die Goldbachs-Vermutung. Sie können das Papier lesen, um zu sehen, wie es aufgebaut wurde. TMs werden selten erstellt, aber diejenigen, die in der Regel compilerähnlich sind, basieren auf Hochsprachen, und die Compiler fügen viele Zustände hinzu. Ein "handgefertigtes" TM könnte leicht eine um eine Größenordnung geringere Anzahl von Zuständen verwenden, z. B. in den 100ern oder weniger. Mit anderen Worten, in diesem Artikel wurde nicht wirklich versucht, die Anzahl der Zustände wirklich zu minimieren . Die allgemeine Idee ist Ton und Informatiker sind im Allgemeinen nicht so besorgt über die genauen Konstanten für die angewandte Arbeit.

Diese allgemeine Theorie wird von den Caludes (auch von [1] zitiert) in zwei ausgezeichneten Abhandlungen umrissen, in denen einige der Sätze der langen Folklore in diesem Bereich dargelegt sind und die von anderen Autoren (z. B. Michel) erwähnt wurden. [2] 3] Grundsätzlich kann jedes offene mathematische Problem in unentscheidbare Probleme umgewandelt werden. Dies liegt daran, dass die meisten mathematischen Probleme darin bestehen, eine unendliche Anzahl von Fällen nach Gegenbeispielen zu durchsuchen, und Gegenbeispiele algorithmisch überprüfbar sind (aber möglicherweise ineffizient sind oder große TMs usw. erfordern).

Auch "sehr kleine" TMs (gezählt in Anzahl von Zuständen) können äquivalente, sehr komplexe mathematische Probleme prüfen / sein. Beispiel: Eine grobe Schätzung für ein TM, um die Kollatz-Vermutung aufzulösen, wäre ein paar Dutzend Zustände.

Es gibt also einen interessanten Zusammenhang / eine interessante Analogie zwischen Unentscheidbarkeit und NP-Vollständigkeit. NP ist die Klasse der effizient überprüfbaren Probleme, dh Instanzen können in P-Zeit überprüft werden. Unentscheidbare Probleme sind die Klasse aller Probleme, die eine algorithmische Überprüfung auf Gegenbeispiele ohne Einschränkung der Effizienz ermöglichen.

Hier ist ein grundlegender Weg, um den Zusammenhang mit dem Problem der beschäftigten Biber zu verstehen. Alle unentscheidbaren Probleme sind aufgrund der Berechenbarkeit / Äquivalenz von Turing gleichwertig. Ähnlich wie alle NP-Gesamtprobleme in P-Zeit (Verringerungen) ineinander umgewandelt werden können, sind alle unentscheidbaren Probleme aufgrund der Turing-Vollständigkeit und berechenbaren Verringerungen (die eine beliebige Zeit in Anspruch nehmen können) gleichwertig. Daher ist das Problem der beschäftigten Biber in diesem Sinne gleichbedeutend mit dem Problem der Unterbrechung, und wenn man beschäftigte Biber lösen könnte, dann könnte man alle offenen mathematischen Fragen lösen.

[1] Eine relativ kleine TM, deren Verhalten unabhängig von der Mengenlehre ist / Yedidia, Aaronson

[2] Bewertung der Komplexität mathematischer Probleme: Teil 1 / Calude

[3] Bewertung der Komplexität mathematischer Probleme: Teil 2 / Calude

1. Die Goldbach-Vermutung kann durch ein solches TM-Programm gefälscht werden (wenn sie tatsächlich falsch ist). es kann auf diese Weise nicht als richtig erwiesen werden (ein einsichtiger Mathematiker könnte dies jedoch tun).

2. Die Kenntnis von BB (27) würde es erlauben, die Goldbach-Suche irgendwann zu stoppen; Dennoch muss BB (27) (oder Chaitins Omega (27)) vorher wissen, ob der Goldbach TM schließlich stoppt oder nicht.

Es ist daher irreführend zu sagen, dass "BB (27) die Antwort auf Goldbach enthält". Es geht aber eher darum: "Goldbach (und viele andere) sind Voraussetzungen für die Nummer BB (27)", mit anderen Worten, es gibt keine "BB-Funktion", die Sie mit 27 herausfordern. Wir einfach alle 27-state maschinen laufen lassen, inkl. Goldbach und erst danach siehe BB (27). Und von einem praktischen POV aus scheint sogar BB (6) schwer fassbar zu sein.

Ich denke, es fühlt sich weniger mysteriös an, wenn wir Aaronsons Argument in Bezug auf Beweise wiederholen:

$C$$C$$C$$C$ und prüfen, ob eine davon ein gültiger Beweis ist.

$C$$C$$n$$BB(n)$$C = O(BB(n))$