Shortest terminating program whose output size exceeds Graham's number 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


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:

f=proc{|k,n|k&gt;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.
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 -&gt; 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.

⬛