Comment by evanb

11 years ago

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_]:=If[n==0,a b,Nest[u[n-1]@a,1,b]];Nest[u[#^#^#][#]@#&,9,u[99][9]@9]

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.

https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

6 comments

evanb

evanb 11 years ago

I just realized 99 should be replaced with "9!".

evanb 11 years ago

Using the infix special form ~ we can cram in another ^#:

  u[n_][a_,b_]:=If[n==0,a b,Nest[a~u[n-1]~#&,1,b]];Nest[#~u[#^#^#^#]~#&,9,9~u@9~9]

I should also note that I'm not confident as to which of

  Nest[#~u[#^#^#^#]~#&,9,9~u@9~9]
  Nest[#~u@#~#&,9,9~u[9^9^9^9]~9]

is larger.

gglon 11 years ago

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.

Here is my modification:

  M=Nest;
  u[f_][n_][a_]:=If[n<1,f@a,M[u[f][n-1],a,a]];
  u[#][#@9][#@9]&@(u[#!&][#][#]&)

82 chars total.

comments:

  (*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[#!&][#][#]&)

3 replies →