本文共 7529 字,大约阅读时间需要 25 分钟。
A Turing machine consists of:
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.
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 l: it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skip 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 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 , which was already shown to be undecidable in Turing's original paper, and .
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 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.
A universal Turing machine is . It can calculate any , decide any , and accept any . According to the , 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 in Heidelberg, Germany.
" rel="nofollow">Upload files
This page has been accessed 1826 times. Other namespaces :
Last edited: Saturday, June 22, 2002, 13:14
来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10748419/viewspace-959367/,如需转载,请注明出处,否则将追究法律责任。
转载于:http://blog.itpub.net/10748419/viewspace-959367/