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?
1–5 of 5 posts
Re: If Real computers have finite number of states, why Turing machines are needed?
#2This 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).
Re: If Real computers have finite number of states, why Turing machines are needed?
#3This 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).
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 Turing machines are needed?
#4This 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).
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.
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 Turing machines are needed?
#5Earlier quoted context omitted.
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.
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.