Re:If Real computers have finite number of states, why Turin...
by tgflynn on Sunday May 01, 2016 @08:16AM
(#11605889)
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).
[ Parent
| on HN ]
Re:If Real computers have finite number of states, why Turin...
by dalke on Sunday May 01, 2016 @11:37AM
(#11606565)
We lose very little. The Busy Beaver problem shows that even a small number of states can take time that's described with Knuth's up arrow notation.
Re:If Real computers have finite number of states, why Turin...
by tgflynn on Sunday May 01, 2016 @01:46PM
(#11607070)
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 ?
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.