Editing Turing machine (section)

==Equivalent models==
{{See also|Turing machine equivalents|Register machine|Post–Turing machine}}

Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p.&nbsp;159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (The [[Church–Turing thesis]] ''hypothesises'' this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)

A Turing machine is equivalent to a single-stack [[pushdown automaton]] (PDA) that has been made more flexible and concise by relaxing the [[LIFO (computing)|last-in-first-out]] (LIFO) requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard LIFO  semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.

At the other extreme, some very simple models turn out to be [[Turing completeness|Turing-equivalent]], i.e. to have the same computational power as the Turing machine model.

Common equivalent models are the [[multi-tape Turing machine]], [[multi-track Turing machine]], machines with input and output, and the [[Non-deterministic Turing machine|''non-deterministic'' Turing machine]] (NDTM) as opposed to the ''deterministic'' Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.

[[Read-only right moving Turing machines|Read-only, right-moving Turing machines]] are equivalent to [[Deterministic finite automaton|DFAs]] (as well as [[Nondeterministic finite automaton|NFAs]] by conversion using the [[NFA to DFA conversion]] algorithm).

For practical and didactic intentions, the equivalent [[register machine]] can be used as a usual [[Assembly language|assembly]] [[programming language]].

A relevant question is whether or not the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, [[ANSI C]] is not Turing complete, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called ''pointers'', is accessible inside the language. However, other programming languages like [[Pascal (programming language)|Pascal]] do not have this feature, which allows them to be Turing complete in principle.
It is just Turing complete in principle, as [[memory allocation]] in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.