16
\$\begingroup\$

Some of you may be familiar with the BigNum Bakeoff, which ended up quite interestingly. The goal can more or less be summarized as writing a C program who's output would be the largest, under some constraints and theoretical conditions e.g. a computer that could run the program.

In the same spirit, I'm posing a similar challenge open to all languages. The conditions are:

  • Maximum 512 bytes.

  • Final result must be printed to STDOUT. This is your score. If multiple integers are printed, they will be concatenated.

  • Output must be an integer. (Note: Infinity is not an integer.)

  • No built-in constants larger than 10, but numerals/digits are fine (e.g. Avogadro's constant (as a built-in constant) is invalid, but 10000 isn't.)

  • The program must terminate when provided sufficient resources to be run.

  • The printed output must be deterministic when provided sufficient resources to be run.

  • You are provided large enough integers or bigints for your program to run. For example, if your program requires applying basic operations to numbers smaller than 101,000,000, then you may assume the computer running this can handle numbers at least up to 101,000,000. (Note: Your program may also be run on a computer that handles numbers up to 102,000,000, so simply calling on the maximum integer the computer can handle will not result in deterministic results.)

  • You are provided enough computing power for your program to finish executing in under 5 seconds. (So don't worry if your program has been running for an hour on your computer and isn't going to finish anytime soon.)

  • No external resources, so don't think about importing that Ackermann function unless it's a built-in.

All magical items are being temporarily borrowed from a generous deity.

Extremely large with unknown limit

where B³F is the Church-Kleene ordinal with the fundamental sequence of

B³F[n] = B³F(n), the Busy Beaver BrainF*** variant
B³F[x] = x, ω ≤ x < B³F

Leaderboard:

  1. Simply Beautiful Art, Ruby fψ0(X(ΩM+X(ΩM+1ΩM+1)))+29(999)

  2. Binary198, Python 3 fψ0Ωω+1)+1(3) (there was previously an error but it was fixed)

  3. Steven H, Pyth fψ(ΩΩ)+ω²+183(25627!)

  4. Leaky Nun, Python 3 fε0(999)

  5. fejfo, Python 3 fωω6(fωω5(9e999))

  6. Steven H, Python 3 fωω+ω²(99999)

  7. Simply Beautiful Art, Ruby fω+35(9999)

  8. i.., Python 2, f3(f3(141))

Some side notes:

If we can't verify your score, we can't put it on the leaderboard. So you may want to expect explaining your program a bit.

Likewise, if you don't understand how large your number is, explain your program and we'll try to work it out.

If you use a Loader's number type of program, I'll place you in a separate category called "Extremely large with unknown limit", since Loader's number doesn't have a non-trivial upper bound in terms of the fast growing hierarchy for 'standard' fundamental sequences.

Numbers will be ranked via the fast-growing hierarchy.

For those who would like to learn how to use the fast growing hierarchy to approximate really large numbers, I'm hosting a Discord server just for that. There's also a chat room: Ordinality.

Similar challenges:

Largest Number Printable

Golf a number bigger than TREE(3)

Shortest terminating program whose output size exceeds Graham's number

For those who want to see some simple programs that output the fast growing hierarchy for small values, here they are:

Ruby: fast growing hierarchy

#f_0:
f=->n{n+=1}

#f_1:
f=->n{n.times{n+=1};n}

#f_2:
f=->n{n.times{n.times{n+=1}};n}

#f_3:
f=->n{n.times{n.times{n.times{n+=1}}};n}

#f_ω:
f=->n{eval("n.times{"*n+"n+=1"+"}"*n);n}

#f_(ω+1):
f=->n{n.times{eval("n.times{"*n+"n+=1"+"}"*n)};n}

#f_(ω+2):
f=->n{n.times{n.times{eval("n.times{"*n+"n+=1"+"}"*n)}};n}

#f_(ω+3):
f=->n{n.times{n.times{n.times{eval("n.times{"*n+"n+=1"+"}"*n)}}};n}

#f_(ω∙2) = f_(ω+ω):
f=->n{eval("n.times{"*n+"eval(\"n.times{\"*n+\"n+=1\"+\"}\"*n)"+"}"*n);n}

etc.

To go from f_x to f_(x+1), we add one loop of the n.times{...}.

Otherwise, we're diagonalizing against all the previous e.g.

f_ω(1) = f_1(1)
f_ω(2) = f_2(2)
f_ω(3) = f_3(3)

f_(ω+ω)(1) = f_(ω+1)(1)
f_(ω+ω)(2) = f_(ω+2)(2)
f_(ω+ω)(3) = f_(ω+3)(3)

etc.

\$\endgroup\$
10
  • \$\begingroup\$ Do numerals count as built-in constants? \$\endgroup\$
    – PyRulez
    Nov 24, 2017 at 22:34
  • 3
    \$\begingroup\$ @CloseVoters How can this be too broad... Well, asking the user to output one number in infinitely many numbers is not the same as asking the user to choose one of infinitely many tasks to do. To be fair this question ask the user to do the same thing too. 4 close votes as too broad already... \$\endgroup\$
    – DELETE_ME
    Nov 26, 2017 at 2:13
  • 1
    \$\begingroup\$ @Οurous Yes, you may assume that. But realize that when your program is given more resources, including faster computation, the output must still be deterministic. \$\endgroup\$ Dec 9, 2017 at 1:40
  • 1
    \$\begingroup\$ I stated in the other comment section why I think the bounded Brainfuck Busy Beaver function will be exponential, but I'd like to add that more generally, I don't think the Church-Kleene ordinal will be the appropriate level for any computer program. A function one can code with a program are computable, and so should fall into the provably recursive functions of some sufficiently strong recursive sound theory. That theory will have a recursive proof theoretic ordinal, and that function will be below that ordinal in the FGH, assuming reasonable fundamental sequences. \$\endgroup\$
    – Deedlit
    Dec 13, 2017 at 6:28
  • 1
    \$\begingroup\$ Of course the actual Busy Beaver function cannot be coded into program (hypercomputational languages aside), and restricted Busy Beaver functions that can be programmed must by necessity be much slower growing. \$\endgroup\$
    – Deedlit
    Dec 13, 2017 at 6:30

13 Answers 13

8
\$\begingroup\$

Ruby, fψ0(X(ΩM+X(ΩM+1ΩM+1)))+29(999)

where M is the first Mahlo 'ordinal', X is the chi function (Mahlo collapsing function), and ψ is the ordinal collapsing function.

f=->a,n,b=a,q=n{c,d,e=a;!c ?[q]:a==c ?a-1:e==0||e&&d==0?c:e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:n<1?9:!d ?[f[b,n-1],c]:c==0?n:[t=[f[c,n],d],n,c==-1?[]:d==0?n:[f[d,n,b,t]]]};(x=9**9**9).times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{x.times{h=[];x.times{h=[h,h,h]};h=[[-1,1,[h]]];h=f[h,p x*=x]until h!=0}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

Try it online!

Code Breakdown:

f=->a,n,b=a,q=n{          # Declare function
                c,d,e=a;          # If a is an integer, c=a and d,e=nil. If a is an array, a=[c,d,e].compact, and c,d,e will become nil if there aren't enough elements in a (e.g. a=[1] #=> c=1,d=e=nil).
                        !c ?[q]:          # If c is nil, return [q], else
                                a==c ?a-1:          # If a==c, return a-1, else
                                          e==0||e&&d==0?c:          # If e==0 or e is not nil and d==0, return c, else
                                                          e ?[[c,d,f[e,n,b,q]],f[d,n,b,q],c]:          # If e is not nil, return an array inside an array, else
                                                                                             n<1?9:          # If n<1, return 9, else
                                                                                                   !d ?[f[b,n-1],c]:          # If d is nil, return [f[b,n-1],c], else
                                                                                                                    c==0?n:          # If c==0, return n, else
                                                                                                                           [t=[f[c,n],d],n,c==-1?[]:d==0?n:[f[d,n,b,t]]]          # t=[f[c,n],d]. If c==-1, return [t,n,[]], else if d==0, return [t,n,n], else return [t,n,[f[d,n,b,t]]].
                                                                                                                                                                        };          # End of function
                                                                                                                                                                          (x=9**9**9)          # Declare x
                                                                                                                                                                                     x.times{...}          # Looped within 33 x.times{...} loops
                                                                                                                                                                                                 h=[];          # Declare h
                                                                                                                                                                                                      x.times{h=[h,h,h]};          # Nest h=[h,h,h] x times
                                                                                                                                                                                                                         h=f[h,p x*=x]          # Apply x*=x, print x, then h=f[h,x]
                                                                                                                                                                                                                                      until h==0          # Repeat previous line until h==0

Math Breakdown:

f reduces a based on n,b,q.

The basic idea is to have an extremely nested a and reduce it repeatedly until it reduces down to a=0. For simplicity, let

g[0,n]=n
g[a,n]=g[f[a,n],n+1]

For now, let's only worry about n.

For any integer k, we get f[k,n]=k-1, so we can see that

g[k,n]=n+k

We then have, for any d, f[[0,d],n]=n, so we can see that

g[[0,d],n]
= g[f[[0,d],n],n+1]
= g[n,n+1]
= n+n+1

We then have, for any c,d,e, f[[c,0,e],n]=f[[c,d,0],n]=c. For example,

g[[[0,d],0,e],n]
= g[f[[[0,d],0,e]],n+1]
= g[[0,d],n+1]
= (n+1)+(n+1)+1
= 2n+3

We then have, for any c,d,e such that it does not fall into the previous case, f[[c,d,e],n]=[[c,d,f[e,n]],f[d,n],e]. This is where it starts to get complicated. A few examples:

g[[[0,d],1,1],n]
= g[f[[[0,d],1,1],n],n+1]
= g[[[0,d],1,0],0,[0,d]],n+1]
= g[f[[[0,d],1,0],0,[0,d]],n+1],n+2]
= g[[[0,d],1,0],n+2]
= g[f[[[0,d],1,0],n+2],n+3]
= g[[0,d],n+3]
= (n+3)+(n+3)+1
= 2n+7

#=> Generally g[[[0,d],1,k],n] = 2n+4k+3

g[[[0,d],2,1],n]
= g[f[[[0,d],2,1],n],n+1]
= g[[[[0,d],2,0],1,[0,d]],n+1]
= g[f[[[[0,d],2,0],1,[0,d]],n+1],n+2]
= g[[[[[0,d],2,0],1,n+1],0,[[0,d],2,0]]],n+2]
= g[f[[[[[0,d],2,0],1,n+1],0,[[0,d],2,0]]],n+2],n+3]
= g[[[[0,d],2,0],1,n+1],n+3]
= ...
= g[[[0,d],2,0],3n+6]
= g[f[[[0,d],2,0],2n+6],3n+7]
= g[[0,d],3n+7]
= (3n+7)+(3n+7)+1
= 6n+15

It quickly ramps up from there. Some points of interest:

g[[[0,d],3,[0,d]],n] ≈ Ack(n,n), the Ackermann function
g[[[0,d],3,[[0,d],0,0]],63] ≈ Graham's number
g[[[0,d],5,[0,d]],n] ≈ G(2^^n), where 2^^n = n applications of 2^x, and G(x) is the length of the Goodstein sequence starting at x.

Eventually introducing more arguments of the f function as well as more cases for the array allows us to surpass most named computable notations. Some particularly known ones:

g[[[0],3,[0,d]],n] ≈ tree(n), the weak tree function
g[[[[0],3,[0,d]],2,[0,d]],n] ≈ TREE(n), the more well-known TREE function
g[[[[0,d]],5,[0,d]],n] >≈ SCG(n), sub-cubic graph numbers
g[[[0]],n] ≈ S(n), Chris Bird's S function
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Ordinal explanation? \$\endgroup\$ Dec 9, 2017 at 2:55
  • \$\begingroup\$ Is this your largest defined number yet? It appears so! \$\endgroup\$ Sep 28, 2019 at 3:47
  • \$\begingroup\$ This looks quite powerful, but can you prove your supposed growth rate of \$\psi_0(\chi(\Omega_{M+\chi(\Omega_{M+1}^{\Omega_{M+1}}))})+29\$? That seems quite high in my opinion. But I might be wrong, your program might actually be that strong! \$\endgroup\$
    – Binary198
    Nov 21, 2021 at 9:25
  • \$\begingroup\$ Also, which OCF are you using? The analysis seems ill-defined. \$\endgroup\$
    – Binary198
    Dec 11, 2021 at 15:19
3
\$\begingroup\$

Pyth, fψ(ΩΩ)+ω2+183(~25627!)

=QC`.pGL&=^QQ?+Ibt]0?htb?eb[Xb2yeby@b1hb)hbXb2yeb@,tb&bQ<b1=Y_1VQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQVQ.v%%Fms["*s[.v"*\\^2d"\"%s"*\\^2d"\"")Qs["=Y.v+*"*\\^2Q"\"*3]"*\\^2Q"\"Q\YuyFYHpQ)

Requires any non-empty input, but the value thereof is not used.

Explanation (for the new and actually-reasonably-scoring version):

=QC`.pG                   Sets the value of the autofill variable to app. 256^27!  
                                  27! ~= the number of characters in the string
                                  containing all permutations of the alphabet. 
                                  We interpret that string as a base-256 number.
       L                  Define a function y(b,global Q):
        &=^QQ             Set Q to Q^Q and:
        ?+Ibt]0           If (?) the variable (b) is (I)nvariant on (+)adding itself
                             to the empty array (i.e. if it's an array itself):
               ?htb        If the second element of b is not 0:
                   ?eb         If the last element is not 0
                       [Xb2yeby@b1hG)   return [b with its last element replaced with y(b[-1]), y(b[1]), b[0]]
                     hb                 else return b[0]
                 Xb2yeb     else return b with its last element replaced with y(b[-1])
           @,tb&bQ<b1      If b isn't an array,return:
                               either b-1 if it's a standard ordinal (1 or more)
                               or Q if b is ω
                               or 0 if b is 0
 =Y_1                          Set the global variable Y to -1 (representing ω)
 VQ                        Q times, do (the rest of the explanation):
  VQVQ....VQ               Iterate from 0 to Q-1 183 times, each subiteration
                              reading the most recent value of Q when it starts:
  .v%%Fms["*s[.v"*\\^2d"\"%s"*\\^2d"\"")Q
                            Iterate from 0 to Q-1 Q times, each subiteration 
                               reading the most recent value of Q when it starts:                        
 s["=Y.v+*"*\\^2Q"\"*3]"*\\^2Q"\"Q
                             Y = [Y,Y,Y] Q times, stacking with previous iterations.
 uyFYHpQ)                    Run y_x(Y) for x incrementing until y_(x-1)(Y)=0

It's very hard for me to compute the size of this, mostly because it's late in the day and I'm not super familiar with fast-growing hierarchies or how I'd even go about trying to figure out how many times Q goes through the y() wringer. While I now know more about ordinals, I still have no idea how to calculate the value of the ordinal represented by the recursive definition in my program. I'd join the Discord server, but that's under a pseudonym I'd rather not be linked to my real name.

Unfortunately, because I know relatively little about said fast-growing hierarchies, I'm likely to have already lost to the Ruby answer. It's hard for me to tell. I may have beaten the Ruby answer, but I'm not 100% sure. ¯\_(ツ)_/¯

\$\endgroup\$
9
  • \$\begingroup\$ If I understand correctly, your score is probably somewhere in the ballpark of 27^^^27^^27^^4, or f<sub>4</sub>(27^^27^^4)) ≈ f<sub>4</sub>(f<sub>3</sub>(f<sub>3</sub>(19))). \$\endgroup\$ Nov 25, 2017 at 15:22
  • \$\begingroup\$ I made a small change that I should have thought of yesterday, but somehow didn't - making y recurse to operate on y(Q-1) instead of operating just on Q. How does this affect the score? \$\endgroup\$
    – Steven H.
    Nov 25, 2017 at 19:13
  • 1
    \$\begingroup\$ I'm not entirely sure what's going on. Does y(Q) = L(y(Q-1)), per se? \$\endgroup\$ Nov 25, 2017 at 19:18
  • 1
    \$\begingroup\$ I think we'll have better luck doing this in a chatroom. \$\endgroup\$
    – Steven H.
    Nov 25, 2017 at 19:22
  • \$\begingroup\$ @SimplyBeautifulArt Its probably best not to use fast growing hierarchy notation for this, since its kind of small. \$\endgroup\$
    – PyRulez
    Nov 27, 2017 at 1:25
3
\$\begingroup\$

Pyth, f3+σ-12(25626)

Where σm[n] is the Busy Beaver function Σ of order m called on n: σm[n] = Σm(n). The order -1 is to denote that the Busy Beaver here is not being called on a true Turing Machine, but rather an approximation with a finite wrapping tape of Q elements. This allows the halting problem to be solvable for these programs.

=QCGM.x-Hlhf!-/T4/T5.__<GH0M.x+Hlhf!-/T4/T5._>GHlGL=.<QC`m.uX@[XN2%h@N2l@N1XN2%t@N2l@N1XN1X@N1@N2%h@@N1@N2l@N1XN1X@N1@N2%t@@N1@N2l@N1XW!@@N1@N2N2nFKtPNXW@@N1@N2N2gFK)@hNeN3%heNlhNd)bLym*F[]d^UQQUQUld)^U6QJ"s*].v*\mQ"
.v+PPPP*JQ"+*\mQ\'

The TL;DR is that this creates all possible BrainF**k programs of length Q, runs them in an environment where the maximum value of an integer is Q and the tape length is Q, and compiles all the states from these operations together to append (that's the 3+) to Q, repeating the above on a scale of fω2.

I still have ~half the characters to work with if I wanted to do something more, but until we figure out where this is I'll just leave it as is.

\$\endgroup\$
2
  • \$\begingroup\$ I made a sorta better explanation of σ in the leaderboard. \$\endgroup\$ Dec 13, 2017 at 1:54
  • 5
    \$\begingroup\$ It doesn't look to me like this particular Busy Beaver function an be that fast growing. With a limit of Q integers between 0 and Q, there are only (Q+1)^Q possible tapes, and Q possible positions in the program, so there can be at most Q*(Q+1)^Q possible states of a running program. So a program must halt within Q*(Q+1)^Q steps or not at all. The number of possible programs is also limited by an exponential upper bound. So it looks to me like this Busy Beaver function has an exponential upper bound, and the final function will be on the order of $f_{\omega^2}$. \$\endgroup\$
    – Deedlit
    Dec 13, 2017 at 6:17
3
\$\begingroup\$

Python 3, probably fε0(99) I have no idea

def f(n,d,a,i):
 if d < 0 or i >= len(a):
  return n

 k = a[i]
 if type(k) == int:
  if k < 0:
   a[i] = [-2]*n
   a = f(n,d,a,i+k+2)
  else:
   a[i] -= 1
 else:
  a[i] = f(n,d-1,k,0)
 return a

def g(n):
 d=n
 a=[-2]*n
 while type(a) != int:
  a = f(n,d,a,0)
  n += 1
 

print(g(99))

Edit: Accidentally left d=2 from the slower-growing format, fixed and it's now d=n.

Try it online!

First, this is my first CGSE post (and my first SE post in general) so this definitely looks weird. Second, I'm not sure it's fε0(99) I have no idea what this is. Third, I did no golfing on this, just trying to get something out there that I can understand (and build upon in later edits). I consider this to be "v0.1",

Equivalent equation

Fourth, I'm not sure that g(n) grows at fε0. I sent it to the mathematics stackex discord, and ended up making an approximation of this program.

\$g(n) = f(n,n,\{-2,-2,\cdots\ n\ times\},0)\\a=\{a_0,a_1,\cdots a_k\}\$

\$f(n,d,a,i) =\left\{ \begin{array}{cl} n & : \ d < 0 \\ n & : \ i > k\\ f(n,d,\{a_0,\cdots a_{i-1},\{-2,-2,-2,\cdots n\ times\},a_{i+1}\cdots a_k \},i+k+2) & : \ a_i \in \mathbb{Z}\ \cap\ a_i<0\\ f(n+1,d-1,\{a_0\cdots a_{i-1},a_i-1,a_{i+1},\cdots a_k\},0) & : \ a_i \in \mathbb{Z}\ \cap\ a_i\geq 0 \\ \{a_0,a_1\cdots a_{i-1},f(n,d-1,a_i,0),a_{i+1},\cdots a_k\}&:\ a_i\notin\mathbb{Z} \end{array} \right.\$

If f(n,d,a,i) is cutting off on the side of the screen, then use these links to an image of the equation, both with a White background and with a Discord Dark Mode background.

Slower growing formats

Lastly, while testing it, to make sure it worked, I made a version that grows significantly slower.

Slower growing function. For this, it increments an unrelated q variable instead of incrementing n directly, then outputs q. With n=2 and d=2, it outputs 714025. With n=3 and d=2 or n=2 and d=3, tio.run gives me a "Program has exceeded the 60 second time limit."

def f(n,d,a,i):
 if d < 0 or i >= len(a):
  return n

 k = a[i]
 if type(k) == int:
  if k < 0:
   a[i] = [-2]*n
   a = f(n,d,a,i+k+2)
  else:
   a[i] -= 1
 else:
  a[i] = f(n,d-1,k,0)
 return a

n=3
d=2
a=[-2]*n
q=0

while type(a) != int:
 a = f(n,d,a,0)
 q += 1
 

print(q)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Jan 15 at 18:44
  • 2
    \$\begingroup\$ We have matjax enabled so you can embed the equation in the post without the weird discord coloured background. Just put it between \$s :) \$\endgroup\$
    – Wheat Wizard
    Jan 15 at 20:18
2
\$\begingroup\$

python, f3(f3(141)), 512 bytes

import math
def f(x):
    return math.factorial(x)  
x=9
for j in range(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(x))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))):
    x=f(x)
print x

This isn't really a valid answer, but I wanted to post it anyway. A quick rundown:

import math # imports the factorial function
def f(x):
    return math.factorial(x) # shortens the factorial operation
x=9 # sets x to highest available number
for j in range(f(...f(x)...)): # repeats * A LOT *
    x=f(x) # does the factorial of x
print x # outputs the result

Anyway, I don't know if this answer technically legal, but it was fun to write. Feel free to edit any errors you find in the code.

\$\endgroup\$
3
  • \$\begingroup\$ I think this is f_3(9), and it is definitely legal. You'd get a far larger number by nesting even for j in range(f(x)): for j in range(f(x)): x = f(x), though. Join us in chat to discuss why! \$\endgroup\$
    – Steven H.
    Dec 12, 2017 at 6:22
  • \$\begingroup\$ Why isn't it a valid answer? \$\endgroup\$ Dec 12, 2017 at 9:11
  • \$\begingroup\$ I didn't quite get the question, so I just made what I thought was right. \$\endgroup\$
    – i..
    Dec 13, 2017 at 0:34
1
\$\begingroup\$

Ruby, probably ~ fω+35(9999)

G=->n,k{n<1?k:(f=->b,c,d{x=[]
c<G[b,d]?b-=1:(x<<=b;c-=G[b,d])while c>=d
x<<[c]}
x=f[n-1,k,b=1]
(b+=1;*u,v=x;x=v==[0]?u:v==[*v]?u<<[v[0]-1]:u+f[n-1,G[v,b]-1,b])while x[0]
b)};(n=9**9**99).times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n.times{n=G[n,n]}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}};p n

Try it online!

Approximate Math Explanation:

The below is approximately equal to the program above, but simplified so that its easier to understand.

G(0,k) = k is our base function.

To evaluate G(n,k), we take k and write it as G(n-1,1) + ... + G(n-2,1) + ... + G(0,1).

Then change all of the G(x,1)'s into G(x,2)'s and subtract 1 from the entire result.

Rewrite it in the above form using G(x,2), where x<n, and leave the remainder at the end. Repeat, changing G(x,2) to G(x,3), etc.

When the result reaches -1, return the base (the b that would be in G(x,b).)

Examples:

G(1,1):

1: 1 = G(0,1)
2: G(0,2) - 1 = 1
3: 1 - 1 = 0
4: 0 - 1 = -1      <----- G(1,1) = 4

G(1,2):

1: 2 = G(0,1) + G(0,1)
2: G(0,2) + G(0,2) - 1 = G(0,2) + 1
3: G(0,3) + 1 - 1 = G(0,3)
4: G(0,4) - 1 = 3
5: 3 - 1 = 2
6: 2 - 1 = 1
7: 1 - 1 = 0
8: 0 - 1 = -1      <----- G(1,2) = 8

G(1,3):

1: 3 = G(0,1) + G(0,1) + G(0,1)
2: G(0,2) + G(0,2) + G(0,2) - 1 = G(0,2) + G(0,2) + 1
3: G(0,3) + G(0,3)
4: G(0,4) + 3
5: G(0,5) + 2
6: G(0,6) + 1
7: G(0,7)
8: 7
9: 6
10:5
11:4
12:3
13:2
14:1
15:0
16:-1      <----- G(1,3) = 16

G(2,5):

1: 5 = G(1,1) + G(0,1)
2: G(1,2) + 1
3: G(1,3)
4: G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + G(0,4) + 3
5: G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + G(0,5) + 2
6: G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + G(0,6) + 1
...
1024: -1      <----- G(2,5) = 1024

Doing some math, I found that

G(1,n-1) = 2ⁿ
G(2,n+6) ~ 2^G(2,n),  large enough n.

And beyond that it tends to get a bit hairy.

In general, we have

G(n,k+G(n-1,1)) ~ G(n-1,G(n,k)), large enough n.
\$\endgroup\$
1
\$\begingroup\$

Python 3, fωω+ω*ω(99999)

from functools import*
h=lambda a,x,b:h(h(a,x,b-1),x-1,a)if x*b else a+b
def f(*x):
    if(any(x[:2]):return reduce(lambda y,z:h(z,y,f(x[0],x[1]-1,*x[2:])),x[::-1])if x[0]*x[1]else(f(x[0]-1,f(x[0]-1,x[0],*x[2:]))if x[0]>x[1]else(f(x[1]-1,f(*([x[1]-1]*2+x[2:])),*x[2:])))
    for a,k in enumerate(x):if k:return f(*[f(*[k]*a,k-1,*x[a+1:])]*a,k-1,*x[a+1:])
    return 0
x,s,g,e,r,z=9**9**9**99,"f(*[%s]*%s)",lambda a,b:a%((b,)*a.count("%")),"x*=eval(\"%s\");","x","x=g(e,g(reduce(g,[s]*x,s),r));"
print(exec(z*x)or eval(r))

I'll get an explanation up soon.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This looks soo complicated, but I will trust your analysis. \$\endgroup\$
    – Binary198
    Nov 26, 2021 at 16:44
1
\$\begingroup\$

Python 3, ~ fε0(999)

N=9**9**9
def f(a,n):
 if a[0]==[]:return a[1:]
 if a[0][0]==[]:return[a[0][1:]]*n+a[1:]
 return [f(a[0],n)]+a[1:]
a=eval("["*N+"]"*N)
n=2
while a:a=f(a,n);n+=1
print(n)

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ N=9**9e99 should be slightly larger \$\endgroup\$
    – fejfo
    Dec 19, 2017 at 21:02
  • \$\begingroup\$ than whose answer? \$\endgroup\$
    – Leaky Nun
    Dec 19, 2017 at 21:03
  • \$\begingroup\$ I mean that if you replace the first like with N=9**9e99 the output should be slightly larger because 9e99>9**9. Ofcourse It is still your answer. \$\endgroup\$
    – fejfo
    Dec 19, 2017 at 21:05
  • \$\begingroup\$ @fejfo I mean it wouldn't change my ranking. \$\endgroup\$
    – Leaky Nun
    Dec 19, 2017 at 21:06
  • 3
    \$\begingroup\$ Does that matter? \$\endgroup\$
    – fejfo
    Dec 19, 2017 at 21:06
1
\$\begingroup\$

Python 3, 323 bytes, g9e9(9)

exec("""a=`x:9**x
n=`a,f:`x:a and n(a-1,f)(f(x))or x
c=`n:`l:l[~n](l)
e=`x:n(x,c(0))([x,`l:[a(l[0]),n(*l)],c(0),`l:[a(l[0]),l[2](l[:2])[1]]+map(`i:l[1]((l[0],i))[1],l[2:])]+list(map(c,range(a(x),1,-1))))[1]
f=`l:[l[1](l[0]),e(l[1](l[0]))(l)[1]]
g=`x:e(x)((x,f))[1]((x,a))[1](x)
print(n(9e9,g)(9))""".replace('`','lambda '))

Try it online!

Explanation

Python 3 is a truly recursive language, this means that not only can a function call itself, a function can also take other functions as input or output functions. Using functions to make themselves better is what my program is based on.

f=lambda x,a:[a(x),e(x)((x,a))[1]]

Definition

a(x)=9^x
b(x,f)=a(x), f^x
c(n)(*l)=l[~n](l)
c(0)=c0 <=> c0(…,f)=f(…,f)
d(x,b,c,*l)=a(x), c0(x,b), b(x,c0), b(x,f) for f in l
e(x)=c0^x(x,b,c0,d,c(a(x)),c(a(x)-1),c(a(x)-2),…,c(3),c(2),c(1))[1] 
f(x,a)=a(x),e(a(x))(x,a)[1](x)
g(x)=e(x)(x,f)[1](x,a)[1](x)
myNumber=g^9e9(9)

Definition explained

a(x)=9^x a is the base function, I chose this function because x>0=>a(x)>x` which avoids fixed points.

b(x,f)=a(x), f^x b is the general improving function, it takes in any function and outputs a better version of it. b can even be applied to itself: b(x,b)[1]=b^x b(x,b^x)[1]=b^(x*x)

but to fully use the power of b to improve b you need to take the output of b and use it as the new b, this is what c0 does:

c0(…,f)=f(…,f)
c0(x,b^x)=b^x(x,b^x)[1]>b^(9↑↑x)

the more general c(n) function takes the n last argument (starting from 0) so c(1)(…,f,a)=f(…,f,a) and c(2)(…,f,a,b)=f(…,f,a,b). *l means l is an array and l[~n] takes the n last argument

d(x,b,c,*l)=a(x), c0(x,b), b(x,c0), b(x,f) for f in l d uses c0 to upgrade b and b to upgrade all of the other input functions (of which there can be any amount because of the list)
d(x,b,c,d)>9^x,b^x,c^x,d^x and d²(x,b,c,d)>a²(x), b^(9↑↑x), c^(9↑↑x), d^(9↑↑x)

but d gets even better if you combine it with c:
c0²(x,b,c0,d)=d^x(9^x,b^x,c0^x,d^x)=… c0(x,b,c0,d,c1)=c1(x,b,c0,d,c1)=d(x,b,c0,d,c1)=9^x,b^x,c0^x,d^x,c1^x c0²(x,b,c0,d,c1)=c0(9^x,b^x,c0^x,d^x,c1^x)=c1^x(9^x,b^x,c0^x,d^x,c1^x)=…

the more c(x) you add at the end the more powerful it becomes. The first c0 always remains d: c0(x,b,c0,d,c4,c3,c2,c1)=c1(…)=c2(…)=c3(…)=c4(…)=d(x,b,c0,d,cX,cX-1,…,c3,c2,c1)=…
But the second leaves iterated versions behind:

c0²(x+1,b,c0,d,c4,c3,c2,c1)
=c0(9^x+1,b^x+1,c0^x+1,d^x+1,c4^x+1,c3^x+1,c2^x+1,c1^x+1)
=c1^x(c2^x(c3^x(c4^x(d^x(9^x+1,b^x+1,c0^x+1,d^x+1,c4^x+1,c3^x+1,c2^x+1,c1^x+1)))))

When d^x is finally calculated c4 will take a much more iterated version of d the next time. When c4^x is finally calculated c3 will take a much more iterated version of c4,…
This creates a really powerful version of iteration because d:

  1. Improves b using c0
  2. Improves c0 using b
  3. Improves all the layers of nesting using b The improves themselves improve, this means d becomes more powerful when it is iterated more.

Creating this long chain of c is what what e(x)=c0^x(x,b,c0,d,c(a(x)),c(a(x)-1),c(a(x)-2),…,c(3),c(2),c(1))[1] does.
It uses c0^x to bypass that c0 would just give d.
The [1] means that it will eventually return the second output of d^…. So b^….

At this point I couldn't think of any thing to do with e(x) to significantly increase it's output except increasing input.

So f(x,a)=a(x),e(a(x))(x,a)[1](x) uses the b^… generated by e(x) to output a better base function and uses that base function to call e(x) with a bigger input.

g(x)=e(x)(x,f)[1](x,a)[1](x) uses a final e(x) to nest f and produces a really powerful function.

Fgh approximation

I will need help approximating this number with any sort of fgh.

Old version: fωω6(fωω5 (9e999)), Try it online! Revision history of explanation

\$\endgroup\$
4
  • \$\begingroup\$ Actually, f_1(x) = x+x, but in the long run, this doesn't matter too much. \$\endgroup\$ Dec 24, 2017 at 0:41
  • \$\begingroup\$ Could you explain your fundamental sequences a bit more? \$\endgroup\$ Dec 24, 2017 at 0:41
  • \$\begingroup\$ @SimplyBeautifulArt ow yes I forgot to update that after I changed it from x*x. \$\endgroup\$
    – fejfo
    Dec 24, 2017 at 10:15
  • \$\begingroup\$ @SimplyBeautifulArt My answer doesn't use any ordinals so it's hard for me to explain it with ordinals. All I really can do is give the definition of my functions and an approximation of the effect in the fgh. Example: a2(f_n)~=f_{n+1} \$\endgroup\$
    – fejfo
    Dec 24, 2017 at 10:16
1
\$\begingroup\$

Ruby, fε02(5), 271 bytes

m=->n{x="";(0..n).map{|k|x+="->f#{k}{"};x+="->k{"+"y=#{n<1??k:"f1"};k.times{y=f0[y]};y";(2..n).map{|l|x+="[f#{l}]"};eval x+(n<1?"":"[k]")+"}"*(n+2)}
g=->z{t="m[#{z}]";(0...z).map{|j|t+="[m[#{z-j-1}]]"};eval t+"[->n{n+n}][#{z}]"}
p m[5][m[4]][m[3]][m[2]][m[1]][m[0]][g][6]

Try it online!

This is based off of the m(n) map.

Explanation:

m[0][f0][k] = f0[f0[...f0[k]...]] with k iterations of f0.

m[1][f0][f1][k] = f0[f0[...f0[f1]...]][k] with k iterations of f0.

m[2][f0][f1][f2][k] = f0[f0[...f0[f1]...]][f2][k] with k iterations of f0.

In general, m[n] takes in n+2 arguments, iterates the first argument, f0, k times onto the second argument, and then applies the resulting function onto the third argument (if it exists), then applies the resulting function onto the fourth argument (if it exists), etc.

Examples

m[0][n↦n+1][3] = (((3+1)+1)+1 = 6

In general, m[0][n↦n+1] = n↦2n.

m[0][m[0][n↦n+1]][3] = m[0][n↦2n][3] = 2(2(2(3))) = 24

In general, m[0][m[0][n↦n+1]] = n↦n*2^n.

m[1][m[0]][3]
= m[0][m[0][m[0][n↦n+1]]][3]
= m[0][m[0][n↦2n]][3]
= m[0][n↦n*2^n][3]
= (n↦n*2^n)[(n↦n*2^n)[n↦n*2^n(3)]]
= (n↦n*2^n)[(n↦n*2^n)[24]]
= (n↦n*2^n)[402653184]
= 402653184*2^402653184

In general, m[1][m[0]][n↦n+1] = f_ω in the fast-growing hierarchy.


g[z] = m[z][m[z-1]][m[z-2]]...[m[1]][m[0]][n↦2n][z]

and the final output being

m[5][m[4]][m[3]][m[2]][m[1]][m[0]][g][6]
\$\endgroup\$
1
\$\begingroup\$

Python 3, Greater than fSVO(Z)≈fψ0Ωω)(Z)

Where Z = (...((9^9)^(9^9))^((9^9)^(9^9))...) with about 9^9 parenthesis

def R(a,n):
    if type(a)==int:return a-1
    if n<1:return 0
    if not a:return n
    if a[-1]==0:return a[:-1]
    if a[0]!=0:a[0]=R(a[0],n);return a
    i=0
    while a[i]==0:i+=1
    a[i-1]=R(a[:],n-1);a[i]=R(a[i],n);return a
def G(a,n,m=0):
    A='\t'
    if a==0:return n+1
    if m:
        prgm='';b=G(a,n)
        for i in range(b):prgm+=A*i+'for _ in range(n):\n'
        prgm+=A*b+'n=G(R(a,n),n,m-1)';exec(prgm)
    m=0
    if type(a)==list:m=n
    for i in range(n):n=G(R(a,n),n,m)
    return n+1
z=Z=9**9
for i in range(z):Z=Z**Z
Z=G([Z]*Z,Z)
print(Z)

I wrote this mess a while back but didn't upload it because I was thinking I should just go for First Place Or Bust. Turns out: First Place is hard. So here's my 4th place submission.

Ungolfed program: https://github.com/cpaca/BignumReboot/blob/main/VeblenMethod.py

Website to minify a python program: https://python-minifier.com/

Unfortunately, because I wrote it so long ago, I've forgotten most of what I wrote. I remembered what my goal was, I remembered finishing it, but I don't remember the mathematics behind the mess very well. The ungolfed program has comments (lots of them, actually, looking at it) but there are a few hints that I do remember:


G(a,n,m) accepts either a list, int, int or an int, int, int. If the last variable isn't given, it's defaulted to 0.

All integers are positive. Negative integers should be inaccessible.

G(a,n,0) for int, int, 0 should be equivalent to fa(n) under the fast growing hierarchy. This evidently isn't the case, as it's calculating G(1,1) = 3, G(1,2) = 5, G(1,5) = 11, G(2,2) = 12. (Best guess, it's actually f0(fa(n)) but I can't really confirm.)

G([],n,0) - in other words, for empty list - should be equivalent to G(n,n,0)

R(a,n) is φ(a)[n] under the Veblen hierarchy.

G(a,n,0) should be greater than fφ(a)(n), where φ is the veblen function.

However, there is one thing that could make this function less than what I expect. In the analysis of the FGH, and the Veblen function, I made one assumption which MIGHT not be true:

$$f_{\alpha+\beta}(n) < f_{\alpha+f_\beta(n)}(n)$$

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to Code Golf, and great answer! \$\endgroup\$ Feb 22 at 23:23
1
\$\begingroup\$

Python 2, 181 bytes

def B(s):
 D=range(1,s);B=[[A]for A in D]+[[0]]
 for C in B[::-1]:
  for F in D:C+=[B[C[-1]][C[0]]]
 A=1;E=B[0]
 while s//A*E[:A]!=E:A*=2
 return A
A=0
while B(2**A)<99:A+=1
print A

Try it online!

Much, much larger than Loader’s number. It is well defined.

Nothing new. This is known as the Inverse Laver function.

\$\endgroup\$
3
  • \$\begingroup\$ What is the proof-theoretic strength here, both upper and lower bounds? To turn into a function, replace 99 with an input variable, I presume. Then what is the strength of the statement that the function is total? \$\endgroup\$ Jun 25 at 19:57
  • \$\begingroup\$ Googling a bit, I could not find a clear statement, but it appears the situation is something like: The program constructs finite approximations to an (infinite) left-distributive algrebra, and the termination proof for the program depends on that (or rather some subset) being infinite. Originally, the properties of left-distrib algrebras used a very large cardinal (rank-in-rank). However, Dehornoy later gave an algebraic construction avoiding the set theoretic machinery. The latter makes me skeptical that the function is particularly fast growing - please correct me if I'm wrong! \$\endgroup\$ Jun 25 at 20:59
  • \$\begingroup\$ Ok, arxiv.org/abs/1812.02761 appears to have a summary as of 2018 - the growth rate is uncertain, above primitive recursive and provably total given some very large cardinals - i.e., completely wide open. \$\endgroup\$ Jun 27 at 4:50
0
\$\begingroup\$

Javascript, 483 bytes

So, I'm just reusing a program I wrote for "Golf a number bigger than TREE(3)". The program results in \$f_{TFBO+1}(3) = f_{TFBO}(f_{TFBO}(f_{TFBO}(3)))\$ in the fast-growing hierarchy (3rd place), where \${TFBO}\$ is the Takeuti-Feferman-Buchholz Ordinal \$\psi(\Omega_{\omega+1})\$. It uses Buchholz hydras and implements the BH function. Here is my compressed code, which was done with Naruyoko's Javascript compressor:

_="69{%t.length-1D*6m#{%B]}*6s#{t.splice(m#,14*@n=1;*6e#{7==0/s#;if(9>1/$i=0;i<n;i:t'B-1]4}}7>0&&typeof t==\"number\"/$i=98t[i]<m#8i--/}@s;$j5i8j <= 98j:s't[j]4@?5s;?[j]=?[i]-1;?[l(?)]=0;s#;$k508k <= l(?)8k:t'?[k]4}7==A/B]=n+1Dn += 1;%tD*6b(k/i5[\"+\",0];$l508l < k-28l:i'A)}while(l(i)>=0/i=e(i4%nD*Console.log(b(b(b(3))));#(t)$for(let %return '.push(*\n    /){4)D5 = 6function 7if(m#8; 9l#:++/?sa@var A\"w\"Bt[9D;}";for($ of"DBA@?:987654/*'%$#")with(_.split($))_=join(pop());eval(_)

This is basically incomprehensible, with only fragments of the original code revealing themselves, so here is the original code:

function l(t){return t.length-1;}
function m(t){return t[l(t)]}
function s(t){t.splice(m(t),1);}
var n=1;
function e(t){if(m(t)==0){s(t);if(l(t)>1){for(let i=0;i<n;i++){t.push(t[l(t)-1]);}}}if(m(t)>0&&typeof t=="number"){for(let i=l(t); t[i]<m(t); i--){}var s;for(let j = i; j <= l(t); j++){s.push(t[j]);}var sa = s;sa[j]=sa[i]-1;sa[l(sa)]=0;s(t);for(let k = 0; k <= l(sa); k++){t.push(sa[k]);}}if(m(t)=="w"){t[l(t)]=n+1;}n += 1;return t;}
function b(k){i = ["+",0];for(let l = 0; l < k-2; l++){i.push("w")}while(l(i)>=0){i=e(i);}return n;}
Console.log(b(b(b(3))));

Explanation

This program, as I mentioned earlier implements Buchholz hydras, which are stored as arrays. The program has functions l, m and s, which just serve as shorthand for commonly repeated chunks of code. The function e takes a given hydra and expands it using rules.

It was proven by Buchholz that you can always kill a hydra in a very large, yet finite, amount of steps, so this is what the program uses. The function b(n) produces the hydra [+,0] and then a string of n-2 \$\omega\$s, and returns the number of steps it took to be killed.

The number which it returns is \$BH^3(3)\$, which is around \$f_{\psi_0(\varepsilon_{\Omega_\omega+1})+1}(3)\$ in the FGH.

Size

The function \$BH(n)\$ which this program implements is proven to eventually dominate (overtakes) any function which is provably total in \$\Pi^1_1\$-comprehension with bar induction (\$\Pi^1_1-CA+BI\$).

In fact, even if I replaced "chain of n-2 \$\omega\$s" with "chain of n-2 ones", I would still get third place. However, I have to say, Simply Beautiful Art, your achievement of second place is simply beautiful, and I could never beat it just by trivially this program. Since \$TFBO = \psi_0(\varepsilon_{\Omega_\omega + 1})\$, I could say that \$TFBO_2 = \psi_0(\varepsilon_{\Omega_{TFBO} + 1})\$, and so on, if I allowed labels up to \$TFBO_{TFBO_{...}}\$ instead of just \$\omega\$, my new growth rate would fall around \$\psi_0(\chi(\Omega))+1\$, which is tiny compared to \$\psi_0(\chi(\Omega_{M+\chi(\Omega_M+1^{Ω_{M+1}})}))+29\$

\$\endgroup\$
2
  • \$\begingroup\$ The function b takes a parameter n and returns n without modifying it (the global variable n is distinct from this parameter and has no effect on it), so b(b(b(3))) returns 3, which may be slightly smaller than what you intended. Also, writing to a variable is not one of the allowed output methods. \$\endgroup\$ Nov 21, 2021 at 23:26
  • \$\begingroup\$ Ooh sorry, that's not what I intended to happen. I will fix it \$\endgroup\$
    – Binary198
    Nov 22, 2021 at 17:15

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.