I often hear Turing machine is a mathematical model of computation. Sometimes, it's said to embody any computer program. Sometimes, it's said to be an idealised computing device consisting of a read/write head.

But is it a theoretical model for hardware or a theoretical model for software?


Very roughly, you can use the following analogies.

Turing machine Modern computer
Tape & head RAM, disk, other forms of data storage
Instruction table Electronic circuit
Turing machine Any electronic device (thermostat, PC, phone, digital camera, electronic car key)
Universal Turing machine Computer with a CPU or other programmable general-purpose device
Oracle machine Electronic device with access to external source of information (keyboard, mouse, touchpad, various sensors)
Input Data to be processed
Input to Universal Turing machine Software

But please, do not read too much into this analogy. It may help you understand the formal definition of Turing machines, but you should not try to analyze it as a mathematical definition, because it is not one.

  • $\begingroup$ Shouldn't "Instruction table" be the "software" of instruction instead of "electronic circuit"? $\endgroup$ Aug 3 at 20:23
  • $\begingroup$ Is "Oracle machine" roughly "Universal Turing machine" + "input/output device"? $\endgroup$ Aug 3 at 20:27
  • $\begingroup$ My main source of confusion comes from when people say "Any algorithm could be conceived could be converted to a unique Turing machine", which sounds like Turing machine is a software. But sometimes, I also hear others explaining Church-Turing thesis saying "Turing machine can simulate any mechanical machine", which sounds like Turing machine is a hardware. So do you know what exactly what they mean? $\endgroup$ Aug 3 at 20:51
  • $\begingroup$ Take an algorithm, say Quicksort. If you put together an electronic circuit that sorts arrays using Quicksort, that's like creating a Turing machine that can sort. If you implement Quicksort in machine code on your PC, that's like giving input to the Universal Turing machine that instructs it to perform sorting. So there are possiblities. Regarding "oracle machine", I provided a link to Wikipedia, so don't make guesses, read the description instead. $\endgroup$ Aug 3 at 21:26
  • $\begingroup$ An no, instruction set should not be software. Software is not fixed: you can install and uninstall various apps on your computer, so that is like writing things on the input tape of a Universal Turing machine. But each Turing machine has a fixed instruction set, so that corresponds to the fixed circuitry that controls an electronic device. $\endgroup$ Aug 3 at 21:29

The turing machine is a mathematical concept to describe computability and complexity. Although we often talk about a head moving across some infinite tape, this is just to aid thinking and understanding. You don't need that. The TM's formal definition only needs basic discrete mathematics.

Alan Turing wasn't interested in building a computer or some mechanical machine. He was interested in determining exactly what an algorithm is. He started by reflecting what an appropriately educated human being could compute given a pen and infinite piece of paper.

According to the Church-Turing thesis everything that can be computed can (also) be computed by a turing machine. Thus every computer program (which by definition is computable) can be executed by a suitable turing machine. In this sense, it could be considered a model for software, but a very weak one. Formally giving a turing machine that checks whether a string is a palindrome is tedious. Writing a Ruby or Python script to do that is a few lines.

  • $\begingroup$ Maybe the downvoter could elaborate what they think is wrong with my answer. Just downvoting is not particularly helpful. $\endgroup$
    – idmean
    Aug 3 at 10:22
  • 1
    $\begingroup$ At no point of execution does a Turing machine need infinite storage, so you do not need all of it ahead of time. And it is quite possible to create physical models of a Turing machine. It is largely irrelevant that they do not have "infinite" tape, and is certainly misleading to claim that they are "not real Turing machines" because of that. If Zuse or von Neumann held such an attitude, they would have given up on building modern computers even before they began. $\endgroup$ Aug 3 at 10:23
  • $\begingroup$ @AndrejBauer Yes, I realized that this paragraph was very misleading. This is why I already edited my question in this regard. $\endgroup$
    – idmean
    Aug 3 at 10:24
  • $\begingroup$ A little patience, please? I was typing my comment, you didn't even give me any time to explain myself. Also, note that you're not really addressing the OPs concern by telling them that a Turing machine is a mathematical concept that "does not need" an analogy with the physical machines. They're asking precisely for such an analogy. Historically, Turing machines very much inspired the creations of physcal electronic devices, which is another reason in favor of making analogies between Turing machines and physical devices. $\endgroup$ Aug 3 at 10:26
  • $\begingroup$ How do you know that Alan Turing was not interested in building a mechanical machine? $\endgroup$ Aug 3 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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