14 ms·

Who Can Name the Bigger Number?

223 points by jeremynixon 12y ago

infogulch 12y ago
"If you want to use higher-level Busy Beavers in the biggest number contest, here’s what I suggest. First, publish a paper formalizing the concept in some obscure, low-prestige journal." I wonder if anyone has followed through with this?
deleted 12y ago
[deleted]
trishume 12y ago
I really enjoyed this article, it touches on so many different areas of math and computer science and connects them in interesting ways.
codeflo 12y ago
Here's a philosophical question that's been bothering me for a while. For large enough n, we can construct an n-state Turing machine that attempts to prove a contradiction in our current most powerful axiomatic system (let's say ZFC). We must assume that this machine loops forever, but Gödel's incompleteness theorem implies that we can't prove that. What does this construction imply about BB(n)? In what sense is the BB sequence even well-defined if we can prove that it can't be determined? (Edited for clarity.)
- curryhoward 12y ago
  > For large enough n, we can construct a Turing machine that attempts to prove a contradiction in our current most powerful axiomatic system (let's say ZFC). What is n in this construction?
  - codeflo 12y ago
    I'm sorry, n was supposed to be the number of states of the Turing machine. I've clarified the original post.
- zodiac 12y ago
  The article does mention that "no Turing machine can list the Busy Beaver numbers".
  - codeflo 12y ago
    That's clear. My point is that mathematics can't list the Busy Beaver machines.
    - evanb 12y ago
      > In what sense is the BB sequence even well-defined if we can prove that it can't be determined? Every BB number can be determined. However, each one must require zillions of special cases which require their own reasoning---this is the only way to prevent the BB numbers from being computable. So, if you consider, for example, the proof of the four-color theorem (which amounts to checking many special cases), as mathematics, then mathematics surely can determine BB(n). It's just extremely hard---as hard as doing all of mathematics (in the sense that if you could easily get BB(n) you could then take a logical proposition you are interested in proving in some axiomatic system and construct a TM to derive the statement using those axioms. Then, count how many states that TM has, and start running it. If it runs for more than BB(# states), there is no proof from your system of your proposition).
      - qmalxp 12y ago
        I think it is possible, in principle, to find a number which you can be pretty sure is BB(n). The problem I think is being sure that this number really is BB(n). Like you run all n-state Turing Machines for a super long time, and take the max of the output of all the ones that have halted. Now this might give you BB(n), but you can't be sure because you don't know whether the ones that haven't halted are ever going to halt. In mathematics, we can just say "Well consider the set of all the ones that do halt, and take their max." In real life, it's not so easy to "consider the set".
        lmm 12y ago
        You don't just wait, you prove that they all don't halt. There are only finitely many of them. You can't provide a general algorithm for proving that Turing machines don't halt, each one is going to require a special case - but it will be a fact that the physical instance of the machine halts or doesn't halt. (Or if it halts in some models of ZFC but not others, that would be even more interesting).
- Retra 12y ago
  >We must assume that this machine loops forever We must assume this machine would loop forever, it it operated on only the rules of ZFC, because we assume ZFC is consistent. A real machine cannot loop forever, and it would be unreasonable to assume that it does. Real machines are not known to operate based solely on the rules of ZFC. ZFC is only an approximation.
- jbapple 12y ago
  > In what sense is the BB sequence even well-defined if we can prove that it can't be determined? I think it may help you to understand how the BB sequence can be well-defined if you change your definition of "we can prove". A proof is a sequence of logical deductions in an axiomatic system, so what "we can prove" depends a lot on which axiom system you're using. For some types of questions, it helps to make that explicit. For instance, in weak axiom systems, we can't prove that every hydra game terminates. [0] In very strong axiom systems, ones so strong we call them inconsistent, we can prove everything! People argue over intermediate systems sometimes by pointing out things they can prove that are counter-intuitive. [1][2] For any terminating Turing machine, there is a (possibly very long) proof in a very weak axiom system of that fact: the full trace of the execution. (For non-terminating machines, this is not true.) So, if ZFC, a rather strong axiom system, cannot prove a machine halts, it does not halt. For another example of this kind of thing, see Terry Tao's discussion of the consequences of the independence of Goldbach's conjecture from ZFC on MathOverflow. [3] [0] https://en.wikipedia.org/wiki/Goodstein%27s_theorem https://en.wikipedia.org/wiki/Goodstein%27s_theorem [1] https://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry https://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry [2] https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [3] http://mathoverflow.net/a/27764 http://mathoverflow.net/a/27764
  - fbastiat 12y ago
    But if the machine that stops when it has proven ZFC is inconsistent does not halt, then surely it means there is no proof of the inconsistency of ZFC? Hence ZFC is consistent? Which is contradicted by Godel. I would think instead ZFC can't prove or disprove that this machine halts, which just means it's undecidable wether it halts or not. This also implies that for sufficiently large n, we won't be able to prove that BB(n) = N, or even BB(n) < N for any N using the ZFC axioms. Of course, although they can't compute or bound its value, they can still easily prove that BB(n) is finite.
    - fbastiat 12y ago
      I think this[0] is a good formalization of what I'm trying to say. [0] http://math.stackexchange.com/a/614017/215039 http://math.stackexchange.com/a/614017/215039
- qmalxp 12y ago
  This kind of thing happens in math a lot. Any time you use the axiom of choice to prove something exists, it's non-constructive. It exists, but you can't get your hands on it. I wrote a comment down below about how one could in principle determine a number which is probably BB(n), but you could never be sure. But I just had the crazy thought that if a human brain is really just an N-state Turing machine for some giant N, then any human would either wait forever or give up before finding the true BB(n) for some n. Time for bed!
- swatow 12y ago
  that's a good question. I think the answer is that if we could prove BB(n) = K, then we just have to run this turing machine for K iterations, and either it finds a contradiction, or it doesn't. In the latter case, we have proven that ZFC has no contradiction, and so by Godel's theorem, it has a contradiction. From this it follows (by proof by contradiction!) that BB(n) is undecidable/uncomputable (getting a bit hazy on these definitions). In any case, we cannot prove that BB(n) = K for any K. Is it a problem that for all K we cannot prove that BB(n) = K? I don't think so, this is just another incompleteness result.
- lmm 12y ago
  Everything rests on the consistency of ZFC, which we can't prove. In some sense even results like 2+2=4 are provisional, because if ZFC were inconsistent (and we can't prove that it isn't) then it might also be true that 2+2=3 and 2+2=5. (Well, strictly we can prove that 2+2=4 in Presburger arithmetic which is provably complete and consistent. But any result that we prove by contradiction and that uses the higher axioms (e.g. Hilbert's basis theorem) is implicitly assuming the (unprovable) consistency of ZFC). Mostly this doesn't bother working mathematicians - ZFC seems reasonable, corresponds to the models that we do have, so we just take it on trust. People who care explicitly about these issues might work in a "higher" axiom system to prove "metamathematical" facts (e.g. ZFC + weakly inaccessible large cardinal, under which we can prove that ZFC is consistent and also that this particular Turing machine doesn't halt). ((Of course the whole point of Gödel's incompleteness theorems is that there's no sharp line between mathematical and metamathematical; any unproven proposition might turn out to be an unprovable landmine. But this doesn't tend to bother people. After all, the proposition might just as easily turn out to simply be very difficult to prove, and the practical impact would be much the same))
tux3 12y ago
Loved this article, I'm really interested by the BB numbers in particular and how they relate to the halting problem. And I though I could win this silly game with my Knuth's Up Arrow notation and vague knowledge of Ackermann's sequence!
- iopq 12y ago
  BB(6) could be bigger than Graham's number but we don't even know, that's how big it is the busy beaver function grows so fast that for some number N it's always going to be larger than any number we can describe in normal math notation so if you define Graham's number as a function of N like g(N) where Graham's number is g(64), busy beaver still grows faster and for some N it will be bigger
baddox 12y ago
> Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature. Does this mean that the modern mathematician must be able to assemble all the digits of the number's representation (say, in decimal)? Given some formalization of this requirement, there would be a fairly set upper bound on the acceptable integers.
- baddox 12y ago
  It occurs to me that you could formalize the requirement by saying that there must be a provably terminating algorithm that produces precisely the decimal representation of the integer. That way, numbers like Graham's number can be submitted despite there being no physical way to represent the number in decimal (in the observable Universe).
  - gizmo686 12y ago
    Does the algorithm need to terminate? It seems like convergence would be sufficient. For example, we have no terminating algorithm to produce pi, but we have plenty of ways to precisly express it. Of course, given the nature of this problem, you can define your converging algorithm to terminate when it is withing a certain error of what the "pure" answer would be. Of course, it is possible you would underestimate the number, and if someone could beet you by using the same method with a slightly different termination condition, so you may want to add 1...
    - baddox 12y ago
      Good point, although this problem involves only integers, so I'm not sure if "convergence" makes sense. Pi, of course, is a computable number, implying that there is a terminating algorithm that, given input n, outputs the nth digit of pi's decimal representation.
- j2kun 12y ago
  Determining something exactly does not mean providing its digits. It means uniquely identifying the semantic meaning of an expression. As an analogy, you can know what a word means when it's spoken to you even if you can't spell it. Or you can understand what a program written down on paper computes (and prove that it computes that thing) without knowing the explicit output of a particular input.
meric 12y ago
If BB is the highest paradigm published, and it is assumed BB numbers, given enough time and resources, can be computed, and you can't use BB2, why can't you simply go: BB(BB(BB(BB(BB(11111))))) Repeat as many BB's as you have space on your 1000 character card. You might even use math notation to define a new function where BB-(n) = [BB(BB(.......] <---- n -----> And then you might have: BB-(BB-(BB-(1111)))(BB-(BB-(BB-(1111)))(11111)) Or some such monstrosity.
- TheEzEzz 12y ago
  The logical conclusion of this is considering all general computations that can be done with a BB calculator in hand, which leads you to the hyper BB numbers that he refers to, or BB_2.
  - meric 12y ago
    I got the idea his BB_2 is different. He's referring to a super Turing machine that can solve the halting problem for non-super Turing machines. The BB-2 used in an iterative algorithm is talking about "A busy beaver number of (A busy beaver number of 10)", no need for super machines here. The iterative algorithm is short enough you can define it in your 1000 characters, no need for additional publication.
    - zeeboo 12y ago
      But the super Turing machines busy beaver numbers vastly outgrow your iterated busy beaver very quickly. It doesn't take that many states to write a program that can do an iterated function application, and to a super Turing machine, it's easy to write the busy beaver function.
      - meric 12y ago
        OK, but as the article states you'll have to write a paper to a low-level journal to use it, and I'd have to be really into and good at mathematics to consider doing exactly that to win a name-the-biggest-number competition...
JoshTriplett 12y ago
It seems notable that so many different variations of "naming large numbers" all end up mapping iterated applications of a function into a new function that takes a number of iterations as a parameter. Knuth's up-arrow notation defines iterated exponentiation, iterated iterated exponentiation, and so on. Ackermann's function makes the number of up-arrows just a numeric parameter to the function. But you could go further than that: A(A(10)) is much bigger than A(1000), so you can get larger numbers faster by iterated applications of the Ackermann function. Turn the iteration into a function, and let B(n) be n applications of A to n. Iterated application of B would be even faster, so turn that iteration into a function: let C(n) be n applications of B to n. But this process itself is iterative. So, define a new function: let iterA(n) be the nth level of iterated Ackermann functions applied to n, where iterA(1) is A(1), iterA(2) is B(2), iterA(3) is C(3), and so on. Now, iterA can be applied iteratively. So, repeat again. The resulting function can be applied iteratively, so repeat again. And this whole process of turning iteration into a function and then iterating that function is itself an iterative process, so it can be turned into a function...
- meric 12y ago
  So the competition is not really to name the biggest number but rather to write the deepest iterator in 1000 characters and apply it to the highest paradigm function. More like a programmer's challenge. Let A = {fastest published sequence}. # This is a macro for BB, Ackermann's, etc. Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^10(A, 10)
  - cousin_it 12y ago
    IMO you can't win big number competitions by such a low-level approach. At least notice that the concept of "deepest iterator in 1000 characters" is itself mathematically definable, and define it as D(1000) or something. Then try to find connections between that and BB numbers... Coming up with the "highest paradigm function" is the important part of the challenge, iteration is unnoticeable by comparison.
- ccvannorman 12y ago
chacham15 12y ago
> Take 9^9^9, for example. This behemoth, equal to 9^387,420,489 ...if the author is here, he should correct this.
- maxsherman 12y ago
  9^(9^9) = 9^387,420,489
- primitivesuave 12y ago
  Exponentiation is right associative.
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
mcherm 12y ago
One of my favorite articles... well worth the re-read even if (as I have) you have seen it before. You may notice something you had forgotten, as I had forgotten the existence of the "busy-beaver-like-function" for machines more powerful than Turing machines.
swatow 12y ago
Mathematician Edward Nelson has a very interesting take on "big" numbers. He claims that the exponential function is not necessarily total, and a number like 2^1000000000000 might not actually exist. The reason he singles out exponentiation is that the reasoning that exponential numbers are "real" numbers, is circular (impredicative). According to Nelson, speaking about such numbers might lead to condradictions, just like speaking about "the set of all sets that don't contain themselves" leads to a contradiction. He also relates these issues to Christian philosophy, which I find very interesting. In particular, he claims that the a priori belief in the objects defined by Peano Arithmetic, is equivalent to worshipping numbers, as the Pythagoreans did. I think this is the best starting point if you're interested in reading about his ideas: https://web.math.princeton.edu/~nelson/papers/warn.pdf https://web.math.princeton.edu/~nelson/papers/warn.pdf
- hellbanner 12y ago
  I'll read the paper, it sounds interersting. But isn't all Math "circular" -- Goedels Second Incompleteness Theorem yeah? http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems#Implications_for_consistency_proofs http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_the...
  - swatow 12y ago
    Goedel's incompleteness theorem uses Peano Arithmetic, which Nelson claims is (possibly) inconsistent. He develops his own "predicative" arithmetic, to which Goedel's theorem does not apply. (large pdf) https://web.math.princeton.edu/~nelson/books/pa.pdf https://web.math.princeton.edu/~nelson/books/pa.pdf
    - hellbanner 12y ago
      I'll read it, thanks. I always (layman) understood Goedel's theorem as meaning you can be complete or consistent but not both. So you can have a language that can describe everything but you'll have paradoxes, or you'll have no paradoxes but not be able to describe everything (all possibilities) in your system
sixQuarks 12y ago
Here is the most entertaining article I've ever read about large numbers: http://waitbutwhy.com/2014/11/1000000-grahams-number.html http://waitbutwhy.com/2014/11/1000000-grahams-number.html
lifthrasiir 12y ago
xkcd forum has an interesting (and longish) thread playing this exact game. [1] Starting with nine thousands, it quickly becomes a mathematical nightmare or something. And also, the Big Number Duel. [2] [1] http://forums.xkcd.com/viewtopic.php?t=7469 http://forums.xkcd.com/viewtopic.php?t=7469 [2] http://tech.mit.edu/V126/N64/64largenumber.html http://tech.mit.edu/V126/N64/64largenumber.html
- cousin_it 12y ago
  Also see this mathoverflow post by Scott Aaronson as a follow-up to the article: http://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver http://mathoverflow.net/questions/34710/succinctly-naming-bi...
panic 12y ago
There was a contest to produce programs generating large numbers in a version of C with integral types that hold arbitrarily-large integers: http://djm.cc/bignum-rules-posted.txt http://djm.cc/bignum-rules-posted.txt You can see the results here: http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt -- there's some interesting stuff in there!
- cousin_it 12y ago
  Yeah, that was a great contest as well. Though the numbers involved are necessarily much smaller than even the BB numbers, because they must be computable. Also see this old HN discussion where Eliezer proposed a good way to beat the winner: https://news.ycombinator.com/item?id=1542770 https://news.ycombinator.com/item?id=1542770
viraptor 12y ago
I don't get why the BB(x) numbers should grow faster than A(x). They're harder to compute - true. They're more difficult to prove right - true. But I cannot find anything in the article that proves it actually grows faster than Ackerman numbers. Unless you can always program A(x) in less than x steps on a Turing machine?
- j2kun 12y ago
  No, BB is impossible to compute (as a sequence, that is). A(x) is not.
  - viraptor 12y ago
    It's impossible to compute them - sure. But the claim was that: "The sequence of Busy Beaver numbers, BB(1), BB(2), and so on, grows faster than any computable sequence." The explanation was that: "Because if a Turing machine could compute a sequence that grows faster than Busy Beaver, then it could use that sequence to obtain the D‘s—the beaver dams." But these goals seem different to me. Another sequence you cannot compute is "foo(x)" - the number of integers lower than x for which algorithm "bar(x)" doesn't halt. It's impossible to compute if "bar(x)" doesn't always halt. But the sequence cannot grow faster than "x" itself. Also, it doesn't matter that you cannot compute them if every TM of a given size can be analysed and proven halting. It doesn't have to be computed (as in, automatically checked). The fact you can compute A(x) would only be an issue if you could compute A(x) with a machine of size smaller than x.
    - j2kun 12y ago
      I think you are missing some basic concepts here. There is a single Turing machine (of constant size) which, when given any integer n, outputs A(n). This is the statement that A(n) is computable. One can prove that there is no such Turing machine for the function BB(n) or any function f(n) that bounds BB(n). Such a function would be used to solve the Halting problem as follows: given a TM M and a string x, compute k = f(|M|) and run the TM on x for k steps. If the simulation halts within k steps, output "halt" and otherwise output "loops forever." Your example of foo/bar(x) is not quite correct. If you fix a program bar, then it is not necessarily impossible to characterize (and hence compute) the set of strings for which bar(x) halts. This is not the statement of the Halting problem, and as far as I know there is no theorem that says such a function "bar" exists.
crayola 12y ago
Why not mention factorials? 9!! is way bigger than 9^9^9. And you can write many exclamation marks in 15 seconds.
- vacri 12y ago
  Wow, 9!! is so large that the exponent almost needs it's own exponent. 9^9^9 =~ 2e77 9!! =~ 1.6e1859933
  - peterjmag 12y ago
    Correct me if I'm wrong, but aren't you supposed to evaluate stacked exponents from the top down? That is, 9^(9^9) instead of (9^9)^9. If that's the case, 9^(9^9) is much larger than 9!!. Though I'm not sure how much larger, since I couldn't find any big integer calculators online that would give me an actual result for 9^(9^9).
    - cradle 12y ago
      9^(9^9) is ... wait for it... 4e369693099 bigger than 9!! http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+9%21%21 http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+9%21%21
      - peterjmag 12y ago
        Ah thanks! How could I forget Wolfram Alpha? =)
      - BhavdeepSethi 12y ago
        Shouldn't it be (9!)!? http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+%289%21%29%21 http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+%289%21%29%...
    - vacri 12y ago
      It seems you're correct - I was just pounding the values in sequence into a calculator, much like a determined monkey would.
speakeron 12y ago
If you're interested in big numbers, David Metzler's "Ridiculously huge numbers" sequence on youtube (https://www.youtube.com/watch?v=QXliQvd1vW0 https://www.youtube.com/watch?v=QXliQvd1vW0) is well worth a watch. He gives great explanations of things like the Conway chained arrow notation and the fast-growing hierarchy and just keeps on making bigger and bigger numbers.
dmichulke 12y ago
Given the other comments I wonder whether the Meta-Algorithm for big numbers is basically: Compose a state space that expands as quickly as possible in terms of the argument(s) and define some property of the state space as the result. Looking at it this way, I'd say: "Hyper-exponentiation" (Ackermann, tetration and so on) is basically counting the number of states in a well-defined state space. BB(X) is equivalent to generating automatically the state space (via a search over all possible state spaces that can be constructed with a TM with X states) and returning the size of the maximum. This means that BB(X) is smaller than the sum of the sizes of all possible state spaces constructible via that TM. But BB(X+1) is aware of that trick (summing state space sizes) and uses it already (or more probably something better), so it doesn't really matter and you might as well just increase X by one to include all the tricks you had in mind for BB(X). Anyone thoughts on that?
- cousin_it 12y ago
  BB_2(X) uses a different trick. It asks for the largest number computable by any program of length X that's allowed to call a BB oracle with arbitrary arguments. That's more powerful than any finite expression involving BB and computable functions, like BB(F(X)), BB(F(BB(X))), etc. More generally, I expect there to not be any "meta-algorithm" for naming big numbers. Every big step will require a new insight. A similar problem is inventing notations for large ordinals: http://en.wikipedia.org/wiki/Ordinal_notation http://en.wikipedia.org/wiki/Ordinal_notation
  - Veedrac 12y ago
    I looked it up and this page showed up: http://web.mit.edu/nelhage/Public/big-number.txt http://web.mit.edu/nelhage/Public/big-number.txt. Pretty interesting.
im3w1l 12y ago
Take number theorethic conjecture. Look for counterexamples. Return first counterexample. You can't prove I didn't win!
yyhhsj0521 12y ago
9!!!!!!....!! factorial
- jhonnycano 12y ago
  9!!!!!!....!! + 1
GotAnyMegadeth 12y ago
When I was around 14 years old I was baby sitting a kid who was 3 or 4 or something. He came up to me and said "I bet I can say a bigger number than you." clearly proud of what he had just learnt in preschool. I accepted the challenge, he took a deep breath and said "Five hundred!", so I said "Five hundred and one". He looked determined and said "Ok then! Five hundred and fifty hundred and five hundred million hundred five hundred" (Or something that makes no sense like that). So I said "Five hundred and fifty hundred and five hundred million hundred five hundred, and one". He looked horrified and said "Can you just say 'and one' for any number?" I told him yes, and he said "Cool!".
- poizan42 12y ago
  And every since has that poor kid believed that "Five hundred and one and one" was a valid number.
  - Xophmeister 12y ago
    It kind-of-is, it's just not particularly well-formed/ambiguous linguistically.
    - GotAnyMegadeth 12y ago
      A bit like 99 in French: quatre-vingt-dix-neuf four twenties and ten and nine
      - eitland 12y ago
        I knew the Danes where counting in a crazy way but I didn't know the French did this as well. One more reason I'm happy English is the most common international language I guess.
        iak8god 12y ago
        According to wikitionary [1] "four score and seven" was a commonplace way of saying "eighty seven" in 19th c. English. [1] https://en.wiktionary.org/wiki/four_score_and_seven_years_ago https://en.wiktionary.org/wiki/four_score_and_seven_years_ag...
im3w1l 12y ago
Ok, I think I may have the ultimate answer to this, a sequence that grows optimally fast. It goes like this: Imagine 2^(7n) copies of the judge of this competition. For every judge create a different bit sequence of length 7n. Decode it from ascii and ask if it is a valid entry of the competition. Take the largest valid entry of those imaginary competitions. That is my entry. In order for this procedure to be consistent, this entry must be longer than n characters. Hence it will end with some padding you may disregard: asdfasdfasdfasdfasdfasdfasdfasdfasdfasdf.
- cousin_it 12y ago
  If you're allowed to submit entries that are mutually recursive with the decision procedure of the judges, I'm afraid the competition becomes less well defined. For example, it's easy to create a paradoxical entry by adding 1 to your entry. Also see Berry's paradox: http://en.wikipedia.org/wiki/Berry_paradox http://en.wikipedia.org/wiki/Berry_paradox
  - im3w1l 12y ago
    Yeah, I agree that it becomes less well defined. The problem with Berry's paradox is that it refers to itself. I circumvented paradox, by only refering to shorter descriptions of the number, than the description I gave. If that strategy works really depends on what the judge thinks though. Assuming he accepts refering to his own potential judgements of shorter sequences but not longer or equally long, the solution would work and the rules would be paradox free.
    - cousin_it 12y ago
      Yeah, that might avoid paradox at the cost of requiring a specific kind of judge. But then I think you need to fully specify the judge's reasoning, and that's a very difficult problem, it might be even AI-complete. I don't know of any computer program that would be able to judge the descriptions of current winning entries. Maybe this quote from the googology wiki will set you on a more productive track: Googologists generally avoid many of the common responses such as "infinity," "anything you can come up with plus 1," "the largest number that can be named in ten words," "the largest number imaginable," "a zillion," "a hundred billion trillion million googolplex" or other indefinite, infinite, ill-defined, or inelegant responses. Rather googologists are interested in defining definite numbers using efficient and far reaching structural schemes, and don't attempt to forestall the unending quest for larger numbers, but rather encourage it. So perhaps a more accurate description of the challenge is: "What is the largest number you can come up with using the simplest tools?" http://googology.wikia.com/wiki/Googology#History http://googology.wikia.com/wiki/Googology#History
chinpokomon 12y ago
I have been thinking about this problem for a year or so now. I was introduced to the concept watching a Numberphille video and several hours later read this article. I've been taking a somewhat metaphysical approach to thinking about it. Instead of thinking about a Turing Machine as just a head on an endless tape, can we not consider the Universe to represent the upper limits for our calculations? Just as Turing suggested that we can take the two dimensional representation of a mathematical equation and represent it in one dimension, can we represent the entire state of the Universe in a similar way on a hypothetical Turing Machine? The halting problem is then a question of whether or not the Universe has a halting state. To extend from that, any machine that can be conceived must fit within the bounds of the Universe. Of course BB(Universe) is incalculable, but I think that it defines an upper limit. It is pointless to consider a Turing Machine that features an endless tape if an endless tape is an impossibility. In not sure if this adds to the discussion, but I haven't had anyone else I could discuss this with until now.
- simonh 12y ago
  By postulating an endless tape you're just stalling petty objections based on how long a tape would be required for any given task. The only point that's relevent, when considering Turing machines in the abstract, is that the amount of tape required for any given task be finite.
- bjackman 12y ago
  I suspect a physicist would say you're idea rests on an a view of the universe where everything is deterministic and knowable and encodable. You also have to remember that some quantities are going to be continuous, while TMs are discrete. Even an "infinite" TM can't truly encode real numbers (I think) because its infinity is of the countable variety, while Real numbers are uncountably infinite.
  - chinpokomon 12y ago
    True, I am making an assumption that it is deterministic. If we presume that the Big Bang model of the Universe is true, then in the earliest moment of time, can the state of the Universe be measured? If it can be measured, how does it transition from a measurable state to an immeasurable one? I'll have to give some more thought to what you've said, but I wanted to give you a basis for why I believe it could be deterministic. Clearly I'm making some assumptions, and based on my postulate, this is a state that we could never measure ourselves. I don't know if our inability to make these measurements removes the possibility of determinism.
jbb555 12y ago
I would argue that 9^9 mentioned in the article for example _is not a number_. It is a method for calculating a number. So most of the article is invalid
- ubercow13 12y ago
  So is 387420489. The method goes, first you take 9, then you multiply 8 by 10 and add that to 9, then you multiply 4 by 100 and add that to what you have...
- peteretep 12y ago
  It's a notation, not a formula
- scott_s 12y ago
  You're probably viewing it as a programmer. You see the exponentiation operator, which to you means "computation", which implies some "work" must occur to get the "real" number out of the calculation. As far as a mathematician is concerned, there is no difference between 9^9, 387420489, 387420499 - 10, 774840978 / 2, or 193710244.5 * 2. They all represent the same quantity. That some are not in their fully reduced form does not change that they are unambiguous representations of the same number. Even if you are unable to see it that way, we can easily rephrase the exercise to be "write down a way to compute the largest number you can in 15 seconds". This is an enlightening mental exercise, it would be silly to dismiss it for such trivial reasons.
stillsut 12y ago
Is there some N such that BB(N) can produce any "arbitrarily large" number? Not infinity because that would mean it doesn't halt, but that there is no number which can not be exceeded by saying in effect "plus 1". Or, as N becomes large and can emulate the english language use berry's paradox style algorithm to show there is no limit to what size you want. Another approach would be to use a probability-based event for halting, and so it is always possible that a series of coin flips could keep coming up heads 1,000,000 times in a row, or a zillion times, see: st. petersburg paradox.
- j2kun 12y ago
  >Is there some N such that BB(N) can produce any "arbitrarily large" number? Not infinity because that would mean it doesn't halt, but that there is no number which can not be exceeded by saying in effect "plus 1". This would imply BB(n) is not well defined. To the contrary, BB(n) is finite for every n.
ttctciyf 12y ago
As an adjunct to this, if large numbers interest you there's a really excellent and long-standing set of pages about them at http://www.mrob.com/pub/math/largenum.html http://www.mrob.com/pub/math/largenum.html which has some fascinating incidental detail and covers infinities as well as large finite numbers.
chanandler_bong 12y ago
Name it? Sure - I will call it "Bob". What Bob's value is, I have no idea.
qrendel 12y ago
1) My submission: modifying Ackermann's function to describe a sequence of Busy Beaver numbers of sequential hypercomputation systems. E.g. ABB(n+1) = BB_n(n) Of course it's the same problem, you could just as easily do AABB(n+1) = ABB_n(n), but still grows faster than a Busy Beaver sequence for any single level of the hypercomputation hierarchy. 2) Question: I understand the argument for noncomputability of Busy Beavers given, but couldn't you just argue that BB(n) is finite, therefore BB(n) is a computable sum of 1+1+...+1, therefore BB(n) is computable given a finite amount of time, so any given number in the sequence is itself computable, therefore by mathematical induction all elements in the sequence are computable? Clearly not, but I don't understand why this doesn't work.
- cousin_it 12y ago
  1) If you're aware of the BB_n hierarchy, you've outgrown the need for recursion tricks. Instead, talk about halting times of programs that can make calls to the oracle F(n,m)=BB_n(m). That leaves any Ackermann-like approach in the dust. I leave it to you to come up with an even better approach (yes, it exists, and then there's one or two levels after that). Please don't say "I'll just use Ackermann on top of your idea", at that level it's the moral equivalent of "your number plus one". 2) For each individual BB number, there's a program that prints it. But there's no program that prints the whole infinite sequence of BB numbers one by one. All finite sequences are computable, but not all infinite sequences are.
- mstoehr 12y ago
  To say that the sequence is computable means that you must present a Turing machine, call it T, that will produce BB(n) in finitely many steps after taking input n. Our specific Turing machine T will have a fixed number of rules call it N rules, then by the definition of the Busy Beaver T(N+1) <= BB(N) = T(N) but BB(N+1) > BB(N) so T(N+1) does not compute BB(N+1). The flaw in your inductive proof is that you have shown there is a Turing machine that can compute BB(N) for each N, but you haven't shown that the same Turing machine can compute all numbers in the sequence.
  - qrendel 12y ago
gesman 12y ago
1/0-1 I won! :-P (because infinity is not allowed, so i had to subtract one)
Randgalt 12y ago
24 is the highest number: https://www.youtube.com/watch?v=RkP_OGDCLY0 https://www.youtube.com/watch?v=RkP_OGDCLY0

223 points by jeremynixon 12y ago

"If you want to use higher-level Busy Beavers in the biggest number contest, here’s what I suggest. First, publish a paper formalizing the concept in some obscure, low-prestige journal." I wonder if anyone has followed through with this?

deleted 12y ago

[deleted]

trishume 12y ago

I really enjoyed this article, it touches on so many different areas of math and computer science and connects them in interesting ways.

codeflo 12y ago

Here's a philosophical question that's been bothering me for a while. For large enough n, we can construct an n-state Turing machine that attempts to prove a contradiction in our current most powerful axiomatic system (let's say ZFC). We must assume that this machine loops forever, but Gödel's incompleteness theorem implies that we can't prove that. What does this construction imply about BB(n)? In what sense is the BB sequence even well-defined if we can prove that it can't be determined? (Edited for clarity.)

curryhoward 12y ago
> For large enough n, we can construct a Turing machine that attempts to prove a contradiction in our current most powerful axiomatic system (let's say ZFC). What is n in this construction?
- codeflo 12y ago
  I'm sorry, n was supposed to be the number of states of the Turing machine. I've clarified the original post.
zodiac 12y ago
The article does mention that "no Turing machine can list the Busy Beaver numbers".
- codeflo 12y ago
  That's clear. My point is that mathematics can't list the Busy Beaver machines.
  - evanb 12y ago
    > In what sense is the BB sequence even well-defined if we can prove that it can't be determined? Every BB number can be determined. However, each one must require zillions of special cases which require their own reasoning---this is the only way to prevent the BB numbers from being computable. So, if you consider, for example, the proof of the four-color theorem (which amounts to checking many special cases), as mathematics, then mathematics surely can determine BB(n). It's just extremely hard---as hard as doing all of mathematics (in the sense that if you could easily get BB(n) you could then take a logical proposition you are interested in proving in some axiomatic system and construct a TM to derive the statement using those axioms. Then, count how many states that TM has, and start running it. If it runs for more than BB(# states), there is no proof from your system of your proposition).
    - qmalxp 12y ago
      I think it is possible, in principle, to find a number which you can be pretty sure is BB(n). The problem I think is being sure that this number really is BB(n). Like you run all n-state Turing Machines for a super long time, and take the max of the output of all the ones that have halted. Now this might give you BB(n), but you can't be sure because you don't know whether the ones that haven't halted are ever going to halt. In mathematics, we can just say "Well consider the set of all the ones that do halt, and take their max." In real life, it's not so easy to "consider the set".
      - lmm 12y ago
        You don't just wait, you prove that they all don't halt. There are only finitely many of them. You can't provide a general algorithm for proving that Turing machines don't halt, each one is going to require a special case - but it will be a fact that the physical instance of the machine halts or doesn't halt. (Or if it halts in some models of ZFC but not others, that would be even more interesting).
Retra 12y ago
>We must assume that this machine loops forever We must assume this machine would loop forever, it it operated on only the rules of ZFC, because we assume ZFC is consistent. A real machine cannot loop forever, and it would be unreasonable to assume that it does. Real machines are not known to operate based solely on the rules of ZFC. ZFC is only an approximation.
jbapple 12y ago
> In what sense is the BB sequence even well-defined if we can prove that it can't be determined? I think it may help you to understand how the BB sequence can be well-defined if you change your definition of "we can prove". A proof is a sequence of logical deductions in an axiomatic system, so what "we can prove" depends a lot on which axiom system you're using. For some types of questions, it helps to make that explicit. For instance, in weak axiom systems, we can't prove that every hydra game terminates. [0] In very strong axiom systems, ones so strong we call them inconsistent, we can prove everything! People argue over intermediate systems sometimes by pointing out things they can prove that are counter-intuitive. [1][2] For any terminating Turing machine, there is a (possibly very long) proof in a very weak axiom system of that fact: the full trace of the execution. (For non-terminating machines, this is not true.) So, if ZFC, a rather strong axiom system, cannot prove a machine halts, it does not halt. For another example of this kind of thing, see Terry Tao's discussion of the consequences of the independence of Goldbach's conjecture from ZFC on MathOverflow. [3] [0] https://en.wikipedia.org/wiki/Goodstein%27s_theorem https://en.wikipedia.org/wiki/Goodstein%27s_theorem [1] https://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry https://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry [2] https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox https://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox [3] http://mathoverflow.net/a/27764 http://mathoverflow.net/a/27764
- fbastiat 12y ago
  But if the machine that stops when it has proven ZFC is inconsistent does not halt, then surely it means there is no proof of the inconsistency of ZFC? Hence ZFC is consistent? Which is contradicted by Godel. I would think instead ZFC can't prove or disprove that this machine halts, which just means it's undecidable wether it halts or not. This also implies that for sufficiently large n, we won't be able to prove that BB(n) = N, or even BB(n) < N for any N using the ZFC axioms. Of course, although they can't compute or bound its value, they can still easily prove that BB(n) is finite.
  - fbastiat 12y ago
    I think this[0] is a good formalization of what I'm trying to say. [0] http://math.stackexchange.com/a/614017/215039 http://math.stackexchange.com/a/614017/215039
qmalxp 12y ago
This kind of thing happens in math a lot. Any time you use the axiom of choice to prove something exists, it's non-constructive. It exists, but you can't get your hands on it. I wrote a comment down below about how one could in principle determine a number which is probably BB(n), but you could never be sure. But I just had the crazy thought that if a human brain is really just an N-state Turing machine for some giant N, then any human would either wait forever or give up before finding the true BB(n) for some n. Time for bed!
swatow 12y ago
that's a good question. I think the answer is that if we could prove BB(n) = K, then we just have to run this turing machine for K iterations, and either it finds a contradiction, or it doesn't. In the latter case, we have proven that ZFC has no contradiction, and so by Godel's theorem, it has a contradiction. From this it follows (by proof by contradiction!) that BB(n) is undecidable/uncomputable (getting a bit hazy on these definitions). In any case, we cannot prove that BB(n) = K for any K. Is it a problem that for all K we cannot prove that BB(n) = K? I don't think so, this is just another incompleteness result.
lmm 12y ago
Everything rests on the consistency of ZFC, which we can't prove. In some sense even results like 2+2=4 are provisional, because if ZFC were inconsistent (and we can't prove that it isn't) then it might also be true that 2+2=3 and 2+2=5. (Well, strictly we can prove that 2+2=4 in Presburger arithmetic which is provably complete and consistent. But any result that we prove by contradiction and that uses the higher axioms (e.g. Hilbert's basis theorem) is implicitly assuming the (unprovable) consistency of ZFC). Mostly this doesn't bother working mathematicians - ZFC seems reasonable, corresponds to the models that we do have, so we just take it on trust. People who care explicitly about these issues might work in a "higher" axiom system to prove "metamathematical" facts (e.g. ZFC + weakly inaccessible large cardinal, under which we can prove that ZFC is consistent and also that this particular Turing machine doesn't halt). ((Of course the whole point of Gödel's incompleteness theorems is that there's no sharp line between mathematical and metamathematical; any unproven proposition might turn out to be an unprovable landmine. But this doesn't tend to bother people. After all, the proposition might just as easily turn out to simply be very difficult to prove, and the practical impact would be much the same))

tux3 12y ago

Loved this article, I'm really interested by the BB numbers in particular and how they relate to the halting problem. And I though I could win this silly game with my Knuth's Up Arrow notation and vague knowledge of Ackermann's sequence!

iopq 12y ago
BB(6) could be bigger than Graham's number but we don't even know, that's how big it is the busy beaver function grows so fast that for some number N it's always going to be larger than any number we can describe in normal math notation so if you define Graham's number as a function of N like g(N) where Graham's number is g(64), busy beaver still grows faster and for some N it will be bigger

baddox 12y ago

> Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature. Does this mean that the modern mathematician must be able to assemble all the digits of the number's representation (say, in decimal)? Given some formalization of this requirement, there would be a fairly set upper bound on the acceptable integers.

baddox 12y ago
It occurs to me that you could formalize the requirement by saying that there must be a provably terminating algorithm that produces precisely the decimal representation of the integer. That way, numbers like Graham's number can be submitted despite there being no physical way to represent the number in decimal (in the observable Universe).
- gizmo686 12y ago
  Does the algorithm need to terminate? It seems like convergence would be sufficient. For example, we have no terminating algorithm to produce pi, but we have plenty of ways to precisly express it. Of course, given the nature of this problem, you can define your converging algorithm to terminate when it is withing a certain error of what the "pure" answer would be. Of course, it is possible you would underestimate the number, and if someone could beet you by using the same method with a slightly different termination condition, so you may want to add 1...
  - baddox 12y ago
    Good point, although this problem involves only integers, so I'm not sure if "convergence" makes sense. Pi, of course, is a computable number, implying that there is a terminating algorithm that, given input n, outputs the nth digit of pi's decimal representation.
j2kun 12y ago
Determining something exactly does not mean providing its digits. It means uniquely identifying the semantic meaning of an expression. As an analogy, you can know what a word means when it's spoken to you even if you can't spell it. Or you can understand what a program written down on paper computes (and prove that it computes that thing) without knowing the explicit output of a particular input.

meric 12y ago

If BB is the highest paradigm published, and it is assumed BB numbers, given enough time and resources, can be computed, and you can't use BB2, why can't you simply go: BB(BB(BB(BB(BB(11111))))) Repeat as many BB's as you have space on your 1000 character card. You might even use math notation to define a new function where BB-(n) = [BB(BB(.......] <---- n -----> And then you might have: BB-(BB-(BB-(1111)))(BB-(BB-(BB-(1111)))(11111)) Or some such monstrosity.

TheEzEzz 12y ago
The logical conclusion of this is considering all general computations that can be done with a BB calculator in hand, which leads you to the hyper BB numbers that he refers to, or BB_2.
- meric 12y ago
  I got the idea his BB_2 is different. He's referring to a super Turing machine that can solve the halting problem for non-super Turing machines. The BB-2 used in an iterative algorithm is talking about "A busy beaver number of (A busy beaver number of 10)", no need for super machines here. The iterative algorithm is short enough you can define it in your 1000 characters, no need for additional publication.
  - zeeboo 12y ago
    But the super Turing machines busy beaver numbers vastly outgrow your iterated busy beaver very quickly. It doesn't take that many states to write a program that can do an iterated function application, and to a super Turing machine, it's easy to write the busy beaver function.
    - meric 12y ago
      OK, but as the article states you'll have to write a paper to a low-level journal to use it, and I'd have to be really into and good at mathematics to consider doing exactly that to win a name-the-biggest-number competition...

JoshTriplett 12y ago

It seems notable that so many different variations of "naming large numbers" all end up mapping iterated applications of a function into a new function that takes a number of iterations as a parameter. Knuth's up-arrow notation defines iterated exponentiation, iterated iterated exponentiation, and so on. Ackermann's function makes the number of up-arrows just a numeric parameter to the function. But you could go further than that: A(A(10)) is much bigger than A(1000), so you can get larger numbers faster by iterated applications of the Ackermann function. Turn the iteration into a function, and let B(n) be n applications of A to n. Iterated application of B would be even faster, so turn that iteration into a function: let C(n) be n applications of B to n. But this process itself is iterative. So, define a new function: let iterA(n) be the nth level of iterated Ackermann functions applied to n, where iterA(1) is A(1), iterA(2) is B(2), iterA(3) is C(3), and so on. Now, iterA can be applied iteratively. So, repeat again. The resulting function can be applied iteratively, so repeat again. And this whole process of turning iteration into a function and then iterating that function is itself an iterative process, so it can be turned into a function...

meric 12y ago
So the competition is not really to name the biggest number but rather to write the deepest iterator in 1000 characters and apply it to the highest paradigm function. More like a programmer's challenge. Let A = {fastest published sequence}. # This is a macro for BB, Ackermann's, etc. Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^Iterate^10(A, 10)
- cousin_it 12y ago
  IMO you can't win big number competitions by such a low-level approach. At least notice that the concept of "deepest iterator in 1000 characters" is itself mathematically definable, and define it as D(1000) or something. Then try to find connections between that and BB numbers... Coming up with the "highest paradigm function" is the important part of the challenge, iteration is unnoticeable by comparison.
ccvannorman 12y ago

chacham15 12y ago

> Take 9^9^9, for example. This behemoth, equal to 9^387,420,489 ...if the author is here, he should correct this.

maxsherman 12y ago
9^(9^9) = 9^387,420,489
primitivesuave 12y ago
Exponentiation is right associative.

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

mcherm 12y ago

One of my favorite articles... well worth the re-read even if (as I have) you have seen it before. You may notice something you had forgotten, as I had forgotten the existence of the "busy-beaver-like-function" for machines more powerful than Turing machines.

swatow 12y ago

Mathematician Edward Nelson has a very interesting take on "big" numbers. He claims that the exponential function is not necessarily total, and a number like 2^1000000000000 might not actually exist. The reason he singles out exponentiation is that the reasoning that exponential numbers are "real" numbers, is circular (impredicative). According to Nelson, speaking about such numbers might lead to condradictions, just like speaking about "the set of all sets that don't contain themselves" leads to a contradiction. He also relates these issues to Christian philosophy, which I find very interesting. In particular, he claims that the a priori belief in the objects defined by Peano Arithmetic, is equivalent to worshipping numbers, as the Pythagoreans did. I think this is the best starting point if you're interested in reading about his ideas: https://web.math.princeton.edu/~nelson/papers/warn.pdf https://web.math.princeton.edu/~nelson/papers/warn.pdf

hellbanner 12y ago
I'll read the paper, it sounds interersting. But isn't all Math "circular" -- Goedels Second Incompleteness Theorem yeah? http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems#Implications_for_consistency_proofs http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_the...
- swatow 12y ago
  Goedel's incompleteness theorem uses Peano Arithmetic, which Nelson claims is (possibly) inconsistent. He develops his own "predicative" arithmetic, to which Goedel's theorem does not apply. (large pdf) https://web.math.princeton.edu/~nelson/books/pa.pdf https://web.math.princeton.edu/~nelson/books/pa.pdf
  - hellbanner 12y ago
    I'll read it, thanks. I always (layman) understood Goedel's theorem as meaning you can be complete or consistent but not both. So you can have a language that can describe everything but you'll have paradoxes, or you'll have no paradoxes but not be able to describe everything (all possibilities) in your system

sixQuarks 12y ago

Here is the most entertaining article I've ever read about large numbers: http://waitbutwhy.com/2014/11/1000000-grahams-number.html http://waitbutwhy.com/2014/11/1000000-grahams-number.html

lifthrasiir 12y ago

xkcd forum has an interesting (and longish) thread playing this exact game. [1] Starting with nine thousands, it quickly becomes a mathematical nightmare or something. And also, the Big Number Duel. [2] [1] http://forums.xkcd.com/viewtopic.php?t=7469 http://forums.xkcd.com/viewtopic.php?t=7469 [2] http://tech.mit.edu/V126/N64/64largenumber.html http://tech.mit.edu/V126/N64/64largenumber.html

cousin_it 12y ago
Also see this mathoverflow post by Scott Aaronson as a follow-up to the article: http://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver http://mathoverflow.net/questions/34710/succinctly-naming-bi...

panic 12y ago

There was a contest to produce programs generating large numbers in a version of C with integral types that hold arbitrarily-large integers: http://djm.cc/bignum-rules-posted.txt http://djm.cc/bignum-rules-posted.txt You can see the results here: http://djm.cc/bignum-results.txt http://djm.cc/bignum-results.txt -- there's some interesting stuff in there!

cousin_it 12y ago
Yeah, that was a great contest as well. Though the numbers involved are necessarily much smaller than even the BB numbers, because they must be computable. Also see this old HN discussion where Eliezer proposed a good way to beat the winner: https://news.ycombinator.com/item?id=1542770 https://news.ycombinator.com/item?id=1542770

viraptor 12y ago

I don't get why the BB(x) numbers should grow faster than A(x). They're harder to compute - true. They're more difficult to prove right - true. But I cannot find anything in the article that proves it actually grows faster than Ackerman numbers. Unless you can always program A(x) in less than x steps on a Turing machine?

j2kun 12y ago
No, BB is impossible to compute (as a sequence, that is). A(x) is not.
- viraptor 12y ago
  It's impossible to compute them - sure. But the claim was that: "The sequence of Busy Beaver numbers, BB(1), BB(2), and so on, grows faster than any computable sequence." The explanation was that: "Because if a Turing machine could compute a sequence that grows faster than Busy Beaver, then it could use that sequence to obtain the D‘s—the beaver dams." But these goals seem different to me. Another sequence you cannot compute is "foo(x)" - the number of integers lower than x for which algorithm "bar(x)" doesn't halt. It's impossible to compute if "bar(x)" doesn't always halt. But the sequence cannot grow faster than "x" itself. Also, it doesn't matter that you cannot compute them if every TM of a given size can be analysed and proven halting. It doesn't have to be computed (as in, automatically checked). The fact you can compute A(x) would only be an issue if you could compute A(x) with a machine of size smaller than x.
  - j2kun 12y ago
    I think you are missing some basic concepts here. There is a single Turing machine (of constant size) which, when given any integer n, outputs A(n). This is the statement that A(n) is computable. One can prove that there is no such Turing machine for the function BB(n) or any function f(n) that bounds BB(n). Such a function would be used to solve the Halting problem as follows: given a TM M and a string x, compute k = f(|M|) and run the TM on x for k steps. If the simulation halts within k steps, output "halt" and otherwise output "loops forever." Your example of foo/bar(x) is not quite correct. If you fix a program bar, then it is not necessarily impossible to characterize (and hence compute) the set of strings for which bar(x) halts. This is not the statement of the Halting problem, and as far as I know there is no theorem that says such a function "bar" exists.

crayola 12y ago

Why not mention factorials? 9!! is way bigger than 9^9^9. And you can write many exclamation marks in 15 seconds.

vacri 12y ago
Wow, 9!! is so large that the exponent almost needs it's own exponent. 9^9^9 =~ 2e77 9!! =~ 1.6e1859933
- peterjmag 12y ago
  Correct me if I'm wrong, but aren't you supposed to evaluate stacked exponents from the top down? That is, 9^(9^9) instead of (9^9)^9. If that's the case, 9^(9^9) is much larger than 9!!. Though I'm not sure how much larger, since I couldn't find any big integer calculators online that would give me an actual result for 9^(9^9).
  - cradle 12y ago
    9^(9^9) is ... wait for it... 4e369693099 bigger than 9!! http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+9%21%21 http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+9%21%21
    - peterjmag 12y ago
      Ah thanks! How could I forget Wolfram Alpha? =)
    - BhavdeepSethi 12y ago
      Shouldn't it be (9!)!? http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+%289%21%29%21 http://www.wolframalpha.com/input/?i=9%5E9%5E9+-+%289%21%29%...
  - vacri 12y ago
    It seems you're correct - I was just pounding the values in sequence into a calculator, much like a determined monkey would.

speakeron 12y ago

If you're interested in big numbers, David Metzler's "Ridiculously huge numbers" sequence on youtube (https://www.youtube.com/watch?v=QXliQvd1vW0 https://www.youtube.com/watch?v=QXliQvd1vW0) is well worth a watch. He gives great explanations of things like the Conway chained arrow notation and the fast-growing hierarchy and just keeps on making bigger and bigger numbers.

dmichulke 12y ago

Given the other comments I wonder whether the Meta-Algorithm for big numbers is basically: Compose a state space that expands as quickly as possible in terms of the argument(s) and define some property of the state space as the result. Looking at it this way, I'd say: "Hyper-exponentiation" (Ackermann, tetration and so on) is basically counting the number of states in a well-defined state space. BB(X) is equivalent to generating automatically the state space (via a search over all possible state spaces that can be constructed with a TM with X states) and returning the size of the maximum. This means that BB(X) is smaller than the sum of the sizes of all possible state spaces constructible via that TM. But BB(X+1) is aware of that trick (summing state space sizes) and uses it already (or more probably something better), so it doesn't really matter and you might as well just increase X by one to include all the tricks you had in mind for BB(X). Anyone thoughts on that?

cousin_it 12y ago
BB_2(X) uses a different trick. It asks for the largest number computable by any program of length X that's allowed to call a BB oracle with arbitrary arguments. That's more powerful than any finite expression involving BB and computable functions, like BB(F(X)), BB(F(BB(X))), etc. More generally, I expect there to not be any "meta-algorithm" for naming big numbers. Every big step will require a new insight. A similar problem is inventing notations for large ordinals: http://en.wikipedia.org/wiki/Ordinal_notation http://en.wikipedia.org/wiki/Ordinal_notation
- Veedrac 12y ago
  I looked it up and this page showed up: http://web.mit.edu/nelhage/Public/big-number.txt http://web.mit.edu/nelhage/Public/big-number.txt. Pretty interesting.

im3w1l 12y ago

Take number theorethic conjecture. Look for counterexamples. Return first counterexample. You can't prove I didn't win!

yyhhsj0521 12y ago

9!!!!!!....!! factorial

jhonnycano 12y ago
9!!!!!!....!! + 1

GotAnyMegadeth 12y ago

When I was around 14 years old I was baby sitting a kid who was 3 or 4 or something. He came up to me and said "I bet I can say a bigger number than you." clearly proud of what he had just learnt in preschool. I accepted the challenge, he took a deep breath and said "Five hundred!", so I said "Five hundred and one". He looked determined and said "Ok then! Five hundred and fifty hundred and five hundred million hundred five hundred" (Or something that makes no sense like that). So I said "Five hundred and fifty hundred and five hundred million hundred five hundred, and one". He looked horrified and said "Can you just say 'and one' for any number?" I told him yes, and he said "Cool!".

poizan42 12y ago
And every since has that poor kid believed that "Five hundred and one and one" was a valid number.
- Xophmeister 12y ago
  It kind-of-is, it's just not particularly well-formed/ambiguous linguistically.
  - GotAnyMegadeth 12y ago
    A bit like 99 in French: quatre-vingt-dix-neuf four twenties and ten and nine
    - eitland 12y ago
      I knew the Danes where counting in a crazy way but I didn't know the French did this as well. One more reason I'm happy English is the most common international language I guess.
      - iak8god 12y ago
        According to wikitionary [1] "four score and seven" was a commonplace way of saying "eighty seven" in 19th c. English. [1] https://en.wiktionary.org/wiki/four_score_and_seven_years_ago https://en.wiktionary.org/wiki/four_score_and_seven_years_ag...

im3w1l 12y ago

Ok, I think I may have the ultimate answer to this, a sequence that grows optimally fast. It goes like this: Imagine 2^(7n) copies of the judge of this competition. For every judge create a different bit sequence of length 7n. Decode it from ascii and ask if it is a valid entry of the competition. Take the largest valid entry of those imaginary competitions. That is my entry. In order for this procedure to be consistent, this entry must be longer than n characters. Hence it will end with some padding you may disregard: asdfasdfasdfasdfasdfasdfasdfasdfasdfasdf.

cousin_it 12y ago
If you're allowed to submit entries that are mutually recursive with the decision procedure of the judges, I'm afraid the competition becomes less well defined. For example, it's easy to create a paradoxical entry by adding 1 to your entry. Also see Berry's paradox: http://en.wikipedia.org/wiki/Berry_paradox http://en.wikipedia.org/wiki/Berry_paradox
- im3w1l 12y ago
  Yeah, I agree that it becomes less well defined. The problem with Berry's paradox is that it refers to itself. I circumvented paradox, by only refering to shorter descriptions of the number, than the description I gave. If that strategy works really depends on what the judge thinks though. Assuming he accepts refering to his own potential judgements of shorter sequences but not longer or equally long, the solution would work and the rules would be paradox free.
  - cousin_it 12y ago
    Yeah, that might avoid paradox at the cost of requiring a specific kind of judge. But then I think you need to fully specify the judge's reasoning, and that's a very difficult problem, it might be even AI-complete. I don't know of any computer program that would be able to judge the descriptions of current winning entries. Maybe this quote from the googology wiki will set you on a more productive track: Googologists generally avoid many of the common responses such as "infinity," "anything you can come up with plus 1," "the largest number that can be named in ten words," "the largest number imaginable," "a zillion," "a hundred billion trillion million googolplex" or other indefinite, infinite, ill-defined, or inelegant responses. Rather googologists are interested in defining definite numbers using efficient and far reaching structural schemes, and don't attempt to forestall the unending quest for larger numbers, but rather encourage it. So perhaps a more accurate description of the challenge is: "What is the largest number you can come up with using the simplest tools?" http://googology.wikia.com/wiki/Googology#History http://googology.wikia.com/wiki/Googology#History

chinpokomon 12y ago

I have been thinking about this problem for a year or so now. I was introduced to the concept watching a Numberphille video and several hours later read this article. I've been taking a somewhat metaphysical approach to thinking about it. Instead of thinking about a Turing Machine as just a head on an endless tape, can we not consider the Universe to represent the upper limits for our calculations? Just as Turing suggested that we can take the two dimensional representation of a mathematical equation and represent it in one dimension, can we represent the entire state of the Universe in a similar way on a hypothetical Turing Machine? The halting problem is then a question of whether or not the Universe has a halting state. To extend from that, any machine that can be conceived must fit within the bounds of the Universe. Of course BB(Universe) is incalculable, but I think that it defines an upper limit. It is pointless to consider a Turing Machine that features an endless tape if an endless tape is an impossibility. In not sure if this adds to the discussion, but I haven't had anyone else I could discuss this with until now.

simonh 12y ago
By postulating an endless tape you're just stalling petty objections based on how long a tape would be required for any given task. The only point that's relevent, when considering Turing machines in the abstract, is that the amount of tape required for any given task be finite.
bjackman 12y ago
I suspect a physicist would say you're idea rests on an a view of the universe where everything is deterministic and knowable and encodable. You also have to remember that some quantities are going to be continuous, while TMs are discrete. Even an "infinite" TM can't truly encode real numbers (I think) because its infinity is of the countable variety, while Real numbers are uncountably infinite.
- chinpokomon 12y ago
  True, I am making an assumption that it is deterministic. If we presume that the Big Bang model of the Universe is true, then in the earliest moment of time, can the state of the Universe be measured? If it can be measured, how does it transition from a measurable state to an immeasurable one? I'll have to give some more thought to what you've said, but I wanted to give you a basis for why I believe it could be deterministic. Clearly I'm making some assumptions, and based on my postulate, this is a state that we could never measure ourselves. I don't know if our inability to make these measurements removes the possibility of determinism.

jbb555 12y ago

I would argue that 9^9 mentioned in the article for example _is not a number_. It is a method for calculating a number. So most of the article is invalid

ubercow13 12y ago
So is 387420489. The method goes, first you take 9, then you multiply 8 by 10 and add that to 9, then you multiply 4 by 100 and add that to what you have...
peteretep 12y ago
It's a notation, not a formula
scott_s 12y ago
You're probably viewing it as a programmer. You see the exponentiation operator, which to you means "computation", which implies some "work" must occur to get the "real" number out of the calculation. As far as a mathematician is concerned, there is no difference between 9^9, 387420489, 387420499 - 10, 774840978 / 2, or 193710244.5 * 2. They all represent the same quantity. That some are not in their fully reduced form does not change that they are unambiguous representations of the same number. Even if you are unable to see it that way, we can easily rephrase the exercise to be "write down a way to compute the largest number you can in 15 seconds". This is an enlightening mental exercise, it would be silly to dismiss it for such trivial reasons.

stillsut 12y ago

Is there some N such that BB(N) can produce any "arbitrarily large" number? Not infinity because that would mean it doesn't halt, but that there is no number which can not be exceeded by saying in effect "plus 1". Or, as N becomes large and can emulate the english language use berry's paradox style algorithm to show there is no limit to what size you want. Another approach would be to use a probability-based event for halting, and so it is always possible that a series of coin flips could keep coming up heads 1,000,000 times in a row, or a zillion times, see: st. petersburg paradox.

j2kun 12y ago
>Is there some N such that BB(N) can produce any "arbitrarily large" number? Not infinity because that would mean it doesn't halt, but that there is no number which can not be exceeded by saying in effect "plus 1". This would imply BB(n) is not well defined. To the contrary, BB(n) is finite for every n.

ttctciyf 12y ago

As an adjunct to this, if large numbers interest you there's a really excellent and long-standing set of pages about them at http://www.mrob.com/pub/math/largenum.html http://www.mrob.com/pub/math/largenum.html which has some fascinating incidental detail and covers infinities as well as large finite numbers.

chanandler_bong 12y ago

Name it? Sure - I will call it "Bob". What Bob's value is, I have no idea.

qrendel 12y ago

1) My submission: modifying Ackermann's function to describe a sequence of Busy Beaver numbers of sequential hypercomputation systems. E.g. ABB(n+1) = BB_n(n) Of course it's the same problem, you could just as easily do AABB(n+1) = ABB_n(n), but still grows faster than a Busy Beaver sequence for any single level of the hypercomputation hierarchy. 2) Question: I understand the argument for noncomputability of Busy Beavers given, but couldn't you just argue that BB(n) is finite, therefore BB(n) is a computable sum of 1+1+...+1, therefore BB(n) is computable given a finite amount of time, so any given number in the sequence is itself computable, therefore by mathematical induction all elements in the sequence are computable? Clearly not, but I don't understand why this doesn't work.

cousin_it 12y ago
1) If you're aware of the BB_n hierarchy, you've outgrown the need for recursion tricks. Instead, talk about halting times of programs that can make calls to the oracle F(n,m)=BB_n(m). That leaves any Ackermann-like approach in the dust. I leave it to you to come up with an even better approach (yes, it exists, and then there's one or two levels after that). Please don't say "I'll just use Ackermann on top of your idea", at that level it's the moral equivalent of "your number plus one". 2) For each individual BB number, there's a program that prints it. But there's no program that prints the whole infinite sequence of BB numbers one by one. All finite sequences are computable, but not all infinite sequences are.
mstoehr 12y ago
To say that the sequence is computable means that you must present a Turing machine, call it T, that will produce BB(n) in finitely many steps after taking input n. Our specific Turing machine T will have a fixed number of rules call it N rules, then by the definition of the Busy Beaver T(N+1) <= BB(N) = T(N) but BB(N+1) > BB(N) so T(N+1) does not compute BB(N+1). The flaw in your inductive proof is that you have shown there is a Turing machine that can compute BB(N) for each N, but you haven't shown that the same Turing machine can compute all numbers in the sequence.
- qrendel 12y ago

gesman 12y ago

1/0-1 I won! :-P (because infinity is not allowed, so i had to subtract one)

Randgalt 12y ago

24 is the highest number: https://www.youtube.com/watch?v=RkP_OGDCLY0 https://www.youtube.com/watch?v=RkP_OGDCLY0