Now the contest for programmers:
Write the biggest number in one line of code (80 characters, keywords count as 1 character, whitespace - 0) using computer language of choice(standard library with infinite integer type)
that any reasonable programmer can prove that it is actually a finite number.
Mathematica has important whitespace for indicating multiplication, and it's not clear what counts as a keyword, so here are 80 copy-and-pasteable characters:
u[n][a][b] gives a (Knuth's up arrow)^n b.
The after-the-semicolon expression computes
f(f(f(f(... u[99][9][9] fs total ... f(9) ... ))))
with the function f(n)=u[n^n^n][n][n].
This clearly results in a finite number, since it is just iterated iterated iterated iterated ... (finitely many "iterated"s) ... iterated exponentiation of finite numbers.
However, even when I try to compute (after $RecursionLimit=Infinity)
Nest[u[#^#^#][#]@#&,2,u[2][2]@2]
my kernel crashes. This number is BIG.
There is one obvious way to make this number even bigger: make the base case yield a^b. However, then it's not Knuth's up arrow notation, so it's harder to debug by looking at the wikipedia page :). I used all my tricks (like using @) to get rid of extraneous characters, which gave me space to put #^#^# as the first argument of u. I still had 1 character remaining, so a 9 became 99. If you can squeeze a few more characters #^#^# and 99 should be substituted for u[#][#]@# and 9.
Very nice. Mathematica can clearly do the job. But I feel like there is still a lot of room for improvement. Clearly though, the proof would be more and more difficult.
(*start with definition of Knuth up arrow*)
u1[n_][a_][b_]:=If[n==0,a b,Nest[u[n-1]@a,1,b]]
(*let treat 1 as symbol and take 1 == b == a *)
u2[n_][a_]:=If[n==0,a a,Nest[u[n-1],a,a]]
(*next define for arbitrary function f instead of multiplication*)
u[f_][n_][a_]:=If[n==0,f@a,Nest[u[n-1],a,a]]
(*numerical example when we take n<3 instead of n==0*)
u[#! &][#][#] &@3 = u[#! &][3][3] = 10^1746
(*Next take the function f and parameters a to be: *)
f = u[#!&][#][#]&
a = f@9
(*compute final number*)
u[f][a][a]
(*those 3 steps are shortened to: *)
u[#][#@9][#@9]&@(u[#!&][#][#]&)
Smart. It didn't occur to me to have the base case be an arbitrary function. Yours is much larger than mine. One comment: M=Nest; is a waste of characters. I tried that in my solution too, but it wound up costing me an extra character ;). So I think you're down to 75 characters. It might make sense to remove the factorial, and change the base case of u to f@f@f@f@a.
Thanks, I forgot to remove M=Nest that was beneficial in my previous attempts where I used 3 Nests.
But remember:
Never forget that it is a waste of energy to do the same thing
twice, and that if you know precisely what is to be done, you
need not do it at all.
--- E. E. ``Doc'' Smith (1930)
...the optimal solution avoids all pattern.
--- Douglas Hofstadter (1983)
Unfortunately, if a language L has the property that all programs in it are total, that means L is not Turing-complete. In fact, that puts a hard limit on the growth speed of functions definable in L. For example, the Busy Beaver function for L won't be definable in L (because otherwise you'd get the same paradox as in the halting problem), but will be easily definable in any Turing-complete language (because you can just dovetail through all possible programs in L without worrying that any of them will loop forever).
