Turing Machine

The Turing machine -not to be confused with the band- is a basic abstract symbol-manipulating device. Although it may seem symple, it can simulate the logic of any computer algorithum.
It was first described in 1936 by Alan Turing. He did not intend for it to be used as practical computing technology. It was meant to be used as a thought experiment about the limits of mechanical computation. Because of that, the Turing machine was not actually constructed.
A Turing machine that could simulate any other Turing machine is called a Universal Turing machine (UTM or universal machine) A more mathematically-oriented definition with a similar "universal" nature was introduced by Alfonzo Church whose work on the lambda calculus intertwined with Turing's formal theory on computation known as the "Church-Turing thesis." The thesis states that Turing machines in fact, capture the informal notion of effective method of logic and mathematics, and provide a precise defonition would be algorithim or 'mechanical procedure.'

The machine has an infinate one-dementional tape devided into cells. Traditionally, he tape is shown as hirizontal, with the cells arranged in a left-right orientation. Each cell is able to contain one symbol, which is either '0' or '1'. The machine has a read-write head that at any time will scan a single cell on the tape.
The action of a Turing machine is absolutely determined by three things: (1) The state of the machine; (2) the symbol currently being scanned by the head; (3) A table of transition rules that serve as a type of "program. Each transition rule is a 4-tuple:
< State0, Symbol, Statenext, Action >
that can be translated as: “if the machine is in state State0 and the current cell contains Symbol then move into state Statenext taking Action”. If the machine reaches a situation in which there is not exactly one transition rule specified, i.e., none or more than one, then the machine halts.
In modern terms, the tape serves as the memory of the machine, while the read-write head is the memory bus through which data is accessed (and updated) by the machine. There are two important things to notice about the definition. The first is that the machine's tape is infinite in length, corresponding to an assumption that the memory of the machine is infinite. The second is similar in nature, but not explicit in the definition of the machine, namely that a function will be Turing-computable if there exists a set of instructions that will result in the machine computing the function regardless of the amount of time it takes. One can think of this as assuming the availability of infinite time to complete the computation.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License