Editing Turing machine (section)

==Comparison with real machines==
[[File:Lego Turing Machine.jpg|thumb|A Turing machine realization using [[Lego]] pieces]]
Turing machines are more powerful than some other kinds of automata, such as [[finite-state machine]]s and [[pushdown automata]]. According to the [[Church–Turing thesis]], they are as powerful as real machines, and are able to execute any operation that a real program can. What is neglected in this statement is that, because a real machine can only have a finite number of ''configurations'', it is nothing but a finite-state machine, whereas a Turing machine has an unlimited amount of storage space available for its computations.

There are a number of ways to explain why Turing machines are useful models of real computers:

* Anything a real computer can compute, a Turing machine can also compute. For example: "A Turing machine can simulate any type of subroutine found in programming languages, including recursive procedures and any of the known parameter-passing mechanisms" (Hopcroft and Ullman p.&nbsp;157). A large enough FSA can also model any real computer, disregarding IO. Thus, a statement about the limitations of Turing machines will also apply to real computers.
* The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.
* Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media.
* Descriptions of real machine programs using simpler abstract models are often much more complex than descriptions using Turing machines. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent deterministic finite automaton (DFA) on a given real machine has quadrillions. This makes the DFA representation infeasible to analyze.
* Turing machines describe algorithms independent of how much memory they use. There is a limit to the memory possessed by any current machine, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in ''conventional'' computing machine architecture.
* Algorithms running on Turing-equivalent abstract machines can have arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not limited to, running [[out of memory]]).

[[File:Turingmachine.jpg|thumb|Another Turing machine realization]]

===Limitations===

====Computational complexity theory====
{{further|Computational complexity theory}}

A limitation of Turing machines is that they do not model the strengths of a particular arrangement well. For instance, modern stored-program computers are actually instances of a more specific form of [[abstract machine]] known as the [[random-access stored-program machine]] or RASP machine model. Like the universal Turing machine, the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the universal Turing machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory "cells" that can contain any integer (cf. Elgot and Robinson (1964), Hartmanis (1971), and in particular Cook-Rechow (1973); references at [[random-access machine]]). The RASP's finite-state machine is equipped with the capability for indirect addressing (e.g., the contents of one register can be used as an address to specify another register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing machine; thus when Turing machines are used as the basis for bounding running times, a "false lower bound" can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing machine). An example of this is [[binary search]], an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model.

====Interaction====
In the early days of computing, computer use was typically limited to [[batch processing]], i.e., non-interactive tasks, each producing output data from given input data. Computability theory, which studies computability of functions from inputs to outputs, and for which Turing machines were invented, reflects this practice.

Since the 1970s, [[interactivity|interactive]] use of computers became much more common.  In principle, it is possible to model this by having an external agent read from the tape and write to it at the same time as a Turing machine, but this rarely matches how interaction actually happens; therefore, when describing interactivity, alternatives such as [[Input/output automaton|I/O automata]] are usually preferred.