Comment by gglon
11 years ago
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
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)
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
I just realized 99 should be replaced with "9!".
Using the infix special form ~ we can cram in another ^#:
I should also note that I'm not confident as to which of
is larger.
4 replies →
Related, this came up in yesterday's thread about Graham's number:
https://news.ycombinator.com/item?id=9054274
Just do -1 on an unsigned number if you're that lazy.
My solution in brainfuck, given a finite tape:
might be easier to use a language like Idris, which can check that functions are total (i.e. return a finite number in finite time).
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).