5 ms·

Another introduction to this same topic, that goes much further and is better written: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaa

by emmett 18y ago

Another introduction to this same topic, that goes much further and is better written: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html

robertk 18y ago
You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number--not an infinity--on a blank index card. 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. Judging by the rest of the article, I would have won. I would have written "Ackermann function on Graham's number and Graham's number." For added enjoyment, add "Call this B_1. Define B_n = A(B_n-1,B_n-1) for n > 1. Now take B_(B_1)." EDIT: Or I guess just: Let G be Graham's number. Let B_n be G if n = 1 and A(B_n-1,B_n-1) if n > 1 (where A is Ackermann's function). Take B_B_2.
- kylec 18y ago
  I think your number is the XKCD number: http://www.xkcd.com/207/ http://www.xkcd.com/207/
  - robertk 18y ago
    Yep! Only my second example was doing that recursively...oh the horror...
- gjm11 18y ago
  Sounds like you didn't read all of the rest of the article! (Unless you mean you'd have won against the mathematically naive people he mentions at the start who wrote down things like long sequences of 9s.) Aaronson goes on to describe short names for big numbers that get much bigger with fewer symbols than things like your iterated Ackermann. Specifically, by defining a sequence of numbers in terms of how much a program of given length can do, given that it halts, it turns out that you get a sequence that provably grows faster than any computable sequence. (It's actually traditional to do this with Turing machines rather than conventional programs.) This is in fact rather closely related to Chaitin's stuff at the start of this discussion.
ars 18y ago
If you ever wanted a use for the term "begs the question" here you go: "If we could live for 70,000,000 years, there’d be no theory of evolution, and certainly no creationism: we could watch speciation and adaptation with our eyes," He assumes that evolution is true, then therefor if we lived to 70,000,000 there would not be creationism. However if evolution wasn't real, but creationism was, and people lived to 70,000,000 year you could say the same thing: they saw creation happen, and no one would imagine such a thing as evolution. Which makes his sentence effectively meaningless. And he "begged the question". It's an interesting article, but it has a number of errors that severely diminish it. Plus he really needs to stop bashing on the bible and stuff (that myth that the bible says Pi is 3 isn't even true). My biggest gripe with it is this: "Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture." That's WRONG! A turing machine that checks every single integer by definition never halts, so the entire exercise is pointless - you'll get no info. Yah, if it halts you know the answer, but if it doesn't you know nothing, so calculating BB(100) doesn't help you at all. On top of that it's possible that BB's for large number don't exist - I don't mean that they can't be calculated, I mean that for whatever numbers of steps you chose you can make the machine halt in that number of steps, but there is no upper limit at all, and you can always create a machine that halts after more steps. PS. If you want a really large number that ordinary students would understand try 9!!!!!!!!.... (repeated factorial).
- jerf 18y ago
  Your "That's WRONG" is, pardon the capitalization, WRONG. The definition of BB(100) is the number below which all 100-rule TMs that halt will in fact halt. Everything that ever halts will halt before that number of steps, everything that continues one step past BB(100) will never halt. That's the definition. If you have a conjecture encoded into a 100-state TM and you know BB(100), then all you do is run the machine for BB(100)+1 steps. If it gets to BB(100)+1, then by the definition of BB(100), it will never halt. If it halts before that, well, it halted. Of course BB(100) is incomprehensibly large, well beyond what the entire universe could possibly be used to execute. (Likely, BB(10) is already at that point.) "On top of that it's possible that BB's for large number don't exist" - no it's not. It's perfectly well defined as the largest element from a well-defined finite set. There must be a maximum value.
yters 18y ago
That article has nothing to do with the one I posted. The one I posted is talking about the implications of Omega numbers for math and physics. Yours just talks about the busy beaver number. It is more mathematically informed though, I'll give you that.
- emmett 18y ago
  Ah, you're right. I forgot it doesn't mention Omega. However, at least they're related concepts!

by emmett 18y ago

Another introduction to this same topic, that goes much further and is better written: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html

robertk 18y ago

You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number--not an infinity--on a blank index card. 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. Judging by the rest of the article, I would have won. I would have written "Ackermann function on Graham's number and Graham's number." For added enjoyment, add "Call this B_1. Define B_n = A(B_n-1,B_n-1) for n > 1. Now take B_(B_1)." EDIT: Or I guess just: Let G be Graham's number. Let B_n be G if n = 1 and A(B_n-1,B_n-1) if n > 1 (where A is Ackermann's function). Take B_B_2.

kylec 18y ago
I think your number is the XKCD number: http://www.xkcd.com/207/ http://www.xkcd.com/207/
- robertk 18y ago
  Yep! Only my second example was doing that recursively...oh the horror...
gjm11 18y ago
Sounds like you didn't read all of the rest of the article! (Unless you mean you'd have won against the mathematically naive people he mentions at the start who wrote down things like long sequences of 9s.) Aaronson goes on to describe short names for big numbers that get much bigger with fewer symbols than things like your iterated Ackermann. Specifically, by defining a sequence of numbers in terms of how much a program of given length can do, given that it halts, it turns out that you get a sequence that provably grows faster than any computable sequence. (It's actually traditional to do this with Turing machines rather than conventional programs.) This is in fact rather closely related to Chaitin's stuff at the start of this discussion.

ars 18y ago

If you ever wanted a use for the term "begs the question" here you go: "If we could live for 70,000,000 years, there’d be no theory of evolution, and certainly no creationism: we could watch speciation and adaptation with our eyes," He assumes that evolution is true, then therefor if we lived to 70,000,000 there would not be creationism. However if evolution wasn't real, but creationism was, and people lived to 70,000,000 year you could say the same thing: they saw creation happen, and no one would imagine such a thing as evolution. Which makes his sentence effectively meaningless. And he "begged the question". It's an interesting article, but it has a number of errors that severely diminish it. Plus he really needs to stop bashing on the bible and stuff (that myth that the bible says Pi is 3 isn't even true). My biggest gripe with it is this: "Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture." That's WRONG! A turing machine that checks every single integer by definition never halts, so the entire exercise is pointless - you'll get no info. Yah, if it halts you know the answer, but if it doesn't you know nothing, so calculating BB(100) doesn't help you at all. On top of that it's possible that BB's for large number don't exist - I don't mean that they can't be calculated, I mean that for whatever numbers of steps you chose you can make the machine halt in that number of steps, but there is no upper limit at all, and you can always create a machine that halts after more steps. PS. If you want a really large number that ordinary students would understand try 9!!!!!!!!.... (repeated factorial).

jerf 18y ago
Your "That's WRONG" is, pardon the capitalization, WRONG. The definition of BB(100) is the number below which all 100-rule TMs that halt will in fact halt. Everything that ever halts will halt before that number of steps, everything that continues one step past BB(100) will never halt. That's the definition. If you have a conjecture encoded into a 100-state TM and you know BB(100), then all you do is run the machine for BB(100)+1 steps. If it gets to BB(100)+1, then by the definition of BB(100), it will never halt. If it halts before that, well, it halted. Of course BB(100) is incomprehensibly large, well beyond what the entire universe could possibly be used to execute. (Likely, BB(10) is already at that point.) "On top of that it's possible that BB's for large number don't exist" - no it's not. It's perfectly well defined as the largest element from a well-defined finite set. There must be a maximum value.

yters 18y ago

That article has nothing to do with the one I posted. The one I posted is talking about the implications of Omega numbers for math and physics. Yours just talks about the busy beaver number. It is more mathematically informed though, I'll give you that.

emmett 18y ago
Ah, you're right. I forgot it doesn't mention Omega. However, at least they're related concepts!