| I don't follow the logic. Every BB(n) is trivially computable, since any integer is computable. So for every BB(n), there is a computable sequence that grows faster than the BB numbers through n (annoyingly, given the word "grows", this can just be the constant sequence of BB(n) + 1). So for any given computable number, the fact that it's computable gives no intrinsic reason to believe it's smaller than BB(n) for any particular n. |
| No, high enough busy beaver numbers are not computable. They can be defined but there's no way to know what they are. Even for very small n you can create Turing machines where it's incredibly hard to prove that they halt: for n=25 you can create a Turing machine that stops only if the Goldbach conjecture is false. Though that isn't enough to prove it's not computable, the point stands that if you could compute BB(n) for arbitrary n, you could run a Turing machine for BB(n)+1 steps and if it hasn't stopped yet then you know that the input corresponds to a machine that never halts. So it's impossible to write a program that computes BB(n) for arbitrary n, because doing so is equivalent to the halting problem. And worse, there are some Turing machines where "proving the Turing machine stops" means "proving that a given set of axioms is consistent", where Gödel's incompleteness theorem says that it's impossible to build such a proof. So, that is how there is some n after which the busy beaver number is defined, but is not computable at all. |
| |
| ▲ | hyperpape a day ago | parent [-] | | What I mean is that any given integer is trivially computable. The busy beaver sequence is not computable (I am aware that somewhere around BB(700), you've encoded the consistency of ZFC). You cannot necessarily compute that BB(n) is a given number. But you can compute larger numbers. There is no such thing as integer that is too large to be computable. I did slightly fuck up--the English language "every BB(n) is computable" is a bit ambiguous. What I should say is: "for all n, BB(n) is trivially computable, since it is a single integer". | | |
| ▲ | bonzini a day ago | parent [-] | | > for all n, BB(n) is trivially computable, since it is a single integer". It is not computable, because for high enough n you can't prove that you got the right integer. And also you can prove that if a sequence a_n is always larger than BB(n) for some n, that sequence a_n is also not computable. | | |
| ▲ | hyperpape a day ago | parent | next [-] | | See https://news.ycombinator.com/item?id=50076267. The busy beaver function is uncomputable. That is well understood. However, for any given n, there is a number BB(n). Since that number is an integer, it is computable, even though it is the value of an incomputable function applied to a particular n. In particular, for numbers > 5, we have no idea what that number is. But whatever number it is, that number is computable. Look at the post that I was responding to. It made the bad inference that because Graham's Number is computable, it ought to be smaller than BB(10). That confuses computability of a given number with computability of a function. | | |
| ▲ | bonzini a day ago | parent [-] | | Computable doesn't mean that you can write it down the number that is the value, given an oracle that tells you the value. It means that you know that it the number you are writing down is the right one, because you computed it. |
| |
| ▲ | SAI_Peregrinus a day ago | parent | prev | next [-] | | You can always exhaustively run all Turing machines of a given size, at each step comparing the state & tape to all previous steps. If they ever reach the same state with the same tape as a previous step, they're in an infinite loop and never halt. If not, they eventually reach the halt state. BB(n) is computable. But BB is not computable, because there's no general algorithm requiring finite storage and time which computes the results of BB(n) for all n. You have to brute-force it for every positive integer n, which takes infinite time (and space) and is therefore not computable. | | |
| ▲ | davrosthedalek a day ago | parent | next [-] | | There is no requirement to have a recurring state when not halting. Indeed, the most trivial machine "write 1 and move right", will never have the same tape state. | | |
| ▲ | Jerrrrrrrrry a day ago | parent [-] | | Total state, not just tape. Meaning stack, pointer Location, etc. | | |
| ▲ | davrosthedalek 20 hours ago | parent [-] | | First, TMs don't have a stack. Second, still no recurrent state needed. Extending a state with additional variables doesn't make a unique state less unique anyway, so "total state" is always more or same unique as "just tape". | | |
| ▲ | Jerrrrrrrrry 12 hours ago | parent [-] | | Some turing machine variants have multiple tapes, effectively registers. If the tape, instruction position, and all other variables are the same as any previous step, then the deterministic machine is going to continue to find itself in that loop, and never halt. Think Collatz like functions - if the output starts into a loop, you know the end result. However, any program trying to detect all loops by maintaining a bloom filter of every previous state doesnt work, that drags any computation down by a scale of its inputs^runtime. |
|
|
| |
| ▲ | Scarblac a day ago | parent | prev [-] | | Note that this casually solves the halting problem, usually a hint that something is wrong. |
| |
| ▲ | empath75 a day ago | parent | prev [-] | | I think people are confusing two ideas. for all n there is some natural number x such that BB(n) = x x like all natural numbers is trivially computable. But BB(n) as a function that you could run and _find_ x, is not computable in general, because it would entail solving the halting problem. |
|
|
|
