Hand-drawn picture of Turing Machine

Is my desktop computer or my laptop a Turing Machine?



That is a very good question, but it is also a very vague question.

You may have heard at some time that "Every computer is a Turing Machine." What does that really mean? Certainly, your desktop computer doesn't look like a Turing Machine as Alan Turing described it; it doesn't have an infinitely-long paper tape on which it keeps reading and writing nothing but 0's and 1's and maybe even some other symbols.

So, when you ask "Is my computer a Turing Machine?" what is it that you are really asking?

Perhaps this question is too vague, and perhaps it would be better to ask some more specific questions:

Is my computer Turing Complete?

Is my computer Turing Equivalent?

A very brief answer to the above questions may be given as follows:

Something is Turing Complete if it can compute anything that any Turing Machine can compute. So, if it can simulate any Turing Machine, then it is Turing Complete.

Something is Turing Equivalent if it can compute anything that any Turing Machine can compute, and also if there is a Turing Machine that can compute anything that it can compute. So, if it can simulate any Turing Machine, and if there is some Turing Machine that can simulate it, then it is Turing Equivalent.

Version 1.0 -- April 23, 2017
Template Version 1.0 -- May 19, 2017