A Turing machine is a hypothetical machine meant to simulate any computer algorithm, no matter the complexity. The machine, as thought of by mathematician Alan Turing in 1936, is a relatively simple framework consisting of an infinitely long tape which acts like the computer's memory. The tape, which initially begins blank, can have either a 1 or a 0 printed upon it. As the variables for printing are limited to 1, 0, and blank, the Turing machine is known as a three-symbol machine.Β

How does a Turing Machine Β work?

A Turing machine has three basic operations when the head of the machine is positioned over the tape. The machine can read the symbol on the square, edit the symbol on the square to a new value, or move the tape left or right to read or edit the adjacent square. Additionally, each value can be assigned an associated action. For example, if the symbol being read is a 1, then the machine will write 0 and move the tape to the right, however if the symbol being read is a 0, it will write a 1. This process is called inversion, as it flips the binary values.

Β

Β