Turing Machine

Alan Turing - the "father" of computer science

…The abstract Universal Turing Machine naturally exploits what was later seen as the 'stored program' concept essential to the modern computer: it embodies the crucial twentieth-century insight that symbols representing instructions are no different in kind from symbols representing numbers. But computers, in this modern sense, did not exist in 1936. Turing created these concepts out of his mathematical imagination. Only nine years later would electronic technology be tried and tested sufficiently to make it practical to transfer the logic of his ideas into actual engineering. In the meanwhile the idea lived only in his mind.

http://www.turing.org.uk/bio/part3.html

Turing Machine Simulators (Java Applets)

A simulator helps you to understand the basic ideas of turing machines.
http://www.turing.org.uk/turing/scrapbook/machine.html
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
Turing Virtual Machine: http://www.nmia.com/~soki/turing/

Description of 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)

More at:
http://www.ams.org/featurecolumn/archive/turing.html

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License