4 ms·

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 lan

by gglon 12y 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.

deleted 12y ago
[deleted]
- deleted 12y ago
  [deleted]
swatow 12y ago
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).
- cousin_it 12y ago
  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).
deleted 12y ago
[deleted]
yepguy 12y ago
My solution in brainfuck, given a finite tape: -[>-]-
evanb 12y 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 https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
- evanb 12y ago
  I just realized 99 should be replaced with "9!".
  - evanb 12y 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 12y 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[#!&][#][#]&)
leohutson 12y ago
num = 0; while (true) { try { num++; } except ( mallocFail ) { return num; } }
- Gurkenmaster 12y ago
  Just do -1 on an unsigned number if you're that lazy.
throwaway_yy2Di 12y ago
Related, this came up in yesterday's thread about Graham's number: http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt https://news.ycombinator.com/item?id=9054274 https://news.ycombinator.com/item?id=9054274

by gglon 12y ago

deleted 12y ago

[deleted]

deleted 12y ago
[deleted]

swatow 12y ago

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).

cousin_it 12y ago
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).

deleted 12y ago

[deleted]

yepguy 12y ago

My solution in brainfuck, given a finite tape: -[>-]-

evanb 12y 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 https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation

evanb 12y ago
I just realized 99 should be replaced with "9!".
- evanb 12y 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 12y 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[#!&][#][#]&)

leohutson 12y ago

num = 0; while (true) { try { num++; } except ( mallocFail ) { return num; } }

Gurkenmaster 12y ago
Just do -1 on an unsigned number if you're that lazy.

throwaway_yy2Di 12y ago

Related, this came up in yesterday's thread about Graham's number: http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt https://news.ycombinator.com/item?id=9054274 https://news.ycombinator.com/item?id=9054274