This is a great question. What do we lose by thinking of real computers as Turing machines when they are in fact finite ? For one thing I believe the halting-problem doesn't exist in reality because it only holds for infinite systems (ie. Turing machines), not finite ones (ie. physical computers).
I never heard of the BB problem before but according to Wikipedia it requires an N-state Turing Machine so I don't see how that's relevant to the question I posed. Could you elaborate ?
Sure. By definition, BB-N halts, which means it uses a finite number of cells because it halts in finite time. Thus, it doesn't need a infinite tape, just a very large one.
Consider this variation. Given 4 GB of tape cells, and 2 symbols, what is the longest number of sequential '1's that can be written by a 10 state machine, where the machine halts and where the machine does not reach the end of the tape?
If you can solve that, use 1 TB of cells. Then 1 gogoolplex of cells. If you can keep on doing this, then you're able to compute S(n) and Σ(n), and solve the Busy Beaver problem.
4 comments
[ 3.1 ms ] story [ 19.0 ms ] threadConsider this variation. Given 4 GB of tape cells, and 2 symbols, what is the longest number of sequential '1's that can be written by a 10 state machine, where the machine halts and where the machine does not reach the end of the tape?
If you can solve that, use 1 TB of cells. Then 1 gogoolplex of cells. If you can keep on doing this, then you're able to compute S(n) and Σ(n), and solve the Busy Beaver problem.