Turing machine

The Turing Machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or 'mechanical procedure'. The concept is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. The thesis that states that Turing machines indeed capture the informal notion of effective or mechanical method in logic and mathematics is known as the Church-Turing thesis.

Example

The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1s on the tape, with the head initially on the leftmost 1, and doubles the 1s with a 0 in between, i.e., "111" becomes "1110111".

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The set of states is {s1, s2, s3, s4, s5} and the start state is s1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The action table is as follows.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The behaviour of this machine can be described as a loop:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1s and the first 0 encountered. S3 then skips over the next sequence of 1s (initially there are none) and replaces the first 0 it finds with a 1. S4 moves back to the left, skipping over 1s until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1s until it finds the 0 that was originally written by s1.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This continues until s1 finds a 0 (this is the 0 ri in the middle between the two strings of 1s) at which time the machine halts.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~