2
$\begingroup$

In several talks and lectures, I've heard people saying that a physical computer is just a Turing machine but I'm unable to justify this analogy.

My apprehension is the following: Without loss of generality, I can consider physical computer as a machine that follows instructions of a code written in C / assembly language with its unit operations being carried out in the transistors in its hardware. But the inner workings of a computer in no way seems to emulate the instructions of the user code in terms of the 7-tuple $Q, \tau, b, \Sigma, q_0, F, \delta$ that performs Turing machine-type operations.

$\endgroup$
2

1 Answer 1

5
$\begingroup$

You certainly are right that if someone says "a physical computer is just a Turing machine" then they are telling a bit of a stretcher. More accurate would be something like "anything that can be computed on a physical computer can be computed on a Turing machine." Still more accurate would be "A Turing machine is an idealization of physical computing device. It is an idealization in that we don't limit ourselves to any particular fixed scratch memory limits, etc. Anything that can be computed on a general purpose computer can be computed on a Turing machine, and the converse holds if we don't bind ourselves to the limits of the general purpose device, such as address spaces of RAM, etc."

The sense in which "a physical computer is just a Turing machine" is if when you are programming you think, "I am going to write a program to compute this, and I am just not going to worry about what happens if the input is too long to fit on the hard disk." My experience with introduction to programming courses is that they do take that model, so perhaps that is what the people meant in those lectures.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.