In 1936, Alan Turing the British mathematician published a paper entitled
On Computable Numbers and their Application to the Entscheidungsproblem. This was where Turing first conceived of a machine built to encapsulate a mathematical method. This machine would be able to perform elementary operations and yet be able to solve any computable problem.
The original theory was that each mathematical method would be encapsulated by a different machine, one machine for factoring and another for calculating square roots for example. Seemingly complicated functions can be reduced to a series of simple ones. An example of this is the calculation of ex for a given value of x. This can be calculated using the Taylor series.
ex = 1 + x + x2/2! + x3/3! + x4/4! + ��
It can be seen that this has been reduced to a series of simple operations, addition and multiplication. The series potentially continues indefinitely; so accuracy to a significant figure must be chosen and the series stopped at the relevant point.
A Turing Machine itself would consist of two parts; a tape of potentially unlimited length, and a machine that can travel along the tape and manipulate the contents. The tape is divided into squares, or cells each of which is either blank or inscribed with a 0 or 1. The machine can travel to the right and left along the tape, read or write to any section of tape it passes over. The action of reading or writing will alter the internal state of the machine, it will cycle through states as it carries out the steps of it's operation.
Returning to ex the machine's internal states would encapsulate the Taylor series. As each bit of the calculation is performed, it changes state until it returns to the original state. The tape holds the input data, the value of x, acts as a memory and output device. The resultant value of ex will be written to the tape by the machine to the significant figure that was inputted.
The concept of a Turing Machine is limited and so Turing conceived of another machine that would be an improvement and he believed would be equivalent to a human brain. This new machine would be equivalent to any possible Turing Machine and so would be in effect a Universal Turing Machine. In essence a Turing Machine is like a computer program whereas a Universal Turing Machine is a like a computer that is capable of carrying out any possible program.
For further information and to see a Perl script of a Truing Machine in action see http://www.nmia.com/~soki/turing/
or http://www.nmt.edu/~prcm/turing/
| 
