**Turing Machines**

**Turing machine** is a term from computer science. A Turing machine is a system of rules, states and transitions rather than a *real* machine. It was first described in 1936 by English mathematician Alan Turing. There are two purposes for a Turing machine: deciding formal languages . Turing machines are one of the most important formal models in the study of computer science.

Turing machines, first described by Alan Turin g in Turing 1936–7, are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed. Turing’s ‘automatic machines’, as he termed them in 1936, were specifically devised for the computing of real numbers. They were first named ‘Turing machines’ by Alonzo Church in a review of Turing’s paper (Church 1937). Today, they are considered to be one of the foundational models of computability and (theoretical) computer science.

A **Turing machine** is a general example of a __CPU__ that controls all data manipulation done by a computer, with the canonical machine using sequential memory to store data. More specifically, it is a machine (__automaton__) capable of __enumerating__ some arbitrary subset of valid strings of an __alphabet__; these strings are part of a __recursively enumerable set__. A Turing machine has a tape of infinite length that enables read and write operations to be performed.

Assuming a __black box__, the Turing machine cannot know whether it will eventually enumerate any one specific string of the subset with a given program. 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**). A more mathematically oriented definition with a similar “universal” nature was introduced by __Alonzo Church__, whose work on lambda calculus intertwined with Turing’s in a formal theory of __computation__ known as the __Church–Turing thesis__. The thesis states that Turing machines indeed capture the informal notion of __effective methods__ in __logic__ and __mathematics__, and provide a precise definition of an __algorithm__ or “mechanical procedure”. Studying their __abstract properties__ yields many insights into __computer science__ and __complexity theory__.

**Physical description :**

In his 1948 essay, “Intelligent Machinery”, Turing wrote that his machine consisted of:

…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 inning.