User:Joachim Draeger/sandbox

2020 Mathematics Subject Classification: Primary: 68P05 [MSN][ZBL]

The name attached to abstract computers (cf. Computer, abstract) of a specific type. The concept of a machine of such a kind originated in the middle of the 1930's from A.M. Turing as the result of an analysis carried out by him of the actions of a human being carrying out some or other calculations in accordance with a plan worked out in advance, that is, carrying out successive transformations of complexes of symbols. This analysis, in turn, was carried out by him with the aim of solving the then urgent problem of finding a precise mathematical equivalent for the general intuitive idea of an algorithm. In the course of development of the theory of algorithms (cf. Algorithms, theory of), there emerged a number of modifications of the original definition of Turing. The version given here goes back to E. Post [2]; in this form the definition of a Turing machine has achieved widespread popularity (the Turing machine has been described in detail, for example, in [3] and [4]).

Definition of a Turing Machine

A Turing machine is conveniently represented as an automatically-functioning system capable of being in a finite number of internal states and endowed with an infinite external memory, called a tape. Two of the states are distinguished, the initial state and the final state. The tape is divided into cells and is unbounded to the left and to the right. Any letter of some finite alphabet $\Gamma$ can be printed on each cell of the tape (for the sake of uniformity, it is convenient to regard an empty cell as being printed with a "blank" $\sqcup\in\Gamma$ ). At each moment of discrete time the Turing machine is in one of its states, and by scanning one of the cells of its tape it perceives the symbol written there (a letter of the alphabet $\Gamma$).

If the Turing machine is in a non-final state at some moment of time, it completes a step, which is completely determined by its current state and the symbol that is perceived on the tape at this moment. A step consists of the following: 1) print a new symbol in the scanned cell, which may be the same as the old symbol or a blank; 2) go to a new state, which may be the same as the old one or the final state; and 3) move the tape to the left or to the right by one cell, or keep it in the same place. The list of all possible steps of the Turing machine in dependence on the current combination of "non-final state + symbol perceived" can be represented, for example, by a special table with two inputs, called the program, or scheme, of the given Turing machine. The codes of the corresponding steps of the machine, called its commands, are placed in the cells of this table. The program of the Turing machine is an object with a given structure, and one can stipulate that the Turing machine be identified with its program. If one wants to emphasize the connection of such a Turing machine with the alphabet $\Gamma$, then one usually says that this machine is a Turing machine in the alphabet $\Gamma$.

The complete description of the current state of a Turing machine is given by its configuration, consisting of the following information at the given moment: 1) the actual symbols filling the cells of the tape; 2) the cell currently being scanned by the machine; and 3) the internal state of the machine. A configuration corresponding to the final state of the Turing machine is also called final.

If some non-final configuration of the Turing machine is fixed as the initial configuration, then the functioning of this machine will consist of a (step by step) sequential transformation starting with the initial configuration in accordance with the machine's program until the time of attaining a final configuration. After this, the functioning of the Turing machine is considered ended and the final configuration attained is regarded as the result of the functioning of the machine. Of course, the functioning of the Turing machine does not, in general, terminate for every initial configuration.

Representing Algorithms by Turing Machines

The notion of a Turing machine can be used for making precise the general idea of an algorithm in a given alphabet, as follows. By a Turing algorithm in an alphabet $\Gamma$ is meant any algorithm $\mathcal{A}$ of the following kind. One takes a fixed Turing machine $\mathcal{M}$ in the alphabet $\Gamma$. Let $P\in (\Gamma\setminus\{\sqcup\})^\ast$ be the word taken as the initial data for the algorithm $\mathcal{A}$. The following initial configuration of the machine $\mathcal{M}$ is constructed: 1) the word $P$ is written on the tape without gaps, the remaining cells being left empty (i.e. blank); 2) the machine $\mathcal{M}$ is set up to scan the cell with the first letter of the word $P$; and 3) $\mathcal{M}$ is put into the initial state (if $P$ is empty, then the tape is chosen to be empty, and the scanned cell is any cell). Suppose that $\mathcal{M}$, starting from this initial configuration, completes its functioning. Consider the cell of the tape being scanned by $\mathcal{M}$ in the final configuration. If the symbol printed on it is blank, then $\mathcal{A}(P)$ is taken to be the empty word. Otherwise, $\mathcal{A}(P)$ is taken to be the word printed on the maximum segment of the tape including the scanned cell and not containing any blanks.

There are strong grounds for supposing that the precise description of the general idea of an algorithm in an alphabet carried out by means of the notion of a Turing machine is adequate. Namely, it is held that for every algorithm $\mathcal{A}$ in some alphabet it is possible to construct a Turing algorithm giving the same results under the same initial data as the algorithm $\mathcal{A}$. This convention is known in the theory of algorithms as the Turing thesis. The acceptance of the Turing thesis is equivalent to the acceptance of the Church thesis (for partial recursive functions) or the normalization principle (for normal algorithms, cf. Normal algorithm). However, in contrast to the latter two, the Turing thesis is immediately highly convincing. In fact, by carrying out computations according to a selected plan, the mathematician acts in a way similar to a Turing machine: in considering some position in his writings and being in a certain "state of mind" , he makes the necessary alterations in his writing, is inspired by a new "state of mind" , and goes on to contemplate further writing. The fact that he completes more complicated steps than a Turing machine seems not principally significant.

In terms of the structure of their description and the type of functioning, Turing machines are automata of a very general kind, so that Turing's conception has to a considerable extent stimulated the origin of the abstract theory of automata and largely predetermined their particular properties (cf. Automaton; Automata, theory of).

The Zoo of Turing Machine Definitions

There are many modifications of Turing machines. The most widespread are multi-tape Turing machines, with one or several heads for each of its tapes. The motion of the heads and the printing of the letters on the tape are carried out simultaneously according to the program of the control system. Multi-tape Turing machines are conveniently used in the formalization of the notion of a relative algorithm. Thus, a function $f$ is (algorithmically) computable relative to a function $g$ if there exists a multi-tape Turing machine that computes $f$ under the condition that in any initial configuration all the values of $g$ are printed in fixed order on one of the tapes. In this form one can, in terms of relative computations, introduce the important notion of Turing reducibility in the theory of algorithms, as well as other forms of algorithmic reducibility. It is natural to formalize the concept of a probabilistic algorithm by means of multi-tape Turing machines. A common approach consists of the following: A random sequence is printed on one of the tapes of the multi-tape Turing machine; the Turing machine then deals with exactly one symbol of this sequence at each instant. In a second approach, the program of the control system of the Turing machine will allow the existence of several commands with the same left-hand sides, the choice of one or other of the commands then being carried out with prescribed probabilities. The notion of a non-deterministic Turing machine is based on a similar idea. Here again, the program of the control system can have several commands with the same left-hand sides. In both cases, instead of a single computation for a given input, one considers the class of all possible computations compatible with the program. For probabilistic Turing machines the probability of such computations is considered; for non-deterministic Turing machines one considers the possibility of the computation itself.

Comments

See also Algorithm, complexity of description of an; Algorithm, computational complexity of an; Complexity theory; Computable function; Formal languages and automata; Machine; Undecidability. Consult [a1] and [a2] for the importance of a Turing machine as a formalization of the intuitive notion of an algorithm and for the Church thesis, as well as for the relation of Turing machines to complexity theory in general.

References

[1a]	A.M. Turing, "On computable numbers, with an application to the Entscheidungsproblem" Proc. London Math. Soc. (2) , 42 (1937) pp. 230–265
[1b]	A.M. Turing, "On computable numbers with an application to the Entscheidungsproblem, a correction" Proc. London Math. Soc. (2) , 43 (1937) pp. 544–546
[2]	E.L. Post, "Finite combinatory processes - formulation 1" J. Symbolic Logic , 1 : 3 (1936) pp. 103–105
[3]	S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)
[4]	A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)
[5]	E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)
[6]	M. Minsky, "Computation: finite and infinite machines" , Prentice-Hall (1967)
[7]	, Turing machines and recursive functions , Moscow (1972) (In Russian; translated from German)
[a1]	A. Salomaa, "Formal languages" , Acad. Press (1973)
[a2]	A. Salomaa, "Computation and automata" , Cambridge Univ. Press (1985)
[a3]	M. Davis, "Computability and unsolvability" , McGraw-Hill (1958)
[a4]	J.E. Hopcroft, J.D. Ulman, "Introduction to automata theory, languages and computation" , Addison-Wesley (1979)
[a5]	C.H. Papdimitriou, "Elements of the theory of computation" , Prentice-Hall (1981)