Turing Machines

Turing_Machine_Model_Davey_2012

As a mathematician, Alan Turing was interested in mathematical logic, and in particular with the foundations of mathematics. In 1935 he learnt from M.H.A. Newman that Hilbert’s Entsceidungsproblem (decision problem) was open: could there be a definite method to determine if any given mathematical statement was provable? To answer this, he analysed what a human ‘computer’ would do, and derived a simplified model that seemed capable of performing autmomatic calculation.

A Turing machine is a device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a computer. The “Turing” machine was described by Alan Turing in 1936, who called it an “a(utomatic)-machine”:

We may compare a man in the process of computing a real number to a machine which is only capable of a finite number of conditions q1, q2, …, qR which will be called “m-configurations”. The machine is supplied with a “tape”, (the analogue of paper) running through it, and divided into sections (called “squares”) each capable of bearing a “symbol”. At any moment there is just one square, say the r-th, bearing the symbol S(r) which is “in the machine”. We may call this square the “scanned square”. The symbol on the scanned square may be called the “scanned symbol”. The “scanned symbol” is the only one of which the machine is, so to speak, “directly aware”. However, by altering its m-configuration the machine can effectively remember some of the symbols which it has “seen” (scanned) previously. The possible behaviour of the machine at any moment is determined by the m-configuration qn and the scanned symbol S(r). This pair qnS(r) will be called the “configuration”: thus the configuration determines the possible behaviour of the machine. In some of the configurations in which the scanned square is blank (i.e. bears no symbol) the machine writes down a new symbol on the scanned square: in other configurations it erases the scanned symbol. The machine may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configuration may be changed. Some of the symbols written down  will form the sequence of figures which is the decimal of the real number which is being computed. The others are just rough notes to “assist the memory”. It will only be these rough notes which will be liable to erasure.

The Turing machine is not intended as a practical computing technology, but rather as a hypothetical device representing a computing machine. Turing machines help computer scientists understand the limits of mechanical computation.

There are many virtual implementations of the Turing machine, in various languages, and even some in hardware that actually read and write on moving tape. (The theoretical machine requires infinite tape, serving as memory). As implied just above, these aren’t practical devices but serve a pedagocial use. So here is a very elementary example in Python:

# Add unary numbers (e.g. 2+1)
table={'1': {'0': '1>2', '1': '1>1'},'2':{'0':'0<3','1':'1>2'},'3':{'0':'0>3','1':'1>0'}}
tape='01101000'

head=2
state='1'

while state != '0':
    print tape
    symbol=tape[head]
    next=table[state]
    tuple=next[symbol]
    tape=tape[:head]+tuple[0]+tape[head+1:]
    action=tuple[1]
    if (action=='<'):
        head=head-1
    else:
        head=head+1
    state=tuple[2]
print tape

An improvement would be to equip this program with a GUI for setting up the machine (i.e. program/state table, and tape/input) and for illustrating the machine action in a clear way.

Sources & Further Reading

© 2014: Software Training & Private Tuition in Computer Science (South Wales) | KABBO Theme by: D5 Creation | Powered by: WordPress