Invented in 1936 by Alan Turing, this computation model can, theoretically, can compute anything given infinite memory and time.
Described best by the author himself in his manuscript
...an unlimited memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol, and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings
Actual implementation is very restricted and does not have infinite tape, but I have tried to make it as close to the original description as possible and provide an online interpreter. There are three main parts to it.
First is the language syntax, every line is one instruction that defines a state transition.
Current State | Read Symbol | Write Symbol | Direction | Next State
This basically says if the head encounters ‘Read Symbol’ then write ‘Write Symbol’ and move in ‘Direction’ and change machine state to ‘Next State’. To skip writing ‘null’ is used and to skip movement ’s' (stay) is used. ‘start’ and ‘end’ are special states, where ‘start’ is mandatory in any set of instruction. ‘end’ is optional but required if one wants to halt the program eventually.
Second part is a compiler written in Python that parses the plain text code and creates an internal executable program which can be pickled to create a distributable binary.
Third part is the Turing Machine implementation, again written in Python, which takes that executable and executes the program. The standalone version runs with a clock speed of one instruction per second for better visualization. Every instruction execution prints the state to the terminal and if the program eventually halts it prints out the final state and value at head.I
# start_state, read_value, write_instruction, move_instruction, next_state
# state: start | end | str
# value: 1 | 0 | null
# move: l | r | s
start 0 1 r one
one 0 null l start
start 1 null s stop
I am in the process of writing some practical code as an example for this interpreter. Stay tuned !
Feel free to send me an email for any suggestion or feedback. Follow me on twitter and github.