[Question]
  [
Write the shortest possible program (length measured in bytes) satisfying the following requirements:
* no input
* output is to stdout
* execution eventually terminates
* total number of output bytes exceeds [Graham's number](http://en.wikipedia.org/wiki/Graham%27s_number)
Assume that programs run until "normal" termination on an *ideal* computer1 able to access unlimited resources, and that the common programming languages are modified if necessary (without changing the syntax) to allow this. Because of these assumptions, we might call this a kind of Gedankenexperiment.
To get things started, here's a 73-byte Ruby program that computes fω+1(99) in the [fast-growing hierarchy](http://en.wikipedia.org/wiki/Fast-growing_hierarchy#Functions_in_fast-growing_hierarchies):
```
f=proc{|k,n|k>0?n.times{n=f[k-1,n]}:n+=1;n};n=99;n.times{n=f[n,n]};puts n
```
1 EDIT: More precisely, suppose we're taking an existing system and modifying it only to have no upper limit on storage size (but it is always finite). The execution-times of instructions are *not* supposed to be modified, but the machine is assumed to be ideal in that it will have no upper limit on its operating lifetime.
  
[Answer]
## Haskell, ~~59~~ ~~57~~ ~~55~~ 63
```
(f%s)1=s;(f%s)n=f.(f%s)$n-1
main=print$((flip((%3)%(3^))3)%4)66
```
How it works: `%` simply takes a function and composes it `n-1` times on top of `s`; i.e. `%3` takes a function `f` and returns a function of `n` that equals applying it `f` to 3, `n-1` times in a row. If we iterate the application of this higher-order function, we get a fast-growing sequence of functions – starting with exponentiation, it's exactly the sequence of Knuth-arrow-forest sizes:
  
`((%3)%(3^))1 n = (3^)n     = 3ⁿ = 3↑n`
  
`((%3)%(3^))2 n = ((3^)%3)n = (3↑)ⁿ⁻¹ $ 3 = 3↑↑n`
  
`((%3)%(3^))3 n = (((3^)%3)%3)n = (3↑↑)ⁿ⁻¹ $ 3  = 3↑↑↑n`
  
 and so on. `((%3)%(3^))n 3` is `3 ↑ⁿ 3`, which is what appears in the calculation to Graham's number. All that's left to do is composing the function `(\n -> 3 ↑ⁿ 3) ≡ flip((%3)%(3^))3` more than 64 times, on top of 4 (the number of arrows the calculation starts with), to get a number larger than Graham's number. It's obvious that the logarithm (what a lamely slow function that is!) of `g₆₅` is still larger than `g₆₄=G`, so if we print that number the output length exceeds `G`.
⬛
[Answer]
# Binary Lambda Calculus, 78 bits = 9.75 bytes
Here is an expression in Binary Lambda Calculus that is less than 10 bytes, yet surpasses Graham's Number. This is over 5x shorter than my [previous post](https://codegolf.stackexchange.com/questions/6430/post/219469) in JavaScript. Since [Binary Lambda Calculus](https://esolangs.org/wiki/Binary_lambda_calculus) is radically different than JavaScript, I decided to answer this in a separate post.
```
010101000001110011101000000101011000000101101101011010000110100000011100111010
```
You can find some interpreters [here](https://tromp.github.io/cl/cl.html).
## **[Explanation I made on another post](https://codegolf.stackexchange.com/questions/31695/post/219649)**
Essentially, this binary expression encodes this lambda calculus expression:
```
(\f x.f (f x))(\f n.n (\g m.m g m) f n)(\x.x x)(\f x.f (f x))
```
The decodings can be described like this:
* `(\f x.f (f x))` at the start and at the end corresponds to the Church Numeral \$2\$.
* `(\f n.n (\g m.m g m) f n)` takes in a function \$f\$ and a number \$n\$, and returns \$f\_n (n)\$ where \$f\_0 (n) = f(n)\$ and \$f\_{m+1} (n) = f\_m^n (n)\$ using functional recursion. Let's call this function \$S\$.
* `(\x.x x)` corresponds to the function that raises a number to the power of itself, or \$f(x)=x^x\$.
Since Church Numerals naturally nest the function that they apply to, the lambda calculus string gets reduced as follows:
$$2Sf2 \rightarrow S(Sf)2$$
Since each \$S\$ adds \$\omega\$ to the growth rate of the function, and the \$f(x)=x^x\$ has growth rate \$f\_2\$ in the Fast Growing Hierarchy, then \$(Sf)\$ has growth rate \$f\_{\omega}\$, and \$S(Sf) = 2Sf\$ has growth rate \$f\_{\omega2}\$.
This means the expression \$2Sf2\$ described above has the value of about \$f\_{\omega2} (2)\$ in the Fast-growing Hierarchy. This is greater than Graham's Number.
Therefore, Graham's Number can be beaten by a program that less than 10 bytes!
[Answer]
## GolfScript (49 47 chars)
```
4.,{\):i\.0={.0+.({<}+??\((\+.@<i*\+}{(;}if.}do
```
See [Lifetime of a worm](https://codegolf.stackexchange.com/a/18931/194) for lots of explanation. In short, this prints a number greater than fωω(2).
[Answer]
# [Binary Lambda Calculus](https://tromp.github.io/cl/cl.html), ~~7.625~~ ~~7.5~~ ~~6.75~~ 6.125 bytes, ~~61~~ ~~60~~ ~~54~~ 49 bits
```
0100011010000110011000000101101100000011100111010
```
This encodes:
```
(\x.x x) (\y.y (y (\g m.m g (\f n.f (f n)))))
```
To simplify things a bit, let `H = (\g m.m g 2)` where `2` is the [Church numeral](https://en.wikipedia.org/wiki/Church_encoding) `(\f n.f (f n))`. These are the first few steps of the reduction:
```
(\x.x x) (\y.y (y H))
(\y.y (y H)) (\y.y (y H))
(\y.y (y H)) ((\y.y (y H)) H)
(\y.y (y H)) (H (H H))
H (H H) (H (H H) H)
H (H H) H (H H) 2
H (H H) 2 (H H) 2
2 (H H) 2 (H H) 2
H H (H H 2) (H H) 2
H H 2 H 2 (H H) 2
2 H 2 H 2 (H H) 2
H (H 2) H 2 (H H) 2
H (H 2) 2 2 (H H) 2
2 (H 2) 2 2 (H H) 2
H 2 (H 2 2) 2 (H H) 2
H 2 2 2 2 2 (H H) 2
2 2 2 2 2 2 (H H) 2
2^^6 (H H) 2
```
The next step is applying `H H` \$2\uparrow\uparrow6\$ times to `2`. After an odd number of aplications the result is not a number, but after an even number of aplications it is. Here \$2\uparrow\uparrow6\$ is not an aproximation, and since it is even, the final answer will be a number. We will use \$\frac{2\uparrow\uparrow6}{2}\$ times a function that applies `H H` twice. The function `H H (H H n)` grows as fast as the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function), to see this, let's take a look at a more general case. The function `k H 2 n` grows as fast as \$2\uparrow^kn\$:
```
0 H 2 n = 2 n = n^2 > 2*n = 2{0}n
k+1 H 2 n = H (k H 2) n = H (\x.k H 2 x) n >= H (\x. 2{k}x) n
    = n (\x. 2{k}x) 2 = 2{k+1}(n+1) > 2{k+1}n
```
Applying this to `H H (H H n)` we get `H H (H H n) = H H n H 2 = n H 2 H 2 = H (n-1 H 2) H 2 = H (n-1 H 2) 2 2 = 2 (n-1 H 2) 2 2 = n-1 H 2 (n-1 H 2 2) 2 >= n-1 H 2 2{n-1}2 2 >= 2{n-1}2{n-1}2 2 = 2{n}3 2 > 2{n}3`, which is about the same as \$A(n,n)\$. So the size of the expression `2^^6 (H H) 2` is about \$g\_{\frac{2\uparrow\uparrow6}{2}} > g\_{64}\$.
[Answer]
# Python 3, 53 bytes
```
m=lambda x:-x if x<0 else m(x-m(x-1))/2;print(1/m(9))
```
It computes the reciprocal of the gap between the 9 and the smallest tame fusible number above it, which is shown [here](https://arxiv.org/pdf/2003.14342.pdf) to be at least \$f\_{\varepsilon\_0}(2)\$ in the fast-growing hierarchy, thus beating Graham's number.
# Pyth, ~~24~~ 22 bytes
-2 bytes thanks to r.e.s.
```
DlHR?<HZ_H/l-Hl-H12)lT
```
Same algorithm as before. I changed the argument 9 to 10 (which due to the predefined variable `T` doesn't increase the length), thus making the output at least \$f\_{\varepsilon\_0}(3)\$, absolutely dominating Graham's number and every other answer so far.
[Answer]
# [Pyth](https://github.com/isaacg1/pyth), ~~29~~ 28 bytes
```
M?*GHgtGtgGtH^ThH=ZTV99=gZTZ
```
Defines a lambda for hyper-operation and recursively calls it. Like the definition for Graham's number, but with larger values.
This:
```
M?*GHgtGtgGtH^3hH
```
Defines a lambda, roughly equal to the python
```
g = lambda G, H:
  g(G-1, g(G, H-1)-1) if G*H else 3^(H+1)
```
This gives the hyper-operation function, g(G,H) = 3↑G+1(H+1).  
So, for example, g(1,2)=3↑23 = 7,625,597,484,987, [which you can test here](https://tio.run/##K6gsyfj/39dey90jvcS9JN29xCPOOMMj3VDB6P9/AA "Pyth – Try It Online").
`V<x><y>` starts a loop that executes the body, `y`, `x` times.  
`=gZT` is the body of the loop here, which is equivalent to `Z=g(Z,10)`
The code:
```
M?*GHgtGtgGtH^3hH=Z3V64=gZ2)Z
```
Should recursively call the hyperoperation above 64 times, giving Graham's Number.
In my answer, however, I've replaced the single digits with `T`, which is initialized to 10, and increased the depth of recursion to 99. Using [Graham Array Notation](http://googology.wikia.com/wiki/Graham_Array_Notation), Graham's Number is [3,3,4,64], and my program outputs the larger [10,11,11,99]. I've also removed the `)` that closes the loop to save one byte, so it prints each successive value in the 99 iterations.
[Answer]
# Javascript, 50 Bytes, \$f\_{\omega+8} (9)\$
```
n=(y,x=9)=>y?y-9?n(y-1,x?n(y,x-1)*9:9):x:n(x);n(8)
```
Here, n is a binary function. The function is defined as followed:
* `n(9,x) = x`
* `n(y,0) = n(y-1,9)`
* `n(y,x) = n(y-1,n(y,x-1)*9)`
The `*9` ensures that `n(y,x)` is an increasing function with respect to x.
* `n(9,x)` = x
* `n(10,x)` = 9^(x+1)
* `n(11,x)` ~ 9^^x
* `n(12,x)` ~ 9^^^x
* `n(y+1,x)` recurses over `n(y,x)` with respect to x.
We also defined n(y)=n(y,9), so n(y) grows as fast as \$f\_{\omega}\$ in the Fast Growing Hierarchy.
Now here is the twist:
* `n(0,x)=n(x)=n(x,9)`
This starts an entirely new hierarchy starting from `y=0` all the way up to `y=8`.
* `n(0,x)` grows at \$f\_{\omega}\$ in the FGH
* `n(1,x)` grows at \$f\_{\omega+1} = G\$
* `n(2,x)` grows at \$f\_{\omega+2}\$
* ...
* `n(8,x)` grows at \$f\_{\omega+8}\$
Therefore, `n(8)` ~ \$f\_{\omega+8} (9) > G\_{64}\$
[Answer]
## Ruby, ~~54~~ ~~52~~ 50 bytes
```
f=->b{a*=a;eval"f[b-1];"*b*a};eval"f[a];"*a=99;p a
```
---
## Ruby, ~~85~~ ~~81~~ ~~76~~ ~~71~~ ~~68~~ ~~64~~ ~~63~~ ~~59~~ 57 bytes
```
f=->a,b=-a{eval"a*=b<0?f[a,a]:b<1?a:f[a,b-1];"*a};p f[99]
```
Pretty much fast growing hierarchy with f(a+1) > fω+1(a).
---
## Ruby, 61 bytes
```
f=->a,b=-a{a<0?9:b==0?a*a:f[f[a-1,b],b>0?b-1:f[a,b+1]]};f[99]
```
Basically an Ackermann function with a twist.
---
## Ruby, ~~63~~ 59 bytes
```
n=99;(H=->a{b,*c=a;n.times{b ?H[[b-1]*n*b+c]:n+=n}})[n];p n
```
---
## Another Ruby, ~~74~~ 71 bytes
```
def f(a,b=a)a<0?b:b<0?f(a-1):f(a-1,f(a,b-1))end;n=99;n.times{n=f n};p n
```
Basically Ackermann function to itself 99 times.
[Answer]
## Python (111+n), n=length(x)
Although this one is not as short as the answerer's Ruby program, I'll post it anyway, to rule this possibility out.
It uses the Ackermann function, and calls the Ackermann function with m and n being the values from another call to the Ackermann function, and recurses 1000 times.
This is **probably** bigger than Graham's number, but I'm not sure, because nobody knows the exact length of it. It can be easily extended, if it's not bigger.
```
x=999
b='A('*x+'5,5'+')'*x
def A(m,n):n+1 if m==0 else A(m-1,A(m,n-1)if n>0 else 1)
exec('print A('%s,%s')'%(b,b))
```
[Answer]
# [GolfScript](http://www.golfscript.com/golfscript/), ~~24~~ ~~20~~ 18 bytes
```
"`'1$,*~'+"{.~~})*
```
[Try it online!](https://tio.run/##S8/PSStOLsosKPn/XylB3VBFR6tOXVupWq@urlZT6/9/AA "GolfScript – Try It Online")
```
"`'1$,*~'+"         # Push this string
           {.~~})*  # Becomes {.~}126* and this duplicates and executes the string 126 times
```
When executed, this string modifies the string at the top of the stack:
```
 `          # Parse it to a string inside the string  'foo'  -> '"foo"'
  '1$,*~'+  # Add '1$,*~' at the end                  '"foo"' -> '"foo"1$,*~'
```
When we execute this new string it does whatever `foo` used to do, but many times.
```
     1$,     # Get the number of bytes of the string at the top of the stack
"foo"   *    # Make that many copies of foo
         ~   # Execute all of them
```
We will be dealing with only one string, that will modify itself 126 times. Let `L` be the number of loops and `B` the number of bytes the string has. These values can be calculated with \$B=2^{L+1}+3L+7\$, but for simplicity's sake we will round `B` down to `L`. The number of bytes grows exponentially because every time a loop is added, every `"` becomes `\"` and every `\` becomes `\\`. Now the loops execute `L` times instead of `B`. When the string has no loops it just adds `"` `"1$,*~` around itself, in other words `L = L + 1`. With `a` loops it executes `L` times the version with `a-1` loops. This is exactly the same definition of `f` in the [fast growing hierarchy](https://en.wikipedia.org/wiki/Fast-growing_hierarchy) for when `a` is a successor:
$$f\_0(L)=L+1$$
$$f\_a(L)=f\_{a-1}^L(L)$$
Before each execution `a` and `L` are the same number, so every time we execute the string, `L` becomes \$f\_\omega(L)\$.
We execute it 126 times starting with `L = 0`, so the number of bytes in the output will be:
$$f\_\omega^{126}(0)=f\_\omega^{122}(f\_8(8))>f\_\omega^{122}(122)=f\_{\omega+1}(122)$$
[Answer]
# [Functoid](https://github.com/bforte/Functoid), 14 bytes
```
B"W(BiCA])9.Ef
```
[Try it online!](https://tio.run/##SyvNSy7Jz0z5/99JKVzDKdPZMVbTUs817f9/AA "Functoid – Try It Online")
The pointer wraps around whenever it moves out of the source code, this happens once here, making the code equivalent to `B"W(BiCA])9.EfB"W(BiCA])9.Ef`. The string `"W(BiCA])9.EfB"` gets converted to base 10 and becomes `"91772447243986"`. Now we can rewrite the code as `BkW(BiCA])9.Ef`, where `k` represents that big number.
```
BkW(BiCA])9         # set the current function to B k W (B i C A ]) 9
           .        # evaluate and print the current function as a number
            Ef      # terminate the program
            
```
Let `f_a` be a lambda function equivalent to \$f\_a\$ in the [fast growing hierarchy](https://en.wikipedia.org/wiki/Fast-growing_hierarchy). To increase the index by 1, the function needs to be applied to itself `n` times \$f\_a^n(n) = f\_{a+1}(n)\$. In code this would be `f_(a+1) n = n f_a n = C A f_a n`. To get any finite index we just need to apply `C A` a lot of times to `f_0 = ]`:
```
f_0 = ]
f_1 = C A ]
f_2 = C A (C A ])
f_3 = C A (C A (C A ]))
...
```
\$f\_\omega(n) = f\_n(n)\$ = `n (C A) ] n = W (i (C A) ]) n`
The expression `B k W (B i C A ]) 9` can be reduced to `k (W (i (C A) ])) 9 = k f_ω 9` and this returns \$f\_\omega^{91772447243986}(9)\$.
[Answer]
# Python 3, 79 bytes
```
f=lambda x,y:f(x-1,f(x,y-1))if x*y else x+y+1
z=9;exec("z=f(z,z);"*99);print(z)
```
f(x,y) is a modified version of ackermann for golfing purposes
  
  
f(x,y) = f(x-1,f(x,y-1)) if both x and y are greater than 0
  
f(x,0) and f(0,y) each add one to the nonzero entry (if both are zero, it is 1)
Then the program does recursion on f(x,x) 99 times.
[Answer]
# JavaScript, 68 bytes, however uncompeting for using ES6
```
a=(x,y)=>y?x?a(a(x-1,y)*9,y-1):a(9,y-1):x;b=x=>x?a(9,b(x-1)):9;b(99)
```
`a` function is similar to up-arrow notation with base 9.
```
       /a(a(x-1,y)*9,y-1)  x>0, y>0
a(x,y)=|a(9,y-1)           x=0, y>0
       \x                  y=0
```
`b` function is: b(x)=bx(9).
`b(99)` is ~fω+1(99), compared to Graham's number<fω+1(64).
[Answer]
# Python 3, ~~174~~ ~~171~~ ~~168~~ ~~148~~ ~~125~~ ~~117~~ ~~116~~ ~~112~~ 101 bytes
3^^^...^3 with Graham's number arrows i.e. G(65) (boring, I know)
```
a=lambda b,c:3if b<2else(a(a(b-1,c),c-1)if c else 3*b)
G=lambda k:a(3,G(k-1))if k else 4
print(G(65))
```
Pretty human-readable. a implements arrow notation, G is Graham's sequence.
## Improvements
* Replaced G(64)+1 with G(65), saving two bytes
* Replaced `if c==1:return a**b` with `if c==0:return a*b`, saving one byte
* Renamed ar function to a and renamed variable a to k, saving three bytes
* Turned G function from a proper function into a lambda, saving twenty bytes, believe it or not!
* Turned a function from a proper function also into a lambda, saving twenty-three bytes!
* Removed k from a function since we will only be using it with base 3, saving eight bytes.
* Removed an unnecessary space
* Removed some more unnecessary spaces, saving four bytes
* Shortened definitions of a and G, saving eleven bytes
[Answer]
# [7](https://esolangs.org/wiki/7), 17.5 bytes
```
00000000: 505e 91e7 a3a4 63c8 edda 476d ea0b d556  P^....c...Gm...V
00000010: d7e                                      ..
```
Written in octal:
```
24057221717216443074435566443555724057252555375
```
[Try it online!](https://tio.run/##HYqxDQAACMJeUhT5/zI0LrRJkY0OCkilkNNdoRty5nHtD8R5ifYC "7 – Try It Online")
`721gge644355` is a function that, given a function `f_a()`, returns `f_(a+1)()`:
```
|f_a() 721gge644355
|c7{f_a()}ggerr          # Where {f_a()} represents the pacified version of f_a()
# Applying the result to some number n, to see that it worked:
|n c7{f_a()}ggerr
|n|f_a() nr
   f_a() n               # Make n copies of f_a(), resulting in f^n_a()
 n        r              # Apply it to n, resulting in f^n_a(n) = f_(a+1)(n)
```
From that, a function `f_w()` can be written:
```
|n cc71721644307443556ggerrr
|n|n|721gge644355 nrr
   n                              # A function (\x -> x^n), representing f_0()
     721gge644355 nr              # Add 1 n times to the index of f_0(), resulting in f_n()
 n                  r             # Apply the result to n, resulting in f_n(n) = f_w(n)
```
The full program computes `f^256_w(2)`, which is greater than Graham's number:
```
|| 24057221717216443074435566443555724057252555375
||cg6r|cc71721644307443556ggerrr|cg6r|crcrrre|r
||cg6r|cc71721644307443556ggerrr|cg6r|crcrrre|r r
||cg6r|cc71721644307443556ggerrr|cg6r|crcrrre r
||cg6r|cc71721644307443556ggerrr|cg6r crcrrre
                                 cg6r              # The number 2
                                      cr           # Raise 2, to itself returning 4
                                        cr         # Raise 4, to itself returning 256
       cc71721644307443556ggerrr          r        # Make 256 copies of f_w(), resulting in f^256_w()
  cg6r                                     r       # Apply this function to 2, resulting in f^256_w(2)
                                            e      # Print the result in the same encoding as the source code
```
We can see the code working by reducing it to just `f_w(2)`. This outputs `2^2^18`, which is represented by `2^18` copies of `2405` in the same encoding as the source.
```
2405722171721644307443556644355575375
```
[Try it online!](https://tio.run/##HcXBEQAgCAPBliQQrv/KouNnl0RzjFQUqp3pw8Pe/Rk3Ti4 "7 – Try It Online")
[Answer]
**Python: 85**
```
f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*99
exec'f('*64+'3'+',3)'*64
```
Which maybe could be shortened to *74 + `length(X)`*:
```
f=lambda a,a:a*a
exec'f=lambda a,b,f=f:reduce(f,[a]*b,1)'*int('9'*X)
f(3,3)
```
Where `X` is an appropriate big number such that the resultant hyperoperation on `3, 3` is bigger than Grahams number(if this number is less than `99999999999` then some byte is saved).
---
Note: I assume the python code is executed on the interactive interpreter hence the result is printed to stdout, otherwise add `9` bytes to each solution for the call to `print`.
[Answer]
# Javascript, 83 bytes
Another Ackermann function solution.
```
(function a(m,n,x){return x?a(a(m,n,x-1),n,0):(m?a(m-1,n?a(m,n-1):1):n+1)})(9,9,99)
```
[Answer]
# Ruby, 60 bytes
```
f=->n{n.times{eval("n.times{"*n+"n+=1"+"}"*n)};n};f.call(64)
```
This is \$f\_{\omega+1}(64)\$, exactly, which is slightly bigger than Graham's number :) I copied this from Simply Beautiful Art on their Bignum Bakeoff post.
]