Berechnung der Busy-Beaver-Funktion

Die Busy-Beaver-Max-Shift-Funktion hat bekannte Werte für . Gibt es einen grundlegenden strukturellen Grund, warum es unvorstellbar ist, dass wir jemals für ? Was ist so anders an als an ? Oder ? Irgendwo auf dem Weg muss es einen fundamentalen Unterschied geben, sonst wäre im Prinzip für alle berechenbar. Was genau ist dieser Unterschied? $S(n)$ $n\leq4$ $S(n)$ $n>4$ $n=4$ $n=5$ $n=6$ $S(n)$ $n$

computability busy-beaver PeteyPabPro
quelle

Antworten:

Der Grund, warum kein Programm berechnen kann, ist, dass Sie, wenn Sie wissen, was ist, das Problem des Anhaltens entscheiden können - Sie wissen, wann Sie aufhören müssen zu warten. Andererseits gibt es für jedes ein Programm, das für alle berechnet - es verwendet nur eine Tabelle. $S(n)$ $S(n)$ $m$ $S(n)$ $n \leq m$

Wenn es möglich wäre, den Wert von für alle zu beweisen (d. H. Für alle könnten wir beweisen, dass für einige ), könnten wir berechnen, indem wir alle durchsuchen Beweise (dies setzt voraus, dass unser Beweissystem gültig ist). Für jedes Beweissystem gibt es also einen Minimalwert von für den Sie nicht beweisen können, dass für irgendein . $S(n)$ $n$ $n$ $S(n) = \alpha$ $\alpha$ $S(n)$ $n$ $S(n) = \alpha$ $\alpha$

Schließlich ist der Grund, warum wir wahrscheinlich, dass eine wirklich kleine Zahl ist. Die Nummer ist etwas größer und die Dinge werden komplizierter. Es gibt keinen tiefen Grund, warum wir aber nicht , genauso wie es keinen tiefen Grund gibt, warum wir die Ramsey-Zahl aber nicht (obwohl Ramsey-Zahlen natürlich berechenbar sind). . $S(4)$ $4$ $5$ $S(4)$ $S(5)$ $R(4)$ $R(5)$

Yuval Filmus
quelle

Vielen Dank. Der mittlere Absatz war im Wesentlichen das, worüber ich mich wunderte (und es ist ein Beweis von Godel, richtig?). Also könnte es tatsächlich sein, dass

einen Beweis in unserem formalen System hat, aber

nicht.

S (4)

$S(4)$

S (5)

$S(5)$

PeteyPabPro

Vermutlich. Wenn

ist nicht beweisbar, aber wahr, dass

auch nicht beweisbar ist, so haben wir eine Aussage, die weder bewiesen noch widerlegt werden kann.

S (n) = " S (n) "

$S(n)=\text{"}S(n)\text{"}$

S (n) \neq " S (n) "

$S(n)\neq\text{"}S(n)\text{"}$

Yuval Filmus

Sie haben immer noch nicht wirklich erklärt, warum wir so sicher sein können, dass S (4) richtig ist, während S (5) oder höher wir nie wissen können. Liegt es daran, dass wir uns nicht zu 100% mit S (4) befassen, sondern nur "fast" sicher sind?

Dan W

Wir sind uns zu 100% sicher über S (4). Ich glaube nicht, dass es einen tiefen Grund für unsere Ignoranz in Bezug auf S (5) gibt. Es ist nur die aktuelle Grenze unseres Wissens.

Yuval Filmus

Ich glaube, es gibt ein wirklich starkes Proof-System und eine 6-Zustands-2-Farb-Turing-Maschine, so dass bewiesen werden kann, dass es in diesem System keinen Beweis gibt, dass es niemals anhalten wird, und dass es nicht anhalten wird, bevor ein Algorithmus in diesem System bewiesen werden kann innerhalb eines Googol-Charakters, um eventuell anzuhalten.

Timothy

Scott Aaronson diskutiert dies hier . Er und sein Co-Autor finden eine explizite Obergrenze für für die berechnet werden kann. $n$ $S(n)$

PeteyPabPro
quelle

Könnten Sie das relevante Teil zitieren?

Evil

Ein anderer Gesichtspunkt, mit einer informellen Skizze einer Antwort, die eine lange Zeit in Anspruch nehmen würde, um die weitere Forschung technisch zu konkretisieren (dh es handelt sich im Grunde um ein Forschungsprogramm): Es gibt einige vorläufige Beweise dafür, dass die Grenze dessen, was mit dem Busy Beaver berechenbar ist Die Funktion ist ein Maß für die Komplexität des Algorithmus, wobei zwei Verweise darunter auf diese Richtung hindeuten. [1] [2] ungefähr können kleine TMs mit sehr wenigen Zuständen nicht "so viel" oder "so ausgefeiltes Verhalten" wie komplexere Algorithmen mit mehr Zuständen erreichen. Daher scheint die Berechnung auch eine tiefe Verbindung zu haben Komplexität von Kolmogorov . [3] Eine andere Betrachtungsweise ist, dass das, was über die Busy-Beaver-Funktion bekannt / berechenbar ist, auch eng mit dem Stand der Technik im automatisierten Theorem übereinstimmt beweisen, die (ähnlich wie der technologische Fortschritt) eine sich ständig weiterentwickelnde Grenze auf der Grundlage mathematischer und computerwissenschaftlicher Forschung darstellt.

[1] Problem mit vielbeschäftigten Bibern, ein neuer Jahrtausendangriff , van Heuveln et al

[2] Kleine Turingmaschinen und allgemeiner reger Biberwettbewerb , Michel

[3] Zur Laufzeit der kürzesten Probleme , Batfai

vzn
quelle