If Real computers have finite number of states, why Turing machines are needed? (opens in new tab)

(cstheory.stackexchange.com)

2 pointspinchn9y ago4 comments

4 comments

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

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

tgflynn9y ago

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 ?

1 more reply

j / k navigate · click thread line to collapse

4 comments

tgflynn9y ago

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

tgflynn9y ago

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 ?

1 more reply

j / k navigate · click thread line to collapse