Laver-Tabellenberechnungen und ein Algorithmus, von dem nicht bekannt ist, dass er in ZFC endet

12

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+1für und wo .x<2n2n*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*32in den klassischen Laver-Tabellen berechnet und genau dann endet, wenn er ein nmit findet ? Mit anderen Worten, das Programm bricht genau dann ab, wenn es eine findet1*32<2nn 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 istAn1*32<2n1*32<2nn1*32<2nAck(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 inAn2n * x=xxAn .

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

Joseph Van Name
quelle
1
Willkommen bei PPCG! Guter Eintrag!
NoOneIsHere
1
Laut Wikipedia ist Ack (9, Ack (8, Ack (8.254))) eine Untergrenze für n, für die die Periode 16 überschreitet. Dafür können wir 1 * 16 statt 1 * 32 prüfen. Ich werde mein Programm entsprechend anpassen.
John Tromp
1
Ich habe angefangen, eine Turing-Maschine zu schreiben, um dies zu tun, und ich glaube, ich habe einen Fehler entdeckt, der um den Faktor zwei geht. Hat Dougherty nicht bewiesen, dass dies 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 wo 1*16 < 2^n?
Peter Taylor
1
Wenn Sie eine 20-Staaten-2-Symbol-Maschine für Ackermann haben, geben Sie mir bitte einen Link, da ich wahrscheinlich einige Ideen daraus stehlen kann. Ich habe 44 Zustände zu berechnen 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.
Peter Taylor
1
cheddarmonk.org/papers/laver.pdf ist so viel, wie ich für diese Woche erwartet habe, weil ich auf Reisen bin.
Peter Taylor

Antworten:

3

Binäre Lambda-Rechnung, 215 Bit (27 Byte)

\io. let
  zero = \f\x. x;
  one = \x. x;
  two = \f\x. f (f x);
  sixteen = (\x. x x x) two;
  pred = \n\f\x. n (\g\h. h (g f)) (\h. x) (\x. x);
  laver = \mx.
    let laver = \b\a. a (\_. mx (b (laver (pred a))) zero) b
    in laver;
  sweet = sixteen;
  dblmin1 = \n\f\x. n f (n f (f x)); -- map n to 2*n-1
  go2 = \mx. laver mx sweet mx (\_. mx) (go2 (dblmin1 mx));
in go2 one

kompiliert zu (mit Software unter https://github.com/tromp/AIT )

000101000110100000010101010100011010000000010110000101111110011110010111
110111100000010101111100000011001110111100011000100000101100100010110101
00000011100111010100011001011101100000010111101100101111011001110100010

Diese Lösung ist hauptsächlich auf https://github.com/int-e zurückzuführen

John Tromp
quelle
2
Ich bin mir nicht sicher, wie Sie zu Ihrer Punktzahl gekommen sind, aber standardmäßig sollten Einsendungen nach der Anzahl der Bytes im Code bewertet werden. Ich zähle 375 Bytes für diese Einreichung. Sie sollten auch den Namen der Sprache und optional einen Link zu einem Dolmetscher für die Sprache angeben.
Alex A.
Sie sollten wahrscheinlich den genauen Code mit einer Länge von 234 Bit in Ihren Beitrag aufnehmen.
CalculatorFeline
2
Die Kodierung ist auf Wikipedia zu finden . Es gibt auch einen Link zu diesem Interpreter (nicht getestet). Diese sollten jedoch überprüft werden, und die Binärkodierung sollte auch im Beitrag enthalten sein.
PurkkaKoodari
Für kompilierte Sprachen bewerten wir den vom Benutzer geschriebenen Code - nicht die Anzahl der Bytes in der generierten Binärdatei.
Alex A.
4
@AlexA. Das ist nicht notwendig ... jede Form von Code, die ein Compiler oder Interpreter verstehen kann, ist in Ordnung.
Feersum
4

CJam ( 36 32 Bytes)

1{2*31TW$,(+a{0X$j@(@jj}2j)W$=}g

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.

Der Code für table(n,x,y)ist ziemlich ineffizient und kann in der Laver-Tabelle A 4 nur in angemessener Zeit berechnet werden.

ist nicht richtig, wenn wir berechnete Werte zwischenspeichern, um ein erneutes Berechnen zu vermeiden. Das ist der Ansatz, den ich mit dem jOperator (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 optimiert table im Interesse des Golfspiels .

Präparation

Wenn wir davon ausgehen, dass dies naus dem Kontext verstanden wird, statt

f(x,y) =
    x==2^n ? y :
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

Wir können den ersten Sonderfall entfernen und geben

f(x,y) =
    y==1 ? x+1 :
    f(f(x,y-1),x+1)

und es funktioniert immer noch, weil

f(2^n, 1) = 2^n + 1 = 1

und für jeden anderen y,

f(2^n, y) = f(f(2^n, y-1), 1) = f(2^n, y-1) + 1

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^nich den Bereich, 0 .. 2^n - 1indem ich jeden Wert dekrementiere. Die rekursive Funktion, die ich implementiere, ist also

g(y,x) =
    y==0 ? x+1
         : g(x+1, g(y-1, x))

1           e# Initial value of 2^n
{           e# do-while loop
  2*        e#   Double 2^n (i.e. increment n)
  31T       e#   table(n,1,32) is g(31,0) so push 31 0
  W$,(+a    e#   Set up a lookup table for g(0,x) = x+1 % 2^n
  {         e#   Memoisation function body: stack is 2^n ... y x
    0X$j    e#     Compute g(0,x) = x+1 % 2^n
            e#     Stack is 2^n ... y x (x+1%2^n)
    @(      e#     Bring y to top, decrement (guaranteed not to underflow)
            e#     Stack is 2^n ... x (x+1%2^n) (y-1%2^n)
    @jj     e#     Rotate and apply memoised function twice: g(x+1,g(y-1,x))
  }
  2j        e#   Memoise two-parameter function
            e#   Stack: 2^n g(31,0)
  )W$=      e#   Test whether g(31,0)+1 is 2^n
}g          e# Loop while true
Peter Taylor
quelle
1

Pyth, 33 Bytes

.N?qT^2NY?tY:N:NTtYhThT<:T1 32^2T

Probieren Sie es online! (Offensichtlich ist der Testteil hier nicht enthalten.)

Undichte Nonne
quelle
Welche Schleife? Und was bedeutet fider Code?
Undichte Nonne