Die Laver-Tabellen enthalten Beispiele für Programme, von denen nicht gezeigt wurde, dass sie im Standard-Axiomatiksystem der Mathematik ZFC enden, die jedoch enden, wenn man sehr große Kardinalaxiome annimmt.
Einführung
Die klassischen Laver-Tabellen sind die einzigartigen endlichen Algebren mit der zugrunde liegenden Menge und einer Operation , die die Identität befriedigtAn
{1,...,2n}
*
x * (y * z)=(x * y) * (x * z)
und wo x*1=x+1
für und wo .x<2n
2n*1=1
Weitere Informationen zu den klassischen Laver-Tischen finden Sie im Buch Braids and Self-Distributivity von Patrick Dehornoy.
Herausforderung
Was ist der kürzeste Code (in Bytes), der 1*32
in den klassischen Laver-Tabellen berechnet und genau dann endet, wenn er ein n
mit findet ? Mit anderen Worten, das Programm bricht genau dann ab, wenn es eine findet1*32<2n
n
mit findet , andernfalls jedoch für immer ausgeführt.1*32<2n
Motivation
Ein Rang-in-Rang- Kardinal (auch I3-Kardinal genannt) ist ein extrem hohes Maß an Unendlichkeit. Wenn man davon ausgeht, dass es einen Rang-in-Rang-Kardinal gibt, kann man mehr Theoreme beweisen, als wenn man es nicht tut nehme die Existenz eines Rang-in-Rang-Kardinals an. Wenn es einen Rang-in-Rang-Kardinal gibt, dann gibt es einen klassischen Laver-Tisch, an dem . Es ist jedoch kein Beweis dafür in ZFC bekannt. Weiterhin ist bekannt, dass der kleinste Wert größer ist als (was eine extrem große Zahl seit der Ackermann-Funktion istAn
1*32<2n
1*32<2n
n
1*32<2n
Ack(9,Ack(8,Ack(8,254)))
Ack
eine schnell wachsende Funktion ist). Daher wird ein solches Programm extrem lange dauern.
Ich möchte sehen, wie kurz ein Programm geschrieben werden kann, damit wir nicht wissen, ob das Programm mit dem Standard-Axiomatiksystem ZFC endet, aber wo wir wissen, dass das Programm schließlich mit einem viel stärkeren Axiomatiksystem, nämlich ZFC + I3, endet. Diese Frage wurde von Scott Aaronsons jüngstem Beitrag inspiriert in dem Aaronson und Adam Yedidia eine Turing-Maschine mit weniger als 8000 Zuständen konstruiert haben, so dass ZFC nicht beweisen kann, dass die Turing-Maschine nicht terminiert, sondern bekanntermaßen nicht terminiert, wenn man große Kardinalhypothesen annimmt.
Wie die klassischen Laver-Tische berechnet werden
Wenn Laver Tabellen Berechnung ist es in der Regel zweckmäßig , die Tatsache zu nutzen , dass in der Algebra , haben wir für alle inAn
2n * x=x
x
An
.
Der folgende Code berechnet die klassische Laver-Tabelle An
Tabelle # (n, x, y) zurückkehrt x * y in A N Tabelle: = Funktion (n, x, y) wenn x = 2 ^ n, dann gib y zurück; elif y = 1 dann gebe x + 1 zurück; sonst Rückgabetabelle (n, Tabelle (n, x, y-1), x + 1); fi; Ende;
Beispielsweise wird die Eingabe table(4,1,2)
zurückgegeben 12
.
Der Code für table(n,x,y)
ist ziemlich ineffizient und kann nur in angemessener Zeit in der Laver-Tabelle berechnet werden. Glücklicherweise gibt es viel schnellere Algorithmen zum Berechnen der klassischen Laver-Tabellen als die oben angegebenen.A4
quelle
Ack(9,Ack(8,Ack(8,254)))
eine Untergrenze für die erste Tabelle ist, in der die erste Zeile die Periode 32 hat, dh wo1*16 < 2^n
?table(n,x,y)
, und ich denke, es wird zwischen 25 und 30 Zustände dauern, um die Konstanten und die äußere Schleife einzurichten. Die einzige direkte TM-Darstellung, die ich auf esolangs.org finden kann, ist esolangs.org/wiki/ScripTur und es ist nicht wirklich so golfen.Antworten:
Binäre Lambda-Rechnung, 215 Bit (27 Byte)
kompiliert zu (mit Software unter https://github.com/tromp/AIT )
Diese Lösung ist hauptsächlich auf https://github.com/int-e zurückzuführen
quelle
CJam (
3632 Bytes)In der Praxis tritt dieser Fehler ziemlich schnell auf, weil er den Aufrufstapel überläuft, aber auf einem theoretisch unbegrenzten Rechner ist er korrekt, und ich verstehe, dass dies die Annahme dieser Frage ist.
ist nicht richtig, wenn wir berechnete Werte zwischenspeichern, um ein erneutes Berechnen zu vermeiden. Das ist der Ansatz, den ich mit dem
j
Operator (Merken) gewählt habe . Es testet A 6 in Millisekunden und überläuft den Stapel, der A 7 testet - und ich habe es tatsächlich optimierttable
im Interesse des Golfspiels .Präparation
Wenn wir davon ausgehen, dass dies
n
aus dem Kontext verstanden wird, stattWir können den ersten Sonderfall entfernen und geben
und es funktioniert immer noch, weil
und für jeden anderen
y
,also bekommen wir durch Induktion
f(2^n, y) = y
.Für CJam erweist es sich als praktischer, die Reihenfolge der Parameter umzukehren. Und anstatt den Bereich zu verwenden, verwende
1 .. 2^n
ich den Bereich,0 .. 2^n - 1
indem ich jeden Wert dekrementiere. Die rekursive Funktion, die ich implementiere, ist alsoquelle
Pyth, 33 Bytes
Probieren Sie es online! (Offensichtlich ist der Testteil hier nicht enthalten.)
quelle
fi
der Code?