54
\$\begingroup\$

The function TREE(k) gives the length of the longest sequence of trees T1, T2, ... where each vertex is labelled with one of k colours, the tree Ti has at most i vertices, and no tree is a minor of any tree following it in the sequence.

TREE(1) = 1, with e.g. T1 = (1).

TREE(2) = 3: e.g. T1 = (1); T2 = (2)--(2); T3 = (2).

TREE(3) is a big big number. Even bigger than Graham's number. Your job is to output a number even bigger than it!

This is a so the goal is to write the shortest program in any language that deterministically outputs a number bigger than or equal to TREE(3) (to the stdout).

  • You aren't allowed to take input.
  • Your program must eventually terminate but you can assume the machine has infinite memory.
  • You might assume your language's number type can hold any finite value but need to explain how this exactly works in your language (ex: does a float have infinite precision?)
    • Infinities are not allowed as output.
    • Underflow of a number type throws an exception. It does not wrap around.
  • Because TREE(3) is such a complex number you can use the fast growing hierarchy approximation fϑ(Ωω ω)+1(3) as the number to beat.
  • You need to provide an explanation of why your number is so big and an ungolfed version of your code to check if your solution is valid (since there is no computer with enough memory to store TREE(3))

Note: None of the answers currently found here work.

Why is TREE(3) so big?

\$\endgroup\$
48
  • 10
    \$\begingroup\$ @StepHen not trivally. Getting to Tree(3) requires a whole new paradigm. \$\endgroup\$
    – PyRulez
    Aug 16 '17 at 18:58
  • 1
    \$\begingroup\$ relevant: codegolf.meta.stackexchange.com/questions/14057/… \$\endgroup\$
    – fejfo
    Oct 14 '17 at 6:08
  • 13
    \$\begingroup\$ TREE(3)+1 there I win \$\endgroup\$
    – hyper-neutrino
    Oct 14 '17 at 23:44
  • 1
    \$\begingroup\$ @KSmarts You do realize none of the answers there come close to TREE(3)? \$\endgroup\$ Oct 19 '17 at 23:53
  • 2
    \$\begingroup\$ @MDXF I'm gonna say no, because using INT_MAX is kinda a cheating (otherwise, print INT_MAX would insta win). In general, your output needs to be the same for any sufficiently large system. \$\endgroup\$
    – PyRulez
    Oct 26 '17 at 7:30
42
\$\begingroup\$

New Ruby, 135 bytes, >> Hψ(φ3(Ω+1))(9)

where H is the Hardy hierarchy, ψ is an extended version of Madore's OCF (will explain below) and φ is the Veblen function.

Try it 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: (using functions, not 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

Madore's extended OCF:

enter image description here

And (crudely) Veblen's phi function:

enter image description here

Explanation without ordinals:

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]

My program initiates k = 9, h = [[],9,9]. It then applies k = k*k and h = f(h,k) until h == 0 and outputs k.

Explanation with ordinals:

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]

ψ'(ω∙α) ≈ ψ(α), the ordinal collapsing function described in the image above.

My program more or less initiates k = 9 and h = Ω(↑9)9, then applies k ← k² and h ← h[k,h] until h = 1 and returns k.

And so if I did this right, [[],9,9] is way bigger than the Bachmann-Howard ordinal ψ(ΩΩΩ...), which is way bigger than ϑ(Ωωω)+1.

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

And if my analysis is correct, then we should have ψ'(ΩΩ∙x) ~= ψ*(ΩΩ∙x), where ψ* is the normal Madore's psi function. If this holds, then my ordinal is approximately ψ*(φ3(Ω+ω)).


Old Ruby, 309 bytes, Hψ'09)(9) (see revision history, besides the new one is way better)

\$\endgroup\$
36
  • 1
    \$\begingroup\$ I could only test my program for very few values, so do excuse me if I've made a mistake somewhere. \$\endgroup\$ Oct 20 '17 at 20:19
  • 1
    \$\begingroup\$ Bleh, slowly but surely trying to think my way through and fixing anything I see wrong. :-( So tedious. \$\endgroup\$ Oct 20 '17 at 22:26
  • 1
    \$\begingroup\$ Hmm... so $f_{ψ_0(ψ9(9))}(9)$ means we need at least the $ψ_9(9)$ th weakly inaccessible cardinal level of the fast growing hierarchy with base 9 to get larger than $TREE(3)$ \$\endgroup\$
    – Secret
    Oct 21 '17 at 8:54
  • 1
    \$\begingroup\$ @Secret No, I just wanted to overshoot by a bit, plus working out a closer value to TREE(3) would cost me more bytes to write out. And there are no inaccessible cardinals used here. \$\endgroup\$ Oct 21 '17 at 12:14
  • 1
    \$\begingroup\$ Golf nitpicks: You can definitely golf a.class!=Array, most idiomatic is !a.is_a? Array but shortest I can think of is a!=[*a]. And the methods can be converted into lambdas: f=->a,n=0,b=a{...}...f[x,y] to save some characters and maybe open up refactoring possibilities using them as first-class objects. \$\endgroup\$
    – histocrat
    Oct 24 '17 at 16:05
27
\$\begingroup\$

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

Thanks for help from H.PWiz, Laikoni and Ørjan Johansen for help golfing the code!

As suggested by HyperNeutrino, my program outputs TREE(3)+1, exactly (TREE is computable as it turns out).

T n c is a tree with label c and nodes n. c should be 1, 2, or 3.

l t is the number of nodes in a tree t.

t1 # t2 is true if t1 homeomorphically embeds into t2 (based on Definition 4.4 here), and false otherwise.

a n outputs a big list of trees. The exact list isn't important. The important property is that a n contains every tree up to n nodes, with nodes being labelled with 1, 2, or 3, and maybe some more trees as well (but those other trees will also be labelled with 1, 2, or 3). It is also guaranteed to output a finite list.

s n lists all sequences length n of trees, such that the reverse (since we build it backwards) of that sequence is valid. A sequence is valid if the nth element (where we start counting at 1) has at most n nodes, and no tree homeomorphically embeds into a later one.

main prints out the smallest n such that there is no valid sequences of length n.

Since TREE(3) is defined as the length of the longest valid sequence, TREE(3)+1 is the smallest n such that there are no valid sequences of length n, which is what my program outputs.

\$\endgroup\$
0
16
\$\begingroup\$

Python 2, 194 bytes, ~ Hψ(ΩΩΩ)(9)

where H is the Hardy hierarchy, and ψ is the ordinal collapsing function below the Bachmann-Howard ordinal defined by Pohlers.

Thanks to Jonathan Frech for -3 bytes.

def S(T):return 0if T==1else[S(T[0])]+T[1:]
def R(T):U=T[0];V=T[1:];exec"global B;B=T"*(T[-1]==0);return[S(B)]+V if U==1else[R(U)]*c+V if U else V
A=[[[1,1],1],0]
c=9
while A:A=R(A);c*=c
print c

Try it online!

Better spaced version:

def S(T):
  return 0 if T==1 else [S(T[0])]+T[1:]

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

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

Explanation:

This program implements a variant of the Buchholz hydra, using just labels of 0 and 1. Basically, at each step, we look at the first leaf node of the tree, and see if it is labelled with a 0 or a 1.

-If the leaf node is labelled with a 0, then we delete the leaf node, and then copy the tree starting from the parent of the leaf node c times, all of the copies connected to the grandparent of the leaf node.

-If the leaf node is labelled with a 1, then we search back towards the root until we reach an ancestor node labelled with a 0. Let S be the tree starting from that ancestor node. Let S' be S with the leaf node relabelled with 0. Replace the leaf node with S'.

We then repeat the process until we have nothing left but the root node.

This program differs from the normal Buchholz hydra procedure in two ways: First, after we do the above procedure, we recurse back up the tree, and do the label 0 copy procedure described above for each ancestor node of the original leaf node. This increases the size of the tree, so our procedure will take longer than the normal Buchholz hydra, and therefore lead to a bigger number in the end; however, it will still terminate because the ordinal associated with the new tree will still be less the the old tree. The other difference is, rather than start with c = 1 and increasing 1 each time, we start with c = 9 and square it each time, because why not.

The tree [[[1,1],1],0] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω), and so our resulting final number of about Hψ(ΩΩΩ)(9) will definitely exceed TREE(3).

\$\endgroup\$
7
  • \$\begingroup\$ Not so golfy my friend :-) \$\endgroup\$ Oct 25 '17 at 11:53
  • \$\begingroup\$ I know. I don't know how to reduce it further, at least not in Python. Maybe I can try to learn some Ruby. \$\endgroup\$
    – Deedlit
    Oct 25 '17 at 12:05
  • \$\begingroup\$ Is it possible to put R(T) all on one line? \$\endgroup\$ Oct 25 '17 at 20:47
  • \$\begingroup\$ @SimplyBeautifulArt Most likely yes (TIO link), though untested. \$\endgroup\$ Oct 27 '17 at 14:57
  • \$\begingroup\$ @JonathanFrech Thanks for your help! Unfortunately, when I tried your code it gave an error message "global B is not defined". I have no idea why this gives an error while the original code does not, so I don't know how to fix it. \$\endgroup\$
    – Deedlit
    Oct 31 '17 at 3:40
11
\$\begingroup\$

Javascript, 111 bytes, ~ \$f_{\psi(\Omega_\omega)}(6)\$

\$f\$ is the Fast-growing Hierarchy. \$ψ\$ is Buchholz's Psi. This entry, despite being 111 bytes, dominates all of the previous entries in both size and the amount of bytes (except for Loader's number).

Here is the code:

s=JSON.stringify;P=([y,z])=>y?JSON.parse((k=s([P(y),z])).replaceAll(s(z),k)):z;for(a=b=0;a=b++<9?[a,0]:P(a););b

Here is the same code expanded out:

function P([y,z]) {
  if (y==0) {
    return z
  } else {
    k = JSON.stringify([P(y),z])
    return JSON.parse(k.replaceAll(JSON.stringify(z),k))
  }
}

for(a=b=0;a=b++<9?[a,0]:P(a););
b;

I'm going to explain both the P function and the for loop.

The Predecessor Function

The inputs of the predecessor function are binary trees with zeroes as leaf nodes. Here are some examples of binary trees:

  • 0
  • [0,0]
  • [[0,[0,0]],[0,0]]
  • [[[[[0,0],0],[0,0]],[0,0]],[[0,[0,0]],[0,[0,0]]]]
  • [[[[[[[[[[0,0],0],0],0],0],0],0],0],0],0]

The Predecessor function is defined like this:

  • P([0,z])=z
  • P([x,y])=[P(x),y] but with all instances of y replaced with [P(x),y]
  • P(0) is left undefined

Right away, we can see 0 represents the number \$0\$, and [0,z] represents the structure \$z+1\$. Natural numbers can be represented as [0,[0,[0,...[0,0]...]]] with \$n+1\$ zeroes. For example, \$1 =\$ [0,0], \$2 =\$ [0,[0,0]], \$3 =\$ [0,[0,[0,0]]], and so on.

Now consider the string [1,n] where \$n>1\$.

P([1,n])=[0,n] but replace all instances of \$n\$ with [0,n] \$\to\$ [0,[0,n]]

Therefore, [1,n] corresponds to \$n+3\$, as P(P(P([1,n]))) = n

By this logic, [2,n] corresponds to \$n+7\$, [3,n] corresponds to \$n+15\$, and [n,n] would approximately correspond to \$2^n\$. Maybe [[0,n],n] corresponds to \$2^{n+1}\$?

Not so fast!

Consider the string [[0,n],n]. One would expect this to correspond to \$2^{n+1}\$, but it is much stronger. P([[0,n],n]) \$\to\$ [P([0,n]),n] = [n,n], but then the second step would be to replace all instances of n with the entire tree, or [n,n]. This makes P([[0,n],n])=[[n,n],[n,n]] rather than [n,[n,n]].

One would ask whether this would cause an infinite loop. Let's try P([[n,n],[n,n]]). If we let J = P([n,n]), we will get:

P([[n,n],[n,n]])=[J,[n,n]] but with all instances of [n,n] replaced with [J,[n,n]]

However, there are no instances of [n,n] within J, because J is strictly less than [n,n]. Therefore, P([[n,n],[n,n]])=[J,[J,[n,n]]]. This works for all J less than [n,n].

So this means [[0,n],n] corresponds to \$2^{2^n}\$. [[0,[0,n]],n] corresponds to \$2^{2^{2^{2^n}}}\$. And finally, [[n,n],n] corresponds to \$n \uparrow\uparrow n\$. Now it is time to bring in the Middle Growing Hierarchy.

Middle Growing Hierarchy

The Middle Growing Hierarchy is defined here: https://googology.wikia.org/wiki/Middle-growing_hierarchy

One can make an approximate distinction with the Middle Growing Hierarchy.

  • [0,n] corresponds to \$m(0,n) \sim n+1\$
  • [1,n] corresponds to \$m(2,n) \sim n+3\$
  • [2,n] corresponds to \$m(3,n) \sim n+7\$
  • [n,n] corresponds to \$m(n,n) \sim n+2^n\$ and \$m(ω,n)\$
  • [n,[n,n]] corresponds to \$m(n+1,n) \sim 2^{n+1}\$ (not \$m(ω+1,n)\$)
  • [[0,n],n] corresponds to \$m(ω+1,n) \sim 2^{2^n}\$
  • [[0,[0,n]],n] corresponds to \$m(ω+2,n) \sim 2^{2^{2^{2^n}}}\$
  • [[1,n],n] corresponds to \$m(ω+3,n) \sim 2^{2^{2^{2^{2^{2^{2^{2^n}}}}}}}\$
  • [[n,n],n] corresponds to \$m(ω2,n) \sim n \uparrow\uparrow n\$

One can see a correspondence with the left-hand side of the binary tree and the inner subscript of the Middle Growing Hierarchy. Let's continue the correspondence. I will omit the right hand side of the binary tree and the base of the Middle Growing Hierarchy.

  • [n,n] corresponds to \$ω_2\$
  • [0,[n,n]] corresponds to \$ω_2+1\$
  • [n,[n,n]] corresponds to \$ω_3\$
  • [[0,n],[n,n]] corresponds to \$ω_4\$
  • [[1,n],[n,n]] corresponds to \$ω_6\$
  • [[0,n],n] corresponds to \$ω^2\$

So it seems like there is a jump from [[n,n],n] to [[[0,n],n],n], similar to the jump from [n,n] to [[0,n],n]. But even this doesn't capture the power of this notation.

More Ordinal Comparison

  • [n,[[0,n],n]] corresponds to \$ω^2+ω\$
  • [[n,n],[[0,n],n]] corresponds to \$2\timesω^2\$
  • [[n,[n,n]],[[0,n],n]] corresponds to \$ω^3\$
  • [[[0,n],[n,n]],[[0,n],n]] corresponds to \$ω^4\$
  • [[[0,n],n],[[0,n],n]] corresponds to \$ω^ω\$

We're not even at [[0,[0,n]],n] yet, what is going on?

  • [[[0,n],n],[[[0,n],n],[[0,n],n]]] corresponds to \$2\timesω^ω\$
  • [[n,[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω+1}\$
  • [[[n,n],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_2}\$
  • [[n,[[n,n],[[0,n],n]]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_2+1}\$
  • [[[0,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω_3}\$
  • [[[n,[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω^2}\$
  • [[[[0,n],[n,n]],[[0,n],n]],[[[0,n],n],[[0,n],n]]] corresponds to \$ω^{ω^3}\$
  • [[0,[0,n]],n] corresponds to \$ω^{ω^ω}\$

Where does the strength comes from? The strength lies in the fact that the binary tree notation corresponds to performing the Middle Growing Hierarchy on ordinals! Here are some examples:

  • [n,n] corresponds to \$m(ω,n)=n+2^n\$, so [n,n] as an ordinal corresponds to \$ω+2^ω=ω_2\$
  • [[0,n],n] corresponds to \$m(ω+1,n)=2^{n+2^n}\$, so [[0,n],n] as an ordinal corresponds to \$2^{ω+2^ω}=2^{ω_2}=ω^2\$
  • [[[0,n],n],[[0,n],n]] corresponds to \$m(ω,m(ω+1,n))=2^{2^{n+2^n}}\$, so [[[0,n],n],[[0,n],n]] as an ordinal corresponds to \$2^{2^{ω+2^ω}}=ω^ω\$
  • [[0,[0,n]],n] corresponds to \$m(ω+2,n)=2^{2^{2^{n+2^n}}}\$, so [[0,[0,n]],n] as an ordinal corresponds to \$2^{2^{2^{ω+2^ω}}}=ω^{ω^ω}\$

As it turns out, this pattern continues. I'm not going to go through the full analysis, but here are some more ordinal values. Remember that these are ordinals, not functions!

  • [[1,n],n] corresponds to \$ω^{ω^{ω^{ω^{ω^{ω^ω}}}}}\$
  • [[n,n],n] corresponds to \$ε_0\$
  • [[n,[n,n]],n] corresponds to \$ζ_0\$
  • [[[0,n],n],n] corresponds to \$φ(ω,0)\$
  • [[[n,n],n],n] corresponds to the BHO

Speed of Notation

Essentially, if a structure \$K\$ corresponds to \$g_a (n)\$ in the slow-growing hierarchy, then the structure [K,n] corresponds to \$m_a (n)\$ in the middle-growing hierarchy. This makes the limit [[[...,n],n],n], which corresponds to the first SGH-MGH catching point, of \$ψ(Ω_ω)\$. For comparison, \$\text{TREE}(n)\$ only corresponds to the ordinal \$ψ(Ω^{Ω^ω})\$, much much smaller. The premise of this notation is essentially nested Goodstein sequences, except it works!

The Middle Growing Hierarchy corresponds closely to the Fast Growing Hierarchy, this is why I put in \$f_{ψ(Ω_ω)}\$ as it is a catching point.

Actual Value of the program

Now that we have gone through the Predecessor function, and how it corresponds to numbers, functions, and ordinals, it is time to return to the value of this program.

To extract a value from a binary tree, such as [[[0,0],0],0], one would have to repeatedly apply the predecessor function until the value crashes down to 0. As we seen before, one would have to apply the predecessor function a massive amount of time, on the order of \$m(ψ(Ω_ω),x)\$

Just to let you know, [[[...,0],0],0] is not degenerate, unlike stuff like \$2 \uparrow\uparrow...\uparrow\uparrow2 = 4\$ in arrow notation. [[[...,0],0],0] will produce a massive number.

Here is the code again:

for(a=b=0;a=b++<9?[a,0]:P(a););b;

First, it sets a and b equal to 0. Then, it starts incrementing b. If b is less than 9, then it sets a to [a,0]. This means at b=9, a would had been already [[[[[[[[[0,0],0],0],0],0],0],0],0],0], which corresponds to a massive number. Then, the predecessor function gets repeatedly applied to a, increasing b by 1 for each application. Eventually, a is going to crash down to 0, but b will be some value far, far greater than \$\text{TREE}(3)\$, or \$\text{TREE}(\text{TREE}(...\text{TREE}(3)...))\$ with \$\text{TREE}(3)\$ nests. Finally, the program returns b.

So what?

One of the best thing about this program is how the notation enumerates the catching points between the SGH and the MGH. This program only reaches the very first catching point, but by a few simple extension, this program is able to formalize a meameamealokkapoowa oompa, surpass Strong Array Notation, and beat every single Ordinal Collapsing Function ever devised. \$ψ(Ω_ω)\$ is still a pathetically small value...

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to the site, and impressive first answer! I've edited in some formatting and Mathjax to make the answer more readable. Feel free to revert or edit anything I've gotten wrong, or that you don't like, and don't hesitate to ping me (using @cairdcoinheringaahing) if you need any help/tips on editing/formatting \$\endgroup\$ Feb 21 at 18:47
  • \$\begingroup\$ This is amazing, getting way higher than BHO this fast is incredible. \$\endgroup\$
    – nph
    Sep 18 at 21:34
  • \$\begingroup\$ Also, you claim that with some simple extentions, this can go much higher. What extentions are these? \$\endgroup\$
    – nph
    Sep 18 at 22:12
7
\$\begingroup\$

Julia, 569 bytes, Loader's Number

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

To save myself a bit of legwork, I decided to port Loader.c to Julia nearly one-for-one and compact it into the block of code above. For those that want to do the comparisons themselves (either to verify my scoring or to help me find mistakes or improve my code), an ungolfed version is below:

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

No previous counts because I made way too many byte miscounts in the aggressive golfing I've done.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Oh dear. 1 more addition to this madness of a place. \$\endgroup\$ Nov 10 '17 at 2:09
  • 1
    \$\begingroup\$ Also, while I've no proof of this, I think that D(D(D(D(99)))) is large enough. :| Maybe D(D(D(99))) is large enough. \$\endgroup\$ Nov 10 '17 at 2:11
  • 1
    \$\begingroup\$ If anyone wants to help me here, the next logical plan of attack is to generate a macro to compact "(x=¬x)%2!=0" into a single-letter macro. Can't figure out Julia macros myself, so someone else could be of use here. \$\endgroup\$ Dec 4 '17 at 3:32
6
+50
\$\begingroup\$

Ruby, 140 bytes, ~ Hψ(ΩΩΩ)(81)

where H is the Hardy hierarchy, and ψ is the standard ordinal collapsing function below the Bachmann-Howard ordinal, as defined here.

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

Try it online!

Ungolfed version:

def S(a)
  *v, u = a
  if a == 1 
    return []
  else
    return v + [S(u)]
  end
end  

def R(t)
  *v, u = t
  if t[0] == []
    $b = t
  end
  if u == 1
    return v + [S($b)]
  elsif u == []
    return v
  else
    return v + [R(u)]*$c
  end
end

$c = 9

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

while a != [] do
  $c *= 9
  a = R(a)
end

print $c

This program implements the Buchholz hydra with nodes labelled with []'s and 1's, as described in my Python 2 entry.

The tree [[],[1,[1,1]]] corresponds to the ordinal ψ(ΩΩΩ), which is considerably bigger than the ordinal ϑ(Ωωω) = ψ(ΩΩωω), and so our resulting final number of about Hψ(ΩΩΩ)(81) will exceed TREE(3).

\$\endgroup\$
13
  • \$\begingroup\$ Dang it you and your 149 bytes. \$\endgroup\$ Nov 1 '17 at 22:59
  • \$\begingroup\$ But Ruby for the win :P \$\endgroup\$ Nov 1 '17 at 23:04
  • \$\begingroup\$ Golf nitpick: Rather than writing u==0?v:u==[]?v you could write u==0?||u[0]?v, which saves two bytes. \$\endgroup\$ Nov 7 '17 at 11:43
  • \$\begingroup\$ @SimplyBeautifulArt Thanks for the help! Balls back in your court. :D \$\endgroup\$
    – Deedlit
    Nov 7 '17 at 13:11
  • 2
    \$\begingroup\$ D:< that 1 byte difference between us is the most frustrating thing ever. \$\endgroup\$ Nov 9 '17 at 12:24
4
\$\begingroup\$

JavaScript, 190 bytes, Hψ(εΩ+1)(9)Based off of this analysis

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

This program is a modified version of this 225B Pair-sequence number translation in JavaScript. For Pair-sequence number and their original code, see here.

The modifications done:

  • It is in JavaScript instead of BASIC.
  • No iteration(fψ(Ωω+1)->fψ(Ωω))
  • The sequence is (0,0)(1,1)(2,2), which corresponds to ordinal ψ(εΩ+1).This is in Hardy-hierarchy ordinal
\$\endgroup\$
4
\$\begingroup\$

Python, 359 (184 without whitespace) 224 212 bytes, ~$$H_{ψ(ψ_Ι(0))[7]}(8)$$

*S,n=0,2,9
while S:
 i=r=d=0
 for a in S[::-1]:
  i-=1
  if d<S[-1]-a:
   r=r or i;d+=S[-1]-a-d>1
   if[k+d for k in S[i:]]<S[r:]:break
   p=i+1
 S.pop();n*=n
 if r:S=S[:p]+[d*i+k for i in range(n)for k in S[p:]]

I'm new to codegolf so I'm not sure if all the whitespace here counts. If not, this entry isn't the shortest entry, but vastly dominates patcail's entry in size. The code here implements Sudden Sequence System (definition here), which is known to have a perfect correspondence to ordinals below $$\psi(\psi_I(0))$$ represented in Extended Weak Buchholz function. The original idea uses sequences lexicographically less than (0,2) to represent ordinals, but to save characters the sequence itself is reversed. There are actually a few open problems here that we don't know the answer to, but strongly suspect they are true:

  1. Does the limit of Extended Weak Buchholz function equal to limit of Extended Buchholz function?
  2. Is Sudden Sequence System terminating?
  3. Does the correspondence between the two systems hold?

Edit 1: It's broken due to a silly mistake. Now S is correctly initialized. Thanks to Naruyoko for a few great optimizations.

Edit 2: Optimized a bit

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Hi, welcome to code golf. Nice answer, looks good (I'm not on the laptop to test it out). Take your time reading the Welcome to Code golf if you haven't done so already. Btw, replace spaces with tabs to get shorter. There is also a Python tips page here, you could read it too, if you're interested. \$\endgroup\$
    – math
    Jul 27 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.