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.
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 method 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.
Informal description
The Turing machine mathematically models a machine that mechanically operates on a tape. On this tape are symbols, which the machine can read and write, one at a time, using a tape head.-Operation is fully determined by a finite set of elementary instructions such as " in state 42, if the symbol seen is 0, write a 1; if the symbol seen is 1, change into state 17; in state 17, if the symbol seen is 0, write a 1 and change to state 6;" etc. In the original article(" On computable numbers, with an application to the Entscheidungsproblem ", see also references below. Turing imagines not a mechanism, but a person whom he calls the " computer ", who executes these deterministic mechanical rules slavishly( or as Turing puts it, " in a desultory manner ").
q 4 S 1 S 2 S 3 S 1 S 0 S 1
The head is always over a particular square of the tape; only a finite stretch of squares is shown. The instruction to be performed( q) is shown over the scanned square.( Drawing after Kleene( 1952) p. 375.)
4
Here, the internal state( q is shown inside the head, and the illustration describes the tape
1 as being infinite and pre-filled with " 0 ", the symbol serving as blank. The system ' s full state( its complete configuration) consists of the internal state, any non-blank symbols on the tape( in this illustration " 11 B "), and the position of the head relative to those symbols including blanks, i. e. " 011B ".( Drawing after Minsky( 1967) p. 121).
( 61)