Editing Turing machine (section)

==Overview==
A Turing machine is an idealised model of a [[central processing unit]] (CPU) that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. Typically, the sequential memory is represented as a tape of infinite length on which the machine can perform read and write operations.

In the context of [[formal language]] theory, a Turing machine ([[automaton]]) is capable of [[enumeration|enumerating]] some arbitrary subset of valid strings of an [[alphabet (formal languages)|alphabet]]. A set of strings which can be enumerated in this manner is called a [[recursively enumerable language]]. The Turing machine can equivalently be defined as a model that recognises valid input strings, rather than enumerating output strings.

Given a Turing machine ''M'' and an arbitrary string ''s'', it is generally not possible to decide whether ''M'' will eventually produce ''s''. This is due to the fact that the [[halting problem]] is unsolvable, which has major implications for the theoretical limits of computing.

The Turing machine is capable of processing an [[unrestricted grammar]], which further implies that it is capable of robustly evaluating [[first-order logic]] in an infinite number of ways. This is famously demonstrated through [[lambda calculus]].

A Turing machine that is able to simulate any other Turing machine is called a [[universal Turing machine]] (UTM, or simply a universal machine). Another mathematical formalism, [[lambda calculus]], with a similar "universal" nature was introduced by [[Alonzo Church]]. Church's work intertwined with Turing's to form the basis for the [[Church–Turing thesis]]. This thesis states that Turing machines, lambda calculus, and other similar formalisms of [[computation]] do indeed capture the informal notion of [[effective method]]s in [[logic]] and [[mathematics]] and thus provide a model through which one can reason about an [[algorithm]] or "mechanical procedure" in a mathematically precise way without being tied to any particular formalism. Studying the  [[abstract machine|abstract properties]] of Turing machines has yielded many insights into [[computer science]], [[computability theory]], and [[computational complexity theory|complexity theory]].

===Physical description===
In his 1948 essay, "Intelligent Machinery", Turing wrote that his machine consists of:

{{blockquote|...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings.<ref>See the definition of "[[wikt:innings|innings]]" on [[Wiktionary]]</ref>|Turing 1948, p. 3<ref>
{{cite report
| title=Intelligent Machinery
| author=A.M. Turing
| date= Jul 1948
| url=http://www.alanturing.net/Turing_archive/archive/l/l32/L32-004.html
| institution=National Physical Laboratory
}} Here: p.3-4
</ref>}}