Alan M. Turing: That does not compute

In 1936, Alan M. Turing wrote a paper about computable numbers in which he described an abstract machine (which cannot be built because it would require a potentially infinite tape), that read and wrote to a tape, could move the tape left or right, and had a finite number of states which controlled its actions.  This device became known as a Turing machine.  He also described a Turing machine that could simulate any Turing machine, and used it to prove that one could not determine if a given computation would ever end.

Later, Turing and others described different models of computation, and showed that the same numbers and functions were computable under all of these models (or non-computable under all of these models).  This has brought about the assumption that all sufficiently inclusive definitions of computability are equivalent.  This is known as the Church-Turing (or Church-Turing-Tarsky) thesis.

A Turing machine consists of

• A finite set of states
• A start state; when the machine is started, it is in this state
• A finite set of characters that the machine can read and write
• A tape which has an infinite number of cells, each of which can contain a character
• A read/write head for the tape and a mechanism to move the tape left or right
• A mapping from state and input character to output character, new state, and movement of tape left or right (the state table)

 A universal Turing machine is a Turing machine that, when given a a tape containing a description of the state table of a target Turing machine and the input to be supplied to the target machine, will provide the same result as the target machine would.

To prove that it is impossible to determine whether a Turing machine will halt, assume that a universal Turing machine can be designed that halts and outputs a T if the target machine will halt when supplied a given input, and halts and outputs an F if the target machine will not halt when supplied a given input.

Then modify this machine so that when it would output a T, it enters a new state that keeps mapping to itself for all inputs.  This machine will halt if and only if the target machine does not halt.

Then run the new machine with its own description as both target machine and input tape.  The new machine will halt if and only if its target (the machine itself) will not halt when supplied its own description as input.  This is a contradiction, therefore no such machine can be designed.  So there is no computation that can determine whether a particular Turing machine will halt given a particular input.

There are many books and articles that discuss Turing machines and other models of computability.  http://www.turing.org.uk/turing/scrapbook/machine.html provides links to several Turing machine simulators, including http://www.turing.org.uk/turing/scrapbook/tmjava.html.