Turing Machines

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 or right). 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 function

m = 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.

If you want to know more about these machines. you can mail me.

[Home]