|
|
| Line 1: |
Line 1: |
| | | | |
| − | {{MSC|68P05}} | + | {{MSC|68Q05}} |
| | | | |
| | {{TEX|done}} | | {{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]]]). | + | The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. The simulation is realized by using an appropriate transition function. The universality property is of great practical importance. It says that a Turing machine can be adapted to different tasks by ''programming''; from the viewpoint of computability it is not necessary to build special-purpose machines. |
| | | | |
| − | ====Definition of a Turing Machine==== | + | ===Universality of Turing Machines=== |
| | | | |
| − | 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$). | + | A [[Turing machine]] $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function |
| | + | $$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto |
| | + | \begin{cases} j & |
| | + | \text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\ |
| | + | \bot & \text{otherwise} \end{cases}$$ |
| | + | Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ ''simulates'' a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t\circ s) =F_T(s)$. The Turing machine $U$ is called ''universal'', if it can simulate every Turing machine $T$. |
| | | | |
| − | 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$.
| + | ===Existence of a universal Turing Machine=== |
| | | | |
| − | 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.
| + | Via [[Gödelization]] it can be proven that a |
| | + | universal Turing machine exists. The basic idea is as follows: The components |
| | + | of $T$ are coded in $\Sigma^\ast$ giving a Gödel number $g(T)$ |
| | + | (W.r.o.g we assume here that $\Sigma\subset^{\text{fin}}\mathbb{N}$. |
| | + | Furthermore remember, that $\delta$ can be represented as a table). |
| | + | The same strategy is used to code configurations (of $T$) and |
| | + | computations steps (of $T$) in the alphabet $\Sigma$. |
| | | | |
| − | 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.
| + | We will designate the Turing machine $T$ with Gödel number $g(T)$ |
| | + | as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate |
| | + | $M_{g(T)}=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ using its |
| | + | Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the |
| | + | machine $U$ translates $s$ to the corresponding start configuration |
| | + | $c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of |
| | + | $M_{g(T)}$ by looping over the following operation sequence |
| | + | * Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$ |
| | + | * Identify the transition operation to be applied on $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$ |
| | + | * Update $c$ to the new configuration $c'$ using the identified transition operation |
| | + | * Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$. |
| | + | Invalid Gödel numbers are assigned to a Turing machine looping for all inputs. |
| | + | In effect, this gives $ U(g(T)\circ s) = M_{g(T)}(s) $ for all |
| | + | $s\in\Sigma^\ast$. |
| | | | |
| − | ====Representing Algorithms by Turing Machines==== | + | ===Interpretation of Universality=== |
| | | | |
| − | 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. | + | The universality property shows that Turing machines are quite powerful |
| | + | instruments. A Turing machine equipped with a suitable transition function |
| | + | $\delta$ can simulate each other Turing machine. For the other members of |
| | + | the Chomsky-hierarchy this closure property does not hold. Universality |
| | + | has far-reaching consequences for practice. It assures the general-purpose |
| | + | property, i.e. the adaptability to all algorithmical problem-solving tasks |
| | + | by using a corresponding ''program'' as input. |
| | | | |
| − | 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.
| + | On the other hand, universality means a strong limitation as well. It |
| | + | exist uncountable many functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$, |
| | + | but for a universal machine only a countable subset of them is computable. |
| | + | This is caused by the necessary usage of a [[Gödelization]]. |
| | | | |
| − | 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]]).
| + | ===References=== |
| | | | |
| − | ====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|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.
| + | |valign="top"|{{Ref|H77}}||valign="top"| F. Hennie, "Introduction to Computability", Addison-Wesley 1977 |
| − | | + | |- |
| − | ====Comments====
| + | |valign="top"|{{Ref|HU79}}||valign="top"| J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979 |
| − | | + | |- |
| − | 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.
| + | |valign="top"|{{Ref|P81}}||valign="top"| C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981 |
| − | | + | |- |
| − | ====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>
| |
2020 Mathematics Subject Classification: Primary: 68Q05 [MSN][ZBL]
The universality property of Turing machines states that it exists a Turing machine, which can simulate the behaviour of each other Turing machine. The simulation is realized by using an appropriate transition function. The universality property is of great practical importance. It says that a Turing machine can be adapted to different tasks by programming; from the viewpoint of computability it is not necessary to build special-purpose machines.
Universality of Turing Machines
A Turing machine $T=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ can be interpreted as partially defined function
$$F_T\colon\Sigma^\ast \longrightarrow \Sigma^\ast; i \mapsto
\begin{cases} j &
\text{$T$ stops in the final state $q_f\in Q$ with output $j$} \\
\bot & \text{otherwise} \end{cases}$$
Using $F_T$, we are introducing the notions of simulation and universality. A Turing machine $U$ simulates a Turing machine $T$, if $\exists t\in\Sigma^\ast \forall s\in\Sigma^\ast \colon F_U(t\circ s) =F_T(s)$. The Turing machine $U$ is called universal, if it can simulate every Turing machine $T$.
Existence of a universal Turing Machine
Via Gödelization it can be proven that a
universal Turing machine exists. The basic idea is as follows: The components
of $T$ are coded in $\Sigma^\ast$ giving a Gödel number $g(T)$
(W.r.o.g we assume here that $\Sigma\subset^{\text{fin}}\mathbb{N}$.
Furthermore remember, that $\delta$ can be represented as a table).
The same strategy is used to code configurations (of $T$) and
computations steps (of $T$) in the alphabet $\Sigma$.
We will designate the Turing machine $T$ with Gödel number $g(T)$
as $M_{g(T)}$ in the following. Now, a Turing machine $U$ can simulate
$M_{g(T)}=(Q,\Sigma,\Gamma,\sqcup,q_0,q_f,\delta)$ using its
Gödel number $g(T)$. Assuming $M_{g(T)}$ is given the input $s$, the
machine $U$ translates $s$ to the corresponding start configuration
$c_s\in C$ of $T$. Afterwards, $U$ simulates each calculation step of
$M_{g(T)}$ by looping over the following operation sequence
- Identify the actual configuration $c$ of the simulated Turing machine $M_{g(T)}$
- Identify the transition operation to be applied on $c$ according to the (codified) transition function $\delta$ of $M_{g(T)}$
- Update $c$ to the new configuration $c'$ using the identified transition operation
- Stop executing the loop if either no suitable transition operation exist (remember that $\delta$ is a partial function) or if in $c'= (B,i,q)$ it holds $q=q_f$.
Invalid Gödel numbers are assigned to a Turing machine looping for all inputs.
In effect, this gives $ U(g(T)\circ s) = M_{g(T)}(s) $ for all
$s\in\Sigma^\ast$.
Interpretation of Universality
The universality property shows that Turing machines are quite powerful
instruments. A Turing machine equipped with a suitable transition function
$\delta$ can simulate each other Turing machine. For the other members of
the Chomsky-hierarchy this closure property does not hold. Universality
has far-reaching consequences for practice. It assures the general-purpose
property, i.e. the adaptability to all algorithmical problem-solving tasks
by using a corresponding program as input.
On the other hand, universality means a strong limitation as well. It
exist uncountable many functions $f\colon\mathbb{N}\rightarrow\mathbb{N}$,
but for a universal machine only a countable subset of them is computable.
This is caused by the necessary usage of a Gödelization.
References
| [H77] |
F. Hennie, "Introduction to Computability", Addison-Wesley 1977
|
| [HU79] |
J. Hopcroft, J. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley 1979
|
| [P81] |
C. Papdimitriou, "Elements of the theory of computation", Prentice-Hall 1981
|