News for hackers. Stuff that matters.
Re:If Real computers have finite number of states, why Turin... by dalke on Sunday May 01, 2016 @06:25PM (#11608139)
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.

There are no comments on this comment yet.