6 ms·

> But BB is an uncomputable function. You've not escaped undecidability at all. You cannot write a program that will compute BB(n) given n as an input. I think

> But BB is an uncomputable function. You've not escaped undecidability at all. You cannot write a program that will compute BB(n) given n as an input. I think you're going down the wrong path re "uncomputable". BB(n) is easily computable, just write a little program that enumerates (generates) and runs all n-state BB machines. BB(n) is the largest lifetime of any those n-state machines. BB(n) is known and easily computable for small n. The problem is that the number of machines increases very quickly with n, and the time taken to evaluate each machine often increases quickly with n. So for even moderate n, it is completely impractical to brute-force compute BB(n). But impractical is not uncomputable. Just because you don't wait to wait past the heat-death of the universe, doesn't mean that you wouldn't have got an answer eventually. And eventually = computable.

a_cardboard_box 3y ago
How do you know when the last n-state machine has finished, given that some will not halt?
torinmr 3y ago
BB(n) isn't computable, even given unlimited computational resources. Running all n-state machines won't work, because you may have some machines that continue indefinitely, but without repeating. (Remember that while the number of states is finite, the tape is infinite.) No matter how long you run them for, you can't be sure whether they are going to terminate at some point in the future, or if they'll continue forever without halting. This is why computing BB(n) for arbitrary n is equivalent to solving the halting problem.
- drpixie 3y ago
  You're right about the tape. Duh.
srcreigh 3y ago
This is false. You’d never get the answer with that strategy, since some of the machines will never halt, but you wouldn’t know if the ones you have left are going to halt or not. Te winning strategy is to A) prove all the machines that don’t halt and B) find the largest runtime of machines that do halt. That’s why BB(745) is important because we can’t use ZFC to prove A for BB(745), even if we could run all the halting machines to find BB(745).

a_cardboard_box 3y ago

How do you know when the last n-state machine has finished, given that some will not halt?

torinmr 3y ago

BB(n) isn't computable, even given unlimited computational resources. Running all n-state machines won't work, because you may have some machines that continue indefinitely, but without repeating. (Remember that while the number of states is finite, the tape is infinite.) No matter how long you run them for, you can't be sure whether they are going to terminate at some point in the future, or if they'll continue forever without halting. This is why computing BB(n) for arbitrary n is equivalent to solving the halting problem.

drpixie 3y ago
You're right about the tape. Duh.

srcreigh 3y ago

This is false. You’d never get the answer with that strategy, since some of the machines will never halt, but you wouldn’t know if the ones you have left are going to halt or not. Te winning strategy is to A) prove all the machines that don’t halt and B) find the largest runtime of machines that do halt. That’s why BB(745) is important because we can’t use ZFC to prove A for BB(745), even if we could run all the halting machines to find BB(745).