4 ms·

> if you’re in a biggest-number-naming contest, and you write “BB(10000),” you’ll destroy any opponent—however otherwise mathematically literate they are—who’s

> if you’re in a biggest-number-naming contest, and you write “BB(10000),” you’ll destroy any opponent—however otherwise mathematically literate they are—who’s innocent of computability theory. For BB(n) grows faster than any computable sequence of integers So is BB(10000) computable or no? If not, does "greater than" still have meaning?

tialaramex 9y ago
The Busy Beaver _function_ BB() is non-computable. Computability is a property functions have. BB(10000) is a number, although we don't and never will know which one. It doesn't mean anything to ask whether particular numbers are "computable".
- daxfohl 9y ago
  Oh, I see, I think. So for the sake of argument BB(10000) could be, like, 5. But there's no way for us to know that for sure because BB is non-computable above a certain N. 5 itself remains just a number. Takes a bit of the drama out of the topic. (And while "Aha: BB(10000) is NOT 5", one could make some function BBOBB(N) := BB(N)/BB(N-1), and maybe BBOBB(N) for whatever reason is 5 for some large N, but is not computable and thus can't be proven so. Or something like that. Which also takes some of the drama away).
  - schoen 9y ago
    > Oh, I see, I think. So for the sake of argument BB(10000) could be, like, 5. But there's no way for us to know that for sure because BB is non-computable above a certain N. 5 itself remains just a number. Takes a bit of the drama out of the topic. Sure, although BB(3) is already larger than 5 and every BB number is much larger than the previous one, so the specific estimate of 5 is probably going to be more of an understatement than almost anything anyone has ever said. :-) > (And while "Aha: BB(10000) is NOT 5", one could make some function BBOBB(N) := BB(N)/BB(N-1), and maybe BBOBB(N) for whatever reason is 5 for some large N, but is not computable and thus can't be proven so. Or something like that. Which also takes some of the drama away). BBOBB(N) also grows faster than any computable function, and for N≥4, BB(N+1)>BB(N)². So also it's not going to be 5 for any large N.
    - daxfohl 9y ago
      Well so BBOBBSQUARED or whatever. The point being that it's conceivable to define a simple function that is not computable yet has a simple result. Though really that's what (computable.bb)(n) already is, in a far more interesting fashion. So really, never mind this.
      - schoen 9y ago
        I'm not quite sure where you're going with this. The BB numbers are definitely regular integers in the same way that twelve or a googol is, but the uncomputability and fast growth of the function tend to "infect" other transformations and related functions, so that it also becomes very hard to say specific things about them.
        daxfohl 9y ago
        Yeah I don't really know either. Something like if you name a number by saying BB(10000), but it's not computable, then have you actually named a number? But really that's just a boring question of how you referee the game.
      - Scarblac 9y ago
        Of course. The number of Turing machines is countable, so you can number them. HALT(n) is 1 when Turing machine halts and 0 when it doesn't. Incomputable but always 0 or 1.
        Firadeoclus 9y ago
        Except if you doubt that "when it doesn't halt" is an actual condition.
- tialaramex 9y ago
  There's an error here - I said that computability isn't a property of numbers. That's not really fair. Real numbers on the whole can be non-computable, but all the Integers are computable, and all these BB() family functions have integer results, so those numbers would always be computable, we just have no idea what they are exactly. Chaitin's Constants are not computable. They're some fraction (between 0 and 1) which is the probability of a randomly chosen program for some Turing equivalent system halting. This constant will vary depending on how the system works, but we can't compute it for any system at all for obvious reasons.
akrasuski1 9y ago
It is possible to generate a lower bound, so it can be compared with usual numbers, like g_64 etc.

tialaramex 9y ago

The Busy Beaver _function_ BB() is non-computable. Computability is a property functions have. BB(10000) is a number, although we don't and never will know which one. It doesn't mean anything to ask whether particular numbers are "computable".

daxfohl 9y ago
Oh, I see, I think. So for the sake of argument BB(10000) could be, like, 5. But there's no way for us to know that for sure because BB is non-computable above a certain N. 5 itself remains just a number. Takes a bit of the drama out of the topic. (And while "Aha: BB(10000) is NOT 5", one could make some function BBOBB(N) := BB(N)/BB(N-1), and maybe BBOBB(N) for whatever reason is 5 for some large N, but is not computable and thus can't be proven so. Or something like that. Which also takes some of the drama away).
- schoen 9y ago
  > Oh, I see, I think. So for the sake of argument BB(10000) could be, like, 5. But there's no way for us to know that for sure because BB is non-computable above a certain N. 5 itself remains just a number. Takes a bit of the drama out of the topic. Sure, although BB(3) is already larger than 5 and every BB number is much larger than the previous one, so the specific estimate of 5 is probably going to be more of an understatement than almost anything anyone has ever said. :-) > (And while "Aha: BB(10000) is NOT 5", one could make some function BBOBB(N) := BB(N)/BB(N-1), and maybe BBOBB(N) for whatever reason is 5 for some large N, but is not computable and thus can't be proven so. Or something like that. Which also takes some of the drama away). BBOBB(N) also grows faster than any computable function, and for N≥4, BB(N+1)>BB(N)². So also it's not going to be 5 for any large N.
  - daxfohl 9y ago
    Well so BBOBBSQUARED or whatever. The point being that it's conceivable to define a simple function that is not computable yet has a simple result. Though really that's what (computable.bb)(n) already is, in a far more interesting fashion. So really, never mind this.
    - schoen 9y ago
      I'm not quite sure where you're going with this. The BB numbers are definitely regular integers in the same way that twelve or a googol is, but the uncomputability and fast growth of the function tend to "infect" other transformations and related functions, so that it also becomes very hard to say specific things about them.
      - daxfohl 9y ago
        Yeah I don't really know either. Something like if you name a number by saying BB(10000), but it's not computable, then have you actually named a number? But really that's just a boring question of how you referee the game.
    - Scarblac 9y ago
      Of course. The number of Turing machines is countable, so you can number them. HALT(n) is 1 when Turing machine halts and 0 when it doesn't. Incomputable but always 0 or 1.
      - Firadeoclus 9y ago
        Except if you doubt that "when it doesn't halt" is an actual condition.
tialaramex 9y ago
There's an error here - I said that computability isn't a property of numbers. That's not really fair. Real numbers on the whole can be non-computable, but all the Integers are computable, and all these BB() family functions have integer results, so those numbers would always be computable, we just have no idea what they are exactly. Chaitin's Constants are not computable. They're some fraction (between 0 and 1) which is the probability of a randomly chosen program for some Turing equivalent system halting. This constant will vary depending on how the system works, but we can't compute it for any system at all for obvious reasons.

akrasuski1 9y ago

It is possible to generate a lower bound, so it can be compared with usual numbers, like g_64 etc.