Turing machine
From Wikipedia, the free encyclopedia.
Printable version | Pages that link here
12.234.196.121
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages
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 Turing's thesis.
Definition
A Turing machine consists of:
A tape which is divided into cells, one next to the other. Each cell contains a symbol from some finite alphabet. The alphabet contains a special blank symbol (here written as '0') and one or more other symbols. The tape is assumed to be arbitrarily extendible to the left and to the right, i.e., the Turing machine is always supplied with as much tape as it needs for its computation. Cells that have not been written to before are assumed to be filled with the empty symbol.
A head that can read and write symbols on the tape and move left and right.
A state register that stores the state of the Turing machine. The number of different states is always finite and there is one special start state with which the state register is initialized.
An action table that tells the machine what symbol to write, how to move the head ('L' for one step left, and 'R' for one step right) and what its new state will be, given the symbol it has just read on the tape and the state it is currently in. If there is no entry in the table for the current combination of symbol and state then the machine will halt.
Note that every part of the machine is finite, but it is the potentially unlimited amount of tape that gives it an unbounded amount of storage space.
Example:
The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1's on the tape, with the head initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e., "111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.
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.
The Universal Turing Machine
Every Turing machine computes a certain fixed partial function over the 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 every 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.
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. The oldest of these is the 4×6 designed by Marvin Minsky in 1967. It is given in this table, where each row is a state, each column is a symbol, and each box contains the symbol to write, the direction to move the head, and the new state.
1
2
3
4
5
6
7
A
1←B
1←B
3←A
4←A
5→A
6→A
7→B
B
1←B
2→A
HALT
5→A
3←A
3←D
6→A
C
2←C
2→D
3←D
7←C
5→D
6→D
7→C
D
1←C
3←A
4←C
4←C
5→C
6→C
2→B
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.
A Physical Turing Machine
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 in Heidelberg, Germany.
References:
Turing, A., On Computable Numbers, With an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Soceity, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965; (online version)
Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980.
Minsky, M. L., Computation: Finite and Infinite Machines, Prentice Hall, Englewood Cliffs, NJ, 1967. (gives 7×4 universal Turing machine. The transition table is here)
Rogozhin, Yurii, "Small Universal Turing Machines", Theoretical Computer Science, 168:215-240, 1996. (gives 4×6 and 2×18 universal Turing machines).
Rogozhin, Yurii, "A Universal Turing Machine with 22 States and 2 Symbols", Romanian Journal Of Information Science and Technology, 1(3), 259-265, 1998. (gives 22×2 and surveys known results)
External References:
Turing Machines created in the form of software 'games': (game 1)(game 2)
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages
This page has been accessed 1826 times. Other namespaces : Talk
Last edited: Saturday, June 22, 2002, 13:14 (diff)
