Golf un nombre plus grand que TREE (3)

47

La fonction TREE (k) donne la longueur de la plus longue séquence d'arbres T 1 , T 2 , ... où chaque sommet est étiqueté avec l'une des k couleurs, l'arbre T i a au plus i sommets et aucun arbre n'est un mineur de n'importe quel arbre le suivant dans la séquence.

TREE (1) = 1, avec par exemple T 1 = (1).

TREE (2) = 3: par exemple, T 1 = (1); T 2 = (2)--(2); T 3 = (2).

TREE (3) est un grand nombre. Même plus grand que le nombre de Graham. Votre travail consiste à produire un nombre encore plus grand que celui-ci!

Comme il s'agit d'un , l'objectif est d'écrire le programme le plus court, quelle que soit la langue, qui génère de manière déterministe un nombre supérieur ou égal à TREE (3) (sur la sortie standard).

  • Vous n'êtes pas autorisé à prendre des entrées.
  • Votre programme doit éventuellement se terminer, mais vous pouvez supposer que la machine a une mémoire infinie.
  • Vous pouvez supposer que le type de numéro de votre langue peut contenir n'importe quelle valeur finie, mais vous devez expliquer comment cela fonctionne exactement dans votre langue (par exemple, un float a-t-il une précision infinie?)
    • Les infinis ne sont pas autorisés en sortie.
    • Le dépassement d'un type de nombre lève une exception. Ça ne s'enroule pas.
  • Parce que TREE (3) est un nombre complexe, vous pouvez utiliser l' approximation à hiérarchie croissante f ϑ (Ω ω ω) +1 (3) comme nombre à battre.
  • Vous devez expliquer pourquoi votre nombre est si grand et une version non codée de votre code pour vérifier si votre solution est valide (car aucun ordinateur ne dispose de suffisamment de mémoire pour stocker TREE (3) ).

Remarque: Aucune des réponses actuellement trouvées ici ne fonctionne.

Pourquoi TREE (3) est-il si gros?

PyRulez
la source
9
@StepHen pas trivialement. Se rendre à Tree (3) nécessite un tout nouveau paradigme.
PyRulez
11
TREE(3)+1là je gagne
HyperNeutrino
1
@KSmarts Vous vous rendez compte qu'aucune des réponses ne se rapproche de TREE (3)?
Simply Beautiful Art
2
@MDXF Je vais dire non, car utiliser INT_MAX est un peu une tricherie (sinon, imprimer INT_MAX gagnerait à gagner). En général, votre sortie doit être la même pour tout système suffisamment grand.
PyRulez

Réponses:

38

Nouveau Ruby, 135 octets, >> H ( 3 (Ω + 1)) (9)

H est la hiérarchie de Hardy, ψ est une version étendue de l'OCF de Madore (nous l'expliquerons plus loin) et φ est la fonction de Veblen.

Essayez-le en ligne!

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: (en utilisant des fonctions, pas des 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

OCF étendu de Madore:

entrez la description de l'image ici

Et (grossièrement) la fonction phi de Veblen:

entrez la description de l'image ici

Explication sans ordinaux:

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]

Mon programme commence k = 9, h = [[],9,9]. Il s’applique ensuite k = k*ket h = f(h,k)jusqu’à h == 0et sorties k.

Explication avec des ordinaux:

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]

ψ '(ω ∙ α) (α), la fonction de compression ordinale décrite dans l'image ci-dessus.

Mon programme commence plus ou moins k = 9et h = Ω(↑9)9, puis s'applique k ← k²et h ← h[k,h]jusqu'à h = 1et revient k.

Et donc, si je l'ai bien fait, il [[],9,9]est bien plus gros que l'ordinal de Bachmann-Howard ψ (Ω Ω Ω ... ), ce qui est bien plus grand que (Ω ω ω) +1.

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

Et si mon analyse est correcte, alors nous devrions avoir '(Ω Ω ∙ x) ~ = ψ * (Ω Ω ∙ x), où * est la fonction psi de Madore normale. Si cela est vrai, alors mon ordinal est approximativement égal à ψ * ( 3 (Ω + ω)).


Old Ruby, 309 octets, H ψ ' 09 ) (9) (voir l' historique des révisions , de plus le nouveau est bien meilleur)

Tout simplement magnifique
la source
1
Je ne pouvais tester mon programme que pour très peu de valeurs, alors excusez-moi si j'ai commis une erreur quelque part.
Simply Beautiful Art
1
Bleh, essayant lentement mais sûrement de réfléchir et de réparer tout ce que je voyais de travers. :-( Si fastidieux.
Simply Beautiful Art
1
Hmm ... so $ f_ {ψ_0 (ψ9 (9))} (9) $ signifie que nous avons besoin d'au moins le niveau cardinal faiblement inaccessible de $ card_9 (9) de la hiérarchie en croissance rapide avec la base 9 pour dépasser le niveau de $ TREE (3) $
Secret
1
@Secret Non, je voulais juste dépasser un peu, car travailler plus près de TREE (3) me coûterait plus d'octets à écrire. Et il n'y a pas de cardinaux inaccessibles utilisés ici.
Simply Beautiful Art
1
Nitpicks Golf: Vous pouvez sans aucun doute le golf a.class!=Array, la plupart idiomatiques est , !a.is_a? Arraymais plus court que je peux penser est a!=[*a]. Et les méthodes peuvent être converties en lambdas: f=->a,n=0,b=a{...}...f[x,y]pour sauvegarder certains caractères et éventuellement ouvrir des possibilités de refactoring en les utilisant comme objets de première classe.
histocrat
23

Haskell, 252 octets, 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

Merci de l'aide de H.PWiz, Laikoni et Ørjan Johansen de nous aider à jouer au golf dans le code!

Comme suggéré par HyperNeutrino , mon programme génère les sorties TREE (3) +1, exactement (TREE est calculable à l’ avenir ).

T n cest un arbre avec une étiquette cet des noeuds n. cdevrait être 1, 2ou 3.

l test le nombre de nœuds dans un arbre t.

t1 # t2est vrai si t1incorpore homéomorphiquement dans t2(basé sur la définition 4.4 ici ), et faux sinon.

a naffiche une grande liste d’arbres. La liste exacte n'est pas importante. La propriété importante est que a ncontient tous les arbres jusqu'à nnœuds, avec des noeuds étant étiquetés avec 1, 2ou 3, et peut - être quelques arbres aussi bien (mais les autres arbres seront également marqués avec 1, 2ou 3). Il est également garanti de produire une liste finie.

s nliste toutes les séquences de longueur nd'arbre, de sorte que l'inverse (puisque nous le construisons à l'envers) de cette séquence soit valide. Une séquence est valide si le nième élément (où nous commençons à compter à 1) a au plus n nœuds et qu’aucun arbre ne s’intègre de manière homogène dans un autre.

mainimprime le plus petit de ntelle sorte qu'il n'y ait pas de séquence valide de longueur n.

Puisque TREE(3)est défini comme la longueur de la plus longue séquence valide, TREE(3)+1est la plus petite de nsorte qu'il n'y ait pas de séquence valide de longueur n, ce que mon programme génère.

PyRulez
la source
16

Python 2, 194 octets, ~ H Ω Ω ) (9)

H est la hiérarchie de Hardy et ψ est la fonction d'effondrement ordinale au-dessous de l'ordinal de Bachmann-Howard défini par Pohlers.

Merci à Jonathan Frech pour -3 octets.

def S (T): retourne 0 si T == 1else [S (T [0])] + T [1:]
def R (T): U = T [0]; V = T [1:]; exec "global B; B = T" * (T [-1] == 0); retourne [S (B)] + V si U == 1else [R (U)] * c + V si U sinon V
A = [[[1,1], 1], 0]
c = 9
tandis que A: A = R (A); c * = c
print c

Essayez-le en ligne!

Version mieux espacée:

def S (T):
  retourne 0 si T == 1 sinon [S (T [0])] + T [1:]

def R (T):
  U = T [0]
  V = T [1:]
  global B
  si T [-1] == 0:
    B = T
  si U == 1: 
    retourne [S (B)] + V
  retourne [R (U)] * c + V si U sinon V

A = [[[1,1], 1], 0]
c = 9
tandis que A:
  A = R (A)
  c * = c
print c

Explication:

Ce programme implémente une variante de l' hydre de Buchholz , en utilisant uniquement les étiquettes 0 et 1. En gros, à chaque étape, nous examinons le premier nœud feuille de l'arbre et voyons s'il est étiqueté avec un 0 ou un 1.

-Si le nœud feuille est étiqueté avec un 0, nous supprimons le nœud feuille, puis copions l’arborescence à partir du parent du nœud feuille c, toutes les copies connectées au grand-parent du nœud feuille.

-Si le nœud feuille est étiqueté avec un 1, alors nous cherchons en arrière vers la racine jusqu'à atteindre un nœud ancêtre étiqueté avec un 0. Soit S l'arborescence à partir de ce nœud ancêtre. Soit S 'avec le nœud feuille relabellé à 0. Remplacez le nœud feuille par S'.

Nous répétons ensuite le processus jusqu'à ce qu'il ne nous reste plus que le nœud racine.

Ce programme diffère de la procédure d'hydre normale de Buchholz de deux manières: Premièrement, après avoir exécuté la procédure ci-dessus, nous avons sauvegardé de nouveau l'arborescence et effectué la procédure de copie label 0 décrite ci-dessus pour chaque nœud ancêtre du nœud feuille d'origine. Cela augmente la taille de l'arbre, de sorte que notre procédure prendra plus de temps que l'hydre normale de Buchholz et conduira donc à un nombre plus important à la fin; cependant, il se terminera quand même car l'ordinal associé au nouvel arbre sera toujours moins l'ancien. L’autre différence est que, plutôt que de commencer par c = 1 et d’augmenter de 1 à chaque fois, nous commençons avec c = 9 et nous le corrigeons à chaque fois, car pourquoi pas.

L'arbre [[[1,1], 1], 0] correspond à l'ordinal ψ (Ω Ω Ω ), qui est considérablement plus grand que l'ordinal ϑ (Ω ω ω), et donc notre nombre final résultant d'environ H ψ (Ω Ω Ω ) (9) dépassera définitivement TREE (3).

Deedlit
la source
Pas si louche mon ami :-)
Simply Beautiful Art
Je connais. Je ne sais pas comment le réduire davantage, du moins pas en Python. Peut-être que je peux essayer d'apprendre un peu de Ruby.
Deedlit
Est-il possible de mettre R (T) sur une seule ligne?
Simply Beautiful Art
@SimplyBeautifulArt Très probablement oui ( lien TIO ), bien que non testé.
Jonathan Frech
@ JonathanFrech Merci pour votre aide! Malheureusement, lorsque j'ai essayé votre code, il a généré un message d'erreur "le global B n'est pas défini". Je ne sais pas pourquoi cela donne une erreur alors que le code d'origine ne le fait pas, alors je ne sais pas comment le réparer.
Deedlit
6

Ruby, 140 octets, ~ H Ω Ω ) (81)

H est la hiérarchie de Hardy et ψ est la fonction de fusion ordinale standard sous l'ordinal de Bachmann-Howard, telle que définie ici .

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

Essayez-le en ligne!

Version non-golfée:

def S (a)
  * v, u = a
  si a == 1 
    revenir []
  autre
    retourne v + [S (u)]
  fin
fin  

def R (t)
  * v, u = t
  si t [0] == []
    $ b = t
  fin
  si u == 1
    retourne v + [S ($ b)]
  elsif u == []
    retour v
  autre
    retourne v + [R (u)] * $ c
  fin
fin

$ c = 9

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

alors qu'un! = [] do
  $ c * = 9
  a = R (a)
fin

print $ c

Ce programme implémente l'hydre de Buchholz avec des nœuds étiquetés avec les symboles [] et 1, comme décrit dans mon entrée Python 2.

L'arbre [[], [1, [1,1]]] correspond à l'ordinal (Ω Ω Ω ), qui est considérablement plus grand que l'ordinal (Ω ω ω) = (Ω Ω ω ω ), et donc notre nombre final résultant d'environ H H Ω Ω ) (81) dépassera TREE (3).

Deedlit
la source
Dang il vous et vos 149 octets.
Tout simplement magnifique Art
Mais Ruby pour la victoire: P
Simply Beautiful Art
Golf nitpick: Plutôt que d’écrire, u==0?v:u==[]?vvous pouvez écrire u==0?||u[0]?v, ce qui économise deux octets.
Tout simplement magnifique Art
@SimplyBeautifulArt Merci pour l'aide! Les balles dans votre cour. : D
Deedlit
2
D: <cette différence d'un octet entre nous est la chose la plus frustrante de tous les temps.
Simply Beautiful Art
6

Julia, 569 octets, numéro du chargeur

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))))))

Pour me sauver un peu de travail, j'ai décidé de transférer Loader.c à Julia presque un pour un et de le compacter dans le bloc de code ci-dessus. Pour ceux qui veulent faire les comparaisons eux-mêmes (soit pour vérifier mes scores, soit pour m'aider à trouver des erreurs ou pour améliorer mon code), une version non golfée est ci-dessous:

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))))))

Aucun compte précédent, car j’ai fait trop d’erreurs sur les octets dans le jeu agressif que j’ai fait.

eaglgenes101
la source
1
Oh cher. Un ajout de plus à cette folie d'un lieu.
Simply Beautiful Art
1
De plus, bien que je n’aie aucune preuve de cela, je pense que D (D (D (D (D (99)))) est assez grand. : | Peut-être que D (D (D (99))) est assez grand.
Simply Beautiful Art
1
Si quelqu'un veut m'aider ici, le prochain plan d'attaque logique consiste à générer une macro pour compacter "(x = ¬x)% 2! = 0" en une macro à une lettre. Je ne peux pas comprendre les macros de Julia moi-même, alors quelqu'un d'autre pourrait être utile ici.
eaglgenes101
4

JavaScript, 190B, H ψ (ε Ω + 1 ) (9) Sur la base de cette 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

Ce programme est une version modifiée de cette traduction de numéro de séquence de paires 225B en JavaScript . Pour le numéro de séquence de paires et leur code d'origine, voir ici .

Les modifications effectuées:

  • C'est en JavaScript au lieu de BASIC.
  • Pas d'itération (f ψ (Ω ω +1) -> f ψ (Ω ω ) )
  • La séquence est (0,0) (1,1) (2,2), ce qui correspond à l'ordinal ψ (ε Ω + 1 ). Ceci est dans l'ordinal de Hardy-hiérarchie
Naruyoko
la source