Turing Machines

What is a Turing Machine?

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.


Machine State

A Turing machine would continue to process binary values endlessly unless it has a defined point of completion. The program that tells the machine when to stop is called the machine state. For example, in a similar way that each symbol translates to an action, a state groups a set of definitions for each binary symbol together. Where a 0 and 1 have defined instructions within the initial state, a secondary state may have alternate instructions. When each symbol is read, the machine performs the write instruction, the move instruction, and then proceeds to the next state (which may or may not have similar instructions for each symbol).


Instruction Table

A program for a Turing machine is simply a set of instructions for reading the binary symbols on the tape. These instructions are defined on what is called an instruction table, or state table. Every instruction on the table tells the machine what to write, what direction to move the tape, and which state it should move into next. Accordingly, an instruction may indicate the machine should halt and complete the program