Redirected from Universal Turing machine
The Turing machine is an abstract model of computer execution and storage introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.
Turing machines shouldn't be confused with the Turing test, Turing's attempt to capture the notion of artificial intelligence.
A Turing machine that is able to simulate any other Turing machine is called a universal Turing machine.
|
A Turing machine consists of:
Old Read Wr. New Old Read Wr. New St. Sym. Sym. Mv. St. St. Sym. Sym. Mv. St. - - - - - - - - - - - - - - - - - - - - - - - - s1 1 -> 0 R s2 s4 1 -> 1 L s4 s2 1 -> 1 R s2 s4 0 -> 0 L s5 s2 0 -> 0 R s3 s5 1 -> 1 L s5 s3 0 -> 1 L s4 s5 0 -> 1 R s1 s3 1 -> 1 R s3
A computation of this Turing machine might for example be: (the position of the head is indicated by displaying the cell in bold face)
Step State Tape Step State Tape - - - - - - - - - - - - - - - - - 1 s1 11 9 s2 1001 2 s2 01 10 s3 1001 3 s2 010 11 s3 10010 4 s3 0100 12 s4 10011 5 s4 0101 13 s4 10011 6 s5 0101 14 s5 10011 7 s5 0101 15 s1 11011 8 s1 1101 -- halt --
The behavior of this machine can be described as a loop: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1's and the first 0 encountered. S3 then skips over the next sequence of 1's (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1's until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1's until it finds the 0 that was originally written by s1. It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop. This continues until s1 finds a 0 (this is the 0 right in the middle between the two strings of 1's) at which time the machine halts.
Every Turing machine computes a certain fixed partial function from the input strings over its alphabet. In that sense it behaves like a computer with a fixed program. However, as Alan Turing already described, we can encode the action table of any Turing machine in a string. Thus we might try to construct a Turing machine that expects on its tape a string describing an action table followed by a string describing the input tape, and then computes the tape that the encoded Turing machine would have computed. As Turing showed, such a Turing machine is indeed possible and since it is able to simulate any other Turing machine it is called a universal Turing machine.
With this encoding of action tables as strings, it becomes in principle possible for Turing machines to answer questions about the behavior of other Turing machines. Most of these questions however are undecidable, see for instance the Halting problem, which was already shown to be undecidable in Turing's original paper, and Rice's theorem.
If we broaden the definition to include any Turing machine that simulates some Turing-complete computational model, not just Turing machines that directly simulate other Turing machines, a universal Turing machine can be fairly simple, using just a few states and a few symbols. For example, only 2 states are needed, since a 2×18 (meaning 2 states, 18 symbols) universal Turing machine is known. A complete list of the smallest known universal Turing machines is: 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2. These simulate a computational model called tag-systems.
A universal Turing machine is Turing-complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.
It is not difficult to simulate a Turing Machine on a modern computer (except for the limited memory of actually existing computers).
It is also possible to build a Turing Machine on a purely mechanical basis. The mathematician Karl Scherer[?] has indeed built such a machine in 1986 using metal and plastic construction sets, and some wood. The 1.5 meter high machine uses the pulling of strings to read, move and write the data (which is represented using ball bearing balls).
The machine is now exhibited in the entrance of the Department of Computer Science of the University of Heidelberg, Germany.
Let A and S be finite, nonempty sets (the "alphabet" and the "set of states," respectively) and Z be the set of integers. One of the elements of S is singled out as the start state and we will denote it by *. Let T be the set of doubly-infinite sequences of elements of A (functions from Z to A, "set of tapes.") Let X=S×Z×T be the set of all triplets (s,n,t) where s is in S, n is in Z and t is in T (the set of "complete machine data.") Let r be a total binary relation from S×A to {-1,0,1}×S×A (the "transition rule".) (Note that there are finitely many such relations.) The set X0 is the subset of X so that, for each (s,n,t) in X0, s=* and n=0 (the set of "admissible initial conditions.") For any x=(a,b,c) in X, we will denote its tape by t(x) (=c).
Such a set-up (the data (A,S,r), or more implicitly, r) is called a Turing machine.
We define a new relation R from X to X as follows. (a,b,c)×(d,e,f) is in R if, and only if:
If the relation r is a function, then so is R and the Turing machine is said to be deterministic, otherwise it is said to be nondeterministic.
If x0,x1,x2,... is a sequence in X so that, for every k:
the sequence x0,x1,x2,... is said to be a run or execution of the Turing machine r. If the Turing machine is deterministic, then such a sequence is always completely determined by x0 since xk+1=R(xk) for everk k. On the other hand, if the Turing machine is nondeterministic, there will likely be two (or more) runs of the Turing machine, say x0,x1,x2,... and y0,y1,y2,..., which are different but such that x0=y0.
If x is an element of X such that x×x is in R, we say that x is a stopping state.
If x0,x1,x2,... is a run of the Turing machine and if, for some j, xj is a stopping state, we say that the execution has terminated at time j. The running time of the execution is the smallest j which is a termination time for x. If x does not terminate, we say that its running time is ∞. If x is an execution, we will denote its running time by |x|
In the case of deterministic Turing machines, observe that the running time of an execution depends only on x0 and not on all of the data in x1,x2,... On the other hand, if the Turing machine is nondeterministic, x0 is insufficient to compute the running time of the entire sequence. However, we wish to define the running time given only x0 and so a supplemental step is taken.
We will define g(z), a function of X0, to be the set of all executions x0,x1,x2,... with the shortest running time and with x0=z. If the Turing machine is deterministic, then there is only one possible execution. If the Turing machine is nondeterministic, many executions will satisfy x0=z and g(z) is the set of those satisfactory executions with the least running time.
Then, the running time of the Turing machine given the initial situation z in X0 is the running time of any execution in g(z), whether the machine is deterministic or not. In the deterministic case, g(z) also gives the only possible execution, but in the nondeterministic case, g(z) lists all possible executions. We shall now write |z| for |g(z)|, the running time of z for any z in X0.
Let f be any function from U to T where U is some subset of T. We say that f is computable if there exists a Turing machine such that, for all a in U:
An arbitrary function from U to T is usually thought of as a "problem". For instance, A might contain the digits from 0 to 9 and the decimal point, and U might be the set of all real numbers, and f might compute the square root of any number written on U. This function f would be the "square root problem." This problem is clearly not computable because, for instance, the square root of two is irrational, and hence no Turing machine could ever write it out completely on the tape in finite time.
The prototypical non-computable problem is the halting problem.
x0,x1,x2,... and y0,y1,y2,... are executions of two possibly different Turing machines with the same alphabet A, we say that these executions are equivalent if
If r and s are Turing machines with the same alphabet, we say that s generalizes or subsumes r when, for any execution x of r, there is an execution y of s so that x and y are equivalent.
If two Turing machines subsume each other, we say that they are equivalent. The reader may check that if r is any nondeterministic Turing machine, it is equivalent to some deterministic Turing machine s. However, there is a more interesting notion of equivalence.
Let @ be some special symbol in A. If t is a tape in T, then by size of the input (or size of t, or |t|) we shall mean the smallest n so that, for any |k|>n, tk is @. The size of t may be ∞.
We say that a Turing machine r runs in polynomial time if for any z in X0, the running time |z| is bounded above by some polynomial in the length of the tape |t(z)|. The set of deterministic Turing machines which run in polynomial time is denoted by P, while the set of nondeterministic Turing machines that run in polynomial time is denoted NP. It is fairly clear that any polynomial time deterministic Turing machine is equivalent to some polynomial time nondeterministic Turing machine (the only thing to do is to add some nondeterminism without changing the shortest executions.)
Some well known problems (satisfiability, the traveling salesman problem, etc...) are known to be solvable by machines in NP, but so far we have been unable to find machines in P to solve them. One of the most fundamental open questions in theory of computation is:
This is known as the "P=NP?" problem. See Complexity classes P and NP.
wikipedia.org dumped 2003-03-17 with terodump