Home Archive catalogue Bio of Turing More about Turing Codebreaking Artificial Intelligence Computer history Photo gallery Books on Turing Cambridge archive Links Copyright |
## What is a Turing Machine?## By Jack Copeland## © Copyright B.J. Copeland, July 2000- The head and the tape
- States
- Atomic operations
- The instruction table
- An example
- Universal Turing machines
- Computable numbers
- Uncomputable numbers
- Computable and uncomputable functions
Turing first described the Turing machine in an article published in 1936, 'On Computable Numbers, with an Application to the Entscheidungsproblem', which appeared in ## The head and the tapeA Turing machine is an idealised computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation. The input that is inscribed on the tape before the computation starts must consist of a finite number of symbols. However, the tape is of unbounded length--for Turing's aim was to show that there are tasks that these machines are unable to perform, even given unlimited working memory and unlimited time.
The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head's internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed). ## StatesThe head contains a subdevice that I call the ## Atomic operationsThere are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can: - read (i.e. identify) the symbol currently under the head
- write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
- move the tape left one square
- move the tape right one square
- change state
- halt.
These are called the Commercially available computers are hard-wired to perform primitive operations considerably more sophisticated than those of a Turing machine--add, multiply, decrement, store-at-address, branch, and so forth. The precise constitution of the list of primitives varies from manufacturer to manufacturer. It is a remarkable fact that none of these computers can outdo a Turing machine. Despite the Turing machine's austere simplicity, it is capable of computing anything that any computer on the market can compute. Indeed, since it is an abstract or notional machine, a Turing machine can compute It is sometimes said, incorrectly, that a Turing machine is necessarily slow, since the head is continually shuffling backwards and forwards, one square at a time, along a tape of unbounded length. But since a Turing machine is an idealised device, it has no real-world constraints on its speed of operation. ## The instruction tableA program or 'instruction table' for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:
In place of - - - may be written either 'move left one square' or 'move right one square' or 'halt'. ## An exampleThe machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1..., working to the right from its starting place, and leaving a blank square in between each digit. In order to do its work the machine makes use of four states, labelled ' The table of instructions for this machine is as follows.The top line of the table reads: if you are in state
A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank. ## Universal Turing machinesThere are in fact two ways of arranging for a Turing machine to act in accordance with a machine table or program. One, as already mentioned, is to appropriately modify the 'wiring' in the head of a Turing machine. The other is to translate the machine table into, say, binary code and inscribe the result on the tape of a special type of Turing machine known as a Turing was able to demonstrate that there is a table U which is such that if the head of a Turing machine is programmed in accordance with U, and if any table whatsoever, P, is translated and written out on the machine's tape, then the machine will behave There are many different tables that will do the work of U and thus many distinct universal Turing machines, all equivalent in computational power. The most economical such table is due to Marvin Minsky. Using an alphabet of four symbols and making use of only seven states, this table consists of just 28 instructions! Turing's greatest contribution to the development of the digital computer were - this idea of controlling the function of a computing machine by storing a program of symbolically, or numerically, encoded instructions in the machine's memory, and
- his proof that, by this means, a
*single*machine--a universal machine--is able to carry out every computation that can be carried out by any other Turing machine whatsoever.
## Computable numbersA Turing machine program is said to An example of a non-terminating Turing machine program is a program that calculates sequentially each digit of the decimal representation of pi (say by using one of the standard power series expressions for pi). A Turing machine running this program will spend all eternity writing out the decimal representation of pi digit by digit, 3.14159 . . . Turing called the numbers that can be written out by a Turing machine the ## Uncomputable numbersStraight off, one might expect it to be the case that However, Turing was able to prove that not every real number is computable. The decimal representations of some real numbers are so completely lacking in pattern that there simply is no finite table of instructions of the sort that can be followed by a Turing machine for calculating the nth digit of the representation, for arbitrary n. In fact, computable numbers are relatively scarce among the real numbers. There are only countably many computable numbers, whereas--as the mathematician Georg Cantor showed in 1874--there are uncountably many real numbers. (A set is countable if and only if either it is finite or its members can be put into a one-to-one correspondence with the integers.) ## Computable and uncomputable functionsFollowing Turing, to say that a mathematical Addition over the integers is a computable function, whereas addition over the real numbers is not a computable function. This is because there is no way even of inscribing the inputs x and y on a Turing machine's tape if x and y are uncomputable numbers. (Remember that the input must consist of a finite number of symbols.) Is addition over the The answer is Thus Turing has given us a new method for representing numbers. In this system, there are |

Loading

Site created and maintained by Jack Copeland

All rights reserved

All rights reserved