In the 1930's (before the advent of the digital computer) several mathematicians began to think about what it means to be able to compute a function. Alonzo Church and Alan Turing independently arrived at equivalent conclusions. As we might phrase their common definition now:
A function is computable if it can be computed by a Turing machine.
A Turing machine is a very simple machine, but, logically speaking, has all the power of any digital computer. It may be described as follows: A Turing machine processes an infinite tape. This tape is divided into squares, any square of which may contain a symbol from a finite alphabet, with the restriction that there can be only finitely many non-blank squares on the tape. At any time, the Turing machine has a read/write head positioned at some square on the tape. Furthermore, at any time, the Turing machine is in any one of a finite number of internal states. The Turing machine is further specified by a set of instructions of the following form:(current_state, current_symbol, new_state, new_symbol, left/right)
This instruction means that if the Turing machine is now in current_state
, and the symbol under the read/write head is current_symbol
, change its internal state to new_state
, replace the symbol on the tape at its current position by new_symbol
, and move the read/write head one square in the given direction (left
). If a Turing machine is in a condition for which it has no instruction, it halts.
Nowadays it is natural to think of the set of instructions as a program for the Turing machine.
There are several conventions commonly used in Turing machines (and several slightly different, though of course logically equivalent, definitions of them). We adopt the convention that numbers are represented in unary notation, i.e., that the non-negative integer n is represented by a string of n+1 successive1s. Furthermore, if we want to compute a function f(n1,n2, ... ,nk), we assume that initially the tape consists of n1, n2, ... , nk, properly encoded, with each separated from the previous one by a single blank, and with the tape head initially poised over the left-most bit of the first argument, and the state of the Turing machine some initial specified value. We say that the Turing machine has computed m = f(n1,n2,,,,nk) if, when the machine halts, the tape consists of n1, n2, ... , nk, m, properly encoded, and separated by single blanks, and the read/write head back at the left-most bit of the first argument.
For example, suppose we wish to create a Turing machine to compute the functionm = multiply(n1,n2) = n1 * n2
Suppose the input tape reads
_<1>1 1 1 _ 1 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
which encodes 3 and 4 respectively, in unary notation. (Here the position of the read/write head is marked.) Then the Turing machine should halt with its tape reading
_<1>1 1 1 _ 1 1 1 1 1 _ 1 1 1 1 1 1 1 1 1 1 1 1 1 _ _ _ _ _
which encodes 3, 4, and 12 in unary notation.
The very simplicity of a Turing machine makes it a challenge to program one to perform a specific computation. You are urged to try to write a program to multiply two integers yourself. Here is a multiplication program together with sample output (not just the initial and final states of the tape, but the state at each intermediate stage). You can run your program on the Virtual Turing Machine (which was where this program was run).
Note: The Virtual Turing Machine provides instructions on how to code and run a program. One point should be noted: Although the tape on a Turing machine is infinite, in this implementation the tape is finite, and the Turing machine halts if it runs past either end of the tape. Thus, you should be sure to supply a tape with enough blank spaces to be able to perform your computation.
For further information on Alan Turing, see the Alan Turing Home Page, which is maintained by Andrew Hodges, author of the biography Alan Turing: The Enigma.
-- Steven Weintraub