If Real computers have finite number of states, why Turing machines are needed?(cstheory.stackexchange.com) |
If Real computers have finite number of states, why Turing machines are needed?(cstheory.stackexchange.com) |
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.