Namespaces
Variants
Actions

Difference between revisions of "User:Joachim Draeger/sandbox"

From Encyclopedia of Mathematics
Jump to: navigation, search
Line 1: Line 1:
  
 +
{{MSC|68P05}}
  
 +
{{TEX|done}}
  
 +
The name attached to abstract computers (cf. [[Computer, abstract|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|algorithm]]. In the course of development of the theory of algorithms (cf. [[Algorithms, theory of|Algorithms, theory of]]), there emerged a number of modifications of the original definition of Turing. The version given here goes back to E. Post [[#References|[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 [[#References|[3]]] and [[#References|[4]]]).
  
{{MSC|68P05}}
+
====Definition of a Turing Machine====
  
{{TEX|done}}
+
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|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.
  
The name attached to abstract computers (cf. [[Computer,  abstract|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|algorithm]]. In the course of  development of the theory of algorithms (cf. [[Algorithms, theory  of|Algorithms, theory of]]), there emerged a number of modifications of  the original definition of Turing. The version given here goes back to  E. Post [[#References|[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 [[#References|[3]]] and  [[#References|[4]]]).
+
====Representing Algorithms by Turing Machines====
  
====Definition of a Turing Machine====
+
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.
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|alphabet]] <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944601.png" /> 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" ). 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 <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944602.png" /> or the blank).
 
  
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 <img  align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944603.png" />, then one usually  says that this machine is a Turing machine in the alphabet <img  align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944604.png" />.
+
There are strong grounds for supposing that the precise description of the general idea of an [[Algorithm|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|Church thesis]] (for partial recursive functions) or the normalization principle (for normal algorithms, cf. [[Normal algorithm|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.
  
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.
+
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|Automaton]]; [[Automata, theory of|Automata, theory of]]).
  
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.
+
====The Zoo of Turing Machine Definitions====
  
====Representing Algorithms by Turing Machines====
+
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|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.
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  <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944605.png" /> is meant any  algorithm <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944606.png" /> of the following  kind. One takes a fixed Turing machine <img align="absmiddle"  border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944607.png" /> in the alphabet <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944608.png" />. Let <img  align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t0944609.png" /> be the word in <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446010.png" /> taken as the  initial data for the algorithm <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446011.png" />. The following  initial configuration of the machine <img align="absmiddle"  border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446012.png" /> is constructed: 1) the word <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446013.png" /> is written on the tape without gaps, the remaining cells being left empty (i.e. blank);  2) the machine <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446014.png" /> is set up to scan  the cell with the first letter of the word <img align="absmiddle"  border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446015.png" />; and  3) <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446016.png" /> is put into the  initial state (if <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446017.png" /> is empty, then  the tape is chosen to be empty, and the scanned cell is any cell). Suppose that <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446018.png" />, starting from  this initial configuration, completes its functi
 
oning. Consider the cell  of the tape being scanned by <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446019.png" /> in the final  configuration. If the symbol printed on it is blank, then <img  align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446020.png" /> is taken to be  the empty word. Otherwise, <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446021.png" /> 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|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 <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446022.png" /> in some alphabet  it is possible to construct a Turing algorithm giving the same results  under the same initial data as the algorithm <img align="absmiddle"  border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446023.png" />. 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|Church thesis]] (for partial recursive functions) or  the normalization principle (for normal algorithms, cf. [[Normal  algorithm|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.
+
====Comments====
  
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|Automaton]]; [[Automata, theory of|Automata, theory of]]).
+
See also [[Algorithm, complexity of description of an|Algorithm, complexity of description of an]]; [[Algorithm, computational complexity of an|Algorithm, computational complexity of an]]; [[Complexity theory|Complexity theory]]; [[Computable function|Computable function]]; [[Formal languages and automata|Formal languages and automata]]; [[Machine|Machine]]; [[Undecidability|Undecidability]]. Consult [[#References|[a1]]] and [[#References|[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.
 
 
====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  <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446024.png" /> is  (algorithmically) computable relative to a function <img  align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446025.png" /> if there exists a  multi-tape Turing machine that computes <img align="absmiddle"  border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446026.png" /> under  the condition that in any initial configuration all the values of  <img align="absmiddle" border="0"  src="https://www.encyclopediaofmath.org/legacyimages/t/t094/t094460/t09446027.png" /> 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|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.
 
  
 
====References====
 
====References====
See also [[Algorithm, complexity of description of an|Algorithm, complexity of  description of an]]; [[Algorithm, computational complexity of  an|Algorithm, computational complexity of an]]; [[Computable  function|Computable function]]; [[Machine|Machine]].
 
 
<table><TR><TD  valign="top">[1a]</TD> <TD valign="top">  A.M. Turing,    "On computable numbers, with an application to the  Entscheidungsproblem"  ''Proc. London Math. Soc. (2)'' , '''42'''  (1937)  pp. 230–265</TD></TR><TR><TD  valign="top">[1b]</TD> <TD valign="top">  A.M. Turing,    "On computable numbers with an application to the Entscheidungsproblem, a  correction"  ''Proc. London Math. Soc. (2)'' , '''43'''  (1937)  pp.  544–546</TD></TR><TR><TD  valign="top">[2]</TD> <TD valign="top">  E.L. Post,    "Finite combinatory processes - formulation 1"  ''J. Symbolic Logic'' ,  '''1''' :  3  (1936)  pp. 103–105</TD></TR><TR><TD  valign="top">[3]</TD> <TD valign="top">  S.C. Kleene,    "Introduction to metamathematics" , North-Holland  (1951)</TD></TR><TR><TD  valign="top">[4]</TD> <TD valign="top">  A.I. Mal'tsev,    "Algorithms and recursive functions" , Wolters-Noordhoff  (1970)  (Translated from Russian)</TD></TR><TR><TD  valign="top">[5]</TD> <TD valign="top">  E. Mendelson,    "Introduction to mathematical logic" , v. Nostrand  (1964)</TD></TR><TR><TD  valign="top">[6]</TD> <TD valign="top">  M. Minsky,    "Computation: finite and infinite machines" , Prentice-Hall  (1967)</TD></TR><TR><TD  valign="top">[7]</TD> <TD valign="top"> , ''Turing  machines and recursive functions'' , Moscow  (1972)  (In Russian;  translated from German)</TD></TR></table>
 
  
====Comments====
 
See  also [[Complexity theory|Complexity theory]]; [[Formal languages and  automata|Formal languages and automata]];  [[Undecidability|Undecidability]]. Consult [[#References|[a1]]] and  [[#References|[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====
+
<table><TR><TD valign="top">[1a]</TD> <TD valign="top"> A.M. Turing, "On computable numbers, with an application to the Entscheidungsproblem" ''Proc. London Math. Soc. (2)'' , '''42''' (1937) pp. 230–265</TD></TR><TR><TD valign="top">[1b]</TD> <TD valign="top"> A.M. Turing, "On computable numbers with an application to the Entscheidungsproblem, a correction" ''Proc. London Math. Soc. (2)'' , '''43''' (1937) pp. 544–546</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> E.L. Post, "Finite combinatory processes - formulation 1" ''J. Symbolic Logic'' , '''1''' : 3 (1936) pp. 103–105</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top"> A.I. Mal'tsev, "Algorithms and recursive functions" , Wolters-Noordhoff (1970) (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top"> E. Mendelson, "Introduction to mathematical logic" , v. Nostrand (1964)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top"> M. Minsky, "Computation: finite and infinite machines" , Prentice-Hall (1967)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top"> , ''Turing machines and recursive functions'' , Moscow (1972) (In Russian; translated from German)</TD></TR><TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Salomaa, "Formal languages" , Acad. Press (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> A. Salomaa, "Computation and automata" , Cambridge Univ. Press (1985)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> M. Davis, "Computability and unsolvability" , McGraw-Hill (1958)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> J.E. Hopcroft, J.D. Ulman, "Introduction to automata theory, languages and computation" , Addison-Wesley (1979)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> C.H. Papdimitriou, "Elements of the theory of computation" , Prentice-Hall (1981)</TD></TR></table>
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> A. Salomaa,   "Formal languages" , Acad. Press   (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> A. Salomaa,   "Computation and automata" , Cambridge Univ. Press   (1985)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> M. Davis,   "Computability and unsolvability" , McGraw-Hill   (1958)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> J.E. Hopcroft,   J.D. Ulman,   "Introduction to automata theory, languages and computation" , Addison-Wesley   (1979)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> C.H. Papdimitriou,   "Elements of the theory of computation" , Prentice-Hall   (1981)</TD></TR></table>
 

Revision as of 12:42, 21 July 2013

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)
How to Cite This Entry:
Joachim Draeger/sandbox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Joachim_Draeger/sandbox&oldid=29991