top | item 11605845

If Real computers have finite number of states, why Turing machines are needed?

2 points| pinchn | 9 years ago |cstheory.stackexchange.com

4 comments

order

tgflynn|9 years ago

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).

dalke|9 years ago

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.