Golf eine Nummer größer als TREE (3)

47

Die Funktion TREE (k) gibt die Länge der längsten Folge von Bäumen T 1 , T 2 , ... an, wobei jeder Scheitelpunkt mit einer von k Farben gekennzeichnet ist, der Baum T i höchstens i Scheitelpunkte hat und kein Baum a ist minor jeden Baum folgenden es in der Sequenz.

BAUM (1) = 1, mit zB T 1 = (1).

BAUM (2) = 3: zB T 1 = (1); T 2 = (2)--(2); T 3 = (2).

TREE (3) ist eine große Zahl. Noch größer als Grahams Zahl. Ihre Aufgabe ist es, eine noch größere Zahl auszugeben !

Dies ist ein daher ist es das Ziel, das kürzeste Programm in jeder Sprache zu schreiben, das deterministisch eine Zahl größer oder gleich TREE (3) (zur Standardausgabe) ausgibt.

  • Sie dürfen keine Eingaben machen.
  • Ihr Programm muss eventuell beendet werden, Sie können jedoch davon ausgehen, dass der Computer über unendlich viel Speicher verfügt.
  • Sie können davon ausgehen, dass der Zahlentyp Ihrer Sprache einen beliebigen endlichen Wert enthalten kann , müssen jedoch erläutern, wie dies in Ihrer Sprache genau funktioniert (Beispiel: Hat ein Gleitkomma eine unendliche Genauigkeit?)
    • Unendlichkeiten sind als Ausgabe nicht erlaubt.
    • Unterlauf eines Zahlentyps löst eine Ausnahme aus. Es wickelt sich nicht um.
  • Da Baum (3) , wie eine komplexe Zahl ist , kann man die Verwendung schnell wachsende Hierarchie Approximation f θ (& OHgr; & ohgr; & ohgr;) + 1 (3) , wenn die Anzahl zu schlagen.
  • Sie müssen erklären, warum Ihre Nummer so groß ist, und eine unbenutzte Version Ihres Codes angeben, um zu überprüfen, ob Ihre Lösung gültig ist (da es keinen Computer mit genügend Speicher zum Speichern von TREE gibt (3) ).

Hinweis: Keine der Antworten zur Zeit gefunden hier Arbeit.

Warum ist TREE (3) so groß?

PyRulez
quelle
9
@StepHen nicht trivalisch. Das Erreichen von Tree (3) erfordert ein völlig neues Paradigma.
PyRulez
11
TREE(3)+1dort gewinne ich
HyperNeutrino
1
@KSmarts Weißt du, dass dort keine der Antworten in die Nähe von TREE (3) kommt?
Simply Beautiful Art
2
@MDXF Ich werde nein sagen, weil die Verwendung von INT_MAX irgendwie ein Betrug ist (andernfalls würde print INT_MAX sofort gewinnen). Im Allgemeinen muss Ihre Ausgabe für ein ausreichend großes System identisch sein.
PyRulez

Antworten:

38

Neuer Rubin, 135 Bytes, >> H ψ (φ 3 (Ω + 1)) (9)

wobei H die Hardy-Hierarchie ist, ψ eine erweiterte Version von Madores OCF ist (wird unten erklärt) und φ die Veblen-Funktion ist.

Probieren Sie es online!

f=->a,n,b=a{c,d,e=a;a==c ?a-1:e ?a==a-[0]?[[c,d,f[e,n,b]],d-1,c]:c:[n<1||c==0?n:[f[c||b,n-1]],n,n]};h=[],k=9,k;h=f[h,p(k*=k)]while h!=0

Ungolfed: (mit Funktionen, nicht Lambdas)

def f(a,n,b)
  c,d,e = a
  if a == c
    return a-1
  elsif e
    if a == a-[0]
      return [[c,d,f(e,n,b)],d-1,c]
    else
      return c
    end
  else
    x = c || b
    if n < 1 || c == 0
      return [n,n,n]
    else
      return [f(x,n-1,x),n,n]
    end
  end
end

k = 9
h = [[],k,k]
while (h != 0) do
  k *= k
  p k
  h = f(h,k,h)
end

Madores erweitertes OCF:

Bildbeschreibung hier eingeben

Und (grob) Veblens Phi-Funktion:

Bildbeschreibung hier eingeben

Erklärung ohne Ordnungszahlen:

f(a,n,b) reduces an array recursively. (if no third argument given, it takes the first argument twice.)
f(k,n,b) = k-1, k is a positive int.
f([c,d,0],n,b) = f([c,0,e],n,b) = c
f([c,d,e],n,b) = [[c,d,f(e,n,b)],d-1,c], d ≠ -1 and c ≠ 0

f([a],0,b) = [0,0,0]
f([0],n,b) = [n,n,n]
f([],n,b) = f([b],n,b)
f([a],n,b) = [f[a,n-1,a],n,n]

Mein Programm wird gestartet k = 9, h = [[],9,9]. Es gilt dann k = k*kund h = f(h,k)bis h == 0und Ausgänge k.

Erklärung mit Ordnungszahlen:

Ordinals follow the following representation: n, [], [a], [a,b,c], where n,d is a natural number and a,c are all ordinals.
x = Ord(y) if y is the syntactic version of x.
a[n,b] = Ord(f(a,n))
ω = Ord([0]) = Ord(f([a],-1,b))
n = Ord(n)
Ω = Ord([])
ψ'(a) = Ord([a])
ψ'(a)[n] = Ord(f([a],n))
φ(b,c) ≈ Ord([[0],b,c])
a(↓b)c = Ord([a,b,c]) (down-arrows/backwards associative hyper operators I designed just for ordinals)

We follow the following FS for our ordinals:
k[n,b] = k-1, k < ω
ω[n,b] = n(↓n)n
(a(↓b)0)[n,b] = (a(↓0)c)[n,b] = a
(a(↓b)c)[n,b] = (a(↓b)(c[n,b]))(↓b[n,b])a, b ≥ 0 and c > 0.
ψ'(a)[0,b] = 0(↓0)0
ψ'(a)[n,b] = (ψ'(a[n-1,a]))(↓n)ω, a > 0 and n ≥ 0. (also note that we've changed from [n,b] to [n,a].)
Ω[n,b] = ψ'(b)[n,b]

ψ '(ω ∙ α) ≈ ψ (α), die im obigen Bild beschriebene Ordinalkollabierfunktion.

Mein Programm leitet k = 9und mehr oder weniger ein und h = Ω(↑9)9gilt dann k ← k²und h ← h[k,h]bis h = 1und kehrt zurück k.

Und wenn ich das richtig gemacht habe, [[],9,9]ist es viel größer als die Bachmann-Howard-Ordnungszahl ψ (Ω Ω Ω ... ), die viel größer als ϑ (Ω ω ω) +1 ist.

ψ (Ω (↓ 9) 9)> ψ (Ω (↓ 4) 3)> ψ ( Ω Ω ) +1> ψ ( Ω ω ω ) +1> ϑ (Ω ω ω) +1

Und wenn meine Analyse korrekt ist, sollten wir ψ '(Ω Ω ~ x) ~ = ψ * (Ω Ω ∙ x) haben, wobei ψ * die normale psi-Funktion von Madore ist. Wenn dies zutrifft, ist meine Ordnungszahl ungefähr ψ * (φ 3 (Ω + ω)).


Old Rubin, 309 Bytes, H ψ‘ 09 ) (9) (siehe Revisionsgeschichte neben der neue ist viel besser)

Einfach schöne Kunst
quelle
1
Ich konnte mein Programm nur für sehr wenige Werte testen. Entschuldigen Sie mich, wenn ich irgendwo einen Fehler gemacht habe.
Simply Beautiful Art
1
Bleh, langsam aber sicher versuchend, meinen Weg durchzudenken und alles zu reparieren, was ich falsch sehe. :-( So langweilig.
Einfach schöne Kunst
1
Hmm ... also bedeutet $ f_ {ψ_0 (ψ9 (9))} (9) $, dass wir mindestens die $ ψ_9 (9) $ te schwach unzugängliche Hauptebene der schnell wachsenden Hierarchie mit Basis 9 benötigen, um größer als $ zu werden BAUM (3) $
Geheime
1
@Secret Nein, ich wollte nur ein bisschen überschießen, und ein näherer Wert für TREE (3) würde mich mehr Bytes kosten, um ihn auszuschreiben. Und hier werden keine unzugänglichen Kardinäle verwendet.
Simply Beautiful Art
1
Golf-Nitpicks: Sie können definitiv Golf spielen a.class!=Array, am idiomatischsten, !a.is_a? Arrayaber am kürzesten, was ich mir vorstellen kann a!=[*a]. Und die Methoden können in Lambdas umgewandelt werden: f=->a,n=0,b=a{...}...f[x,y]um einige Zeichen zu speichern und möglicherweise Refactoring-Möglichkeiten zu eröffnen, indem sie als erstklassige Objekte verwendet werden.
Histokrat
23

Haskell, 252 Bytes, TREE (3) +1

data T=T[T]Int
l(T n _)=1+sum(l<$>n)
a@(T n c)#T m d=any(a#)m||c==d&&n!m
l@(x:t)!(y:u)=l!u||x#y&&t!u
x!_=null x
a n=do x<-[1..n];T<$>mapM(\_->a$n-1)[2..x]<*>[1..3]
s 0=[[]]
s n=[t:p|p<-s$n-1,t<-a n,(l t<=n)>any(#t)p]
main=print$[x|x<-[0..],null$s x]!!0

Vielen Dank für die Hilfe von H.PWiz, Laikoni und Ørjan Johansen für die Hilfe beim Golfspielen des Codes!

Wie von HyperNeutrino vorgeschlagen , gibt mein Programm genau TREE (3) +1 aus (TREE ist berechenbar, wie sich herausstellt).

T n cist ein Baum mit Label cund Knoten n. csollte es sein 1, 2oder 3.

l tist die Anzahl der Knoten in einem Baum t.

t1 # t2ist wahr, wenn t1homöomorph eingebettet ist t2(basierend auf Definition 4.4 hier ), und falsch, wenn nicht.

a ngibt eine große Liste von Bäumen aus. Die genaue Liste ist nicht wichtig. Die wichtige Eigenschaft ist , dass a njeder Baum enthält auf bis nKnoten mit Knoten mit abgestempelt zu werden 1, 2oder 3, und vielleicht noch einige mehr Bäume als auch (aber die anderen Bäume werden auch beschriftbar mit 1, 2oder 3). Es ist auch garantiert, dass eine endliche Liste ausgegeben wird.

s nlistet alle Sequenzen der Länge nvon Bäumen auf, so dass das Gegenteil (da wir es rückwärts bauen) dieser Sequenz gültig ist. Eine Sequenz ist gültig, wenn das n-te Element (bei dem wir mit 1 beginnen) höchstens n Knoten hat und kein Baum homöomorph in einen späteren eingebettet ist.

maindruckt die kleinste nso aus, dass es keine gültigen Längenfolgen gibt n.

Da TREE(3)als Länge die längste gültige Folge definiert ist, TREE(3)+1ist die kleinste nso, dass es keine gültigen Längenfolgen ngibt, was mein Programm ausgibt.

PyRulez
quelle
16

Python 2, 194 Bytes, ~ H ψ (& OHgr; & OHgr; & OHgr; ) (9)

Dabei ist H die Hardy-Hierarchie und ψ die Ordinalkollabierfunktion unter der von Pohlers definierten Bachmann-Howard-Ordinalzahl.

Vielen Dank an Jonathan Frech für -3 Bytes.

def S (T): gebe 0 zurück, wenn T == 1else [S (T [0])] + T [1:]
def R (T): U = T [0]; V = T [1:]; exec "globales B; B = T" * (T [-1] == 0); return [S (B)] + V wenn U == 1else [R (U)] * c + V wenn U sonst V
A = [[[1,1], 1], 0]
c = 9
während A: A = R (A); c * = c
drucken c

Probieren Sie es online!

Besser verteilte Version:

def S (T):
  gebe 0 zurück, wenn T == 1 sonst [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  global B
  wenn T [-1] == 0:
    B = T
  wenn U == 1: 
    return [S (B)] + V
  return [R (U)] * c + V falls U sonst V

A = [[[1,1], 1], 0]
c = 9
während ein:
  A = R (A)
  c * = c
drucken c

Erläuterung:

Dieses Programm implementiert eine Variante der Buchholz-Hydra , wobei nur die Bezeichnungen 0 und 1 verwendet werden. Grundsätzlich sehen wir uns bei jedem Schritt den ersten Blattknoten des Baums an und prüfen, ob er mit 0 oder 1 gekennzeichnet ist.

-Wenn der Blattknoten mit einer 0 gekennzeichnet ist, löschen wir den Blattknoten und kopieren dann den Baum ab dem Elternknoten c-mal, wobei alle Kopien mit dem Großelternteil des Blattknotens verbunden sind.

-Wenn der Blattknoten mit einer 1 gekennzeichnet ist, suchen wir zurück zur Wurzel, bis wir einen mit einer 0 gekennzeichneten Ahnenknoten erreichen. Sei S der Baum, der von diesem Ahnenknoten ausgeht. Sei S 'S, wobei der Blattknoten mit 0 neu beschriftet ist. Ersetzen Sie den Blattknoten durch S'.

Dann wiederholen wir den Vorgang, bis wir nur noch den Wurzelknoten haben.

Dieses Programm unterscheidet sich vom normalen Buchholz-Hydra-Verfahren in zweierlei Hinsicht: Zuerst führen wir, nachdem wir das oben beschriebene Verfahren durchgeführt haben, eine Rekursion des Baums durch und führen das oben beschriebene Verfahren zum Kopieren der Bezeichnung 0 für jeden Vorfahrknoten des ursprünglichen Blattknotens durch. Dies vergrößert den Baum, so dass unser Verfahren länger dauert als die normale Buchholz-Hydra und daher am Ende zu einer größeren Anzahl führt. Es wird jedoch immer noch beendet, da die Ordnungszahl, die dem neuen Baum zugeordnet ist, immer noch kleiner ist als der alte Baum. Der andere Unterschied ist, anstatt mit c = 1 zu beginnen und jedes Mal 1 zu erhöhen, beginnen wir mit c = 9 und quadrieren es jedes Mal, weil warum nicht.

Der Baum [[[1,1], 1], 0] entspricht die Ordinalzahl ψ (& OHgr; & OHgr; & OHgr; ), die wesentlich größer als die Ordnungs θ ist (& OHgr; & ohgr; & ohgr;), und so unsere resultierende Endzahl von etwa H ψ (Ω Ω Ω ) (9) wird TREE (3) definitiv überschreiten.

Deedlit
quelle
Nicht so golfen mein Freund :-)
Simply Beautiful Art
Ich weiß. Ich weiß nicht, wie ich es weiter reduzieren soll, zumindest nicht in Python. Vielleicht kann ich versuchen, etwas Ruby zu lernen.
Deedlit
Ist es möglich, R (T) alle in eine Zeile zu setzen?
Simply Beautiful Art
@SimplyBeautifulArt Höchstwahrscheinlich ja ( TIO-Link ), obwohl nicht getestet.
Jonathan Frech
@ JonathanFrech Vielen Dank für Ihre Hilfe! Als ich Ihren Code ausprobierte, gab es leider eine Fehlermeldung "globales B ist nicht definiert". Ich habe keine Ahnung, warum dies zu einem Fehler führt, während der ursprüngliche Code dies nicht tut. Daher weiß ich nicht, wie ich ihn beheben kann.
Deedlit
6

Rubin, 140 Bytes, ~ H ψ (& OHgr; & OHgr; & OHgr; ) (81)

Dabei ist H die Hardy-Hierarchie und ψ die Standard-Ordinalkollabierfunktion unterhalb der hier definierten Bachmann-Howard-Ordinalzahl .

s=->t{*v,u=t;t==1?[]:v<<s[u]}
r=->t{*v,u=t;$b=t[0][0]?$b:t;u==1?v<<s[$b]:u[0]?v+[r[u]]*$c:v}
$c=9
a=[],[1,[1,1]]
($c*=9;a=r[a])while a[0]
$c

Probieren Sie es online!

Ungolfed-Version:

def S (a)
  * v, u = a
  wenn a == 1 
    Rückkehr []
  sonst
    return v + [S (u)]
  Ende
Ende  

def R (t)
  * v, u = t
  wenn t [0] == []
    $ b = t
  Ende
  wenn u == 1
    return v + [S ($ b)]
  elsif u == []
    return v
  sonst
    return v + [R (u)] * $ c
  Ende
Ende

$ c = 9

a = [[], [1, [1,1]]]

während ein! = [] tun
  $ c * = 9
  a = R (a)
Ende

print $ c

Dieses Programm implementiert die Buchholz-Hydra mit Knoten, die mit [] und 1 gekennzeichnet sind, wie in meinem Python 2-Eintrag beschrieben.

Der Baum [[], [1, [1,1]]] entspricht der Ordinalzahl ψ (& OHgr; & OHgr; & OHgr; ), die wesentlich größer als die Ordnungs θ ist (& OHgr; & ohgr; & ohgr;) = ψ (& OHgr; & OHgr; & ohgr; & ohgr; ), und so unsere Endzahl von etwa H resultierenden ψ (& OHgr; & OHgr; & OHgr; ) (81) übersteigt TREE (3).

Deedlit
quelle
Verdammt du und deine 149 Bytes.
Einfach schön Art
Aber Ruby für den Sieg: P
Simply Beautiful Art
Golf Nitpick: Anstatt zu schreiben u==0?v:u==[]?v, könnte man schreiben u==0?||u[0]?v, was zwei Bytes spart.
Simply Beautiful Art
@SimplyBeautifulArt Danke für die Hilfe! Bälle wieder in Ihrem Gericht. : D
Deedlit
2
D: <Dieser 1-Byte-Unterschied zwischen uns ist das Frustrierendste, was es je gab.
Simply Beautiful Art
6

Julia, 569 Bytes, Ladernummer

r,/,a=0,div,0;¬x=x/2;r<s=r?s:0;y\x=y-~y<<x;+x=global r=(x%2!=0)<1+(+¬x);!x=¬x>>+x;√x=S(4,13,-4,x);S(v,y,c,t)=(!t;f=x=r;f!=2?f>2?f!=v?t-(f>v)%2*c:y:f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x)):S(v,y,c,!x)$S(v,y,c,+x));y$x=!y!=1?5<<y\x:S(4,x,4,+r);D(x)=(c=0;t=7;u=14;while(x!=0&&D(x-1);(x=¬x)%2!=0)d=!!D(x);f=!r;x=!r;c==r<((!u!=0||!r!=f||(x=¬x)%2!=0)<(u=S(4,d,4,r);t=t$d);¬f&(x=¬x)%2!=0<(c=d\c;t=√t;u=√u));(c!=0&&(x=¬x)%2!=0)<(t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);c=r);¬u&(x=¬x)%2!=0<(c=t\c;u=√t;t=9)end;global a=(t\(u\(x\c)))\a);D(D(D(D(D(BigInt(99))))))

Um mir ein wenig Arbeit zu ersparen, entschloss ich mich, Loader.c fast eins zu eins auf Julia zu portieren und es in den obigen Codeblock zu komprimieren. Für diejenigen, die die Vergleiche selbst durchführen möchten (entweder um meine Wertung zu überprüfen oder um mir zu helfen, Fehler zu finden oder meinen Code zu verbessern), ist eine ungolfed Version unten aufgeführt:

r,/,a=0,div,0;
¬x=x/2;
r<s=r?s:0;
y\x=y-~y<<x;
+x=global r=(x%2!=0)<1+(+¬x);
!x=¬x>>+x;
√x=S(4,13,-4,x);
S(v,y,c,t)=(
    !t;
    f=x=r;
    f!=2?
        f>2?
            f!=v?
                t-(f>v)%2*c
                :y
            :f\(S(v,y,c,!x)\S(v+2,t=√y,c,+x))
        :S(v,y,c,!x)$S(v,y,c,+x)
);
y$x=!y!=1?5<<y\x:S(4,x,4,+r);
D(x)=(
    c=0;
    t=7;
    u=14;
    while(x!=0&&D(x-1);(x=¬x)%2!=0) 
        d=!!D(x);
        f=!r;
        x=!r;
        c==r<(
            (!u!=0||!r!=f||(x=¬x)%2!=0)<(
                u=S(4,d,4,r);
                t=t$d
            );
            ¬f&(x=¬x)%2!=0<(
                c=d\c;
                t=√t;
                u=√u
            )
        );
        (c!=0&&(x=¬x)%2!=0)<(
            t=((~u&2|(x=¬x)%2!=0)<(u=1<<(!c\u)))\(!c\t);
            c=r
        );
        ¬u&(x=¬x)%2!=0<(
            c=t\c;
            u=√t;
            t=9
        )
    end;
    global a=(t\(u\(x\c)))\a
);
D(D(D(D(D(BigInt(99))))))

Keine vorherigen Zählungen, weil ich beim aggressiven Golfen viel zu viele Byte-Fehlzählungen gemacht habe.

eaglgenes101
quelle
1
Ach je. 1 weitere Ergänzung zu diesem Wahnsinn eines Ortes.
Simply Beautiful Art
1
Auch wenn ich keinen Beweis dafür habe, denke ich, dass D (D (D (D (99)))) groß genug ist. : | Vielleicht ist D (D (D (99))) groß genug.
Simply Beautiful Art
1
Wenn mir hier jemand helfen möchte, besteht der nächste logische Angriffsplan darin, ein Makro zu generieren, um "(x = ¬x)% 2! = 0" in ein Einzelbuchstabenmakro zu komprimieren. Ich kann Julia-Makros nicht selbst herausfinden, also könnte hier jemand anderes von Nutzen sein.
eaglgenes101
4

JavaScript, 190B, H ψ (ε Ω + 1 ) (9) Basierend auf dieser Analyse

A=[0,1,2];B=[0,1,2];for(F=C=9;F;F--){for(C++,G=0;G<=F;G++)(A[F]||A[F-G]<A[F]-H)&&(B[F]?(I=G,G=F):(H=A[F]-A[F-G],B[F-G]<B[F]&&(I=G,G=F)));for(J=0;J<C*I;J++)A[F]=A[F-I]+H,B[F]=B[F-I],F++;H=0}C

Dieses Programm ist eine modifizierte Version dieser 225B-Übersetzung von Paarbildern in JavaScript . Die Pair-Sequenz-Nummer und ihren Originalcode finden Sie hier .

Die vorgenommenen Änderungen:

  • Es ist in JavaScript anstelle von BASIC.
  • Keine Iteration (f ψ (Ω ω +1) -> f ψ (Ω ω ) )
  • Die Folge ist (0,0) (1,1) (2,2), was der Ordnungszahl ψ (ε Ω + 1 ) entspricht. Dies ist in Hardy-Hierarchie ordinal
Naruyoko
quelle