Introduction to Turing Machines

Let's take a short tour of Turing machines.

A Turing machine can be thought of as a primitive, abstract computer. Alan Turing, who was a British mathematician and cryptographer, invented the Turing machine as a tool for studying the computability of mathematical functions. Turing's hypothesis (also known has Church's thesis) is a widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer program can solve. There are problems that can not be solved by a Turing machine (e.g., the halting problem); thus, these problems can not be solved by a modern computer program.

A Turing machine has an infinite tape that consists of adjacent cells (or squares). On each cell is written a symbol. The symbols that are allowed on the tape are finite in number and include the blank symbol. Each Turing machine has it's own alphabet (i.e., finite set of symbols), which determines the symbols that are allowed on the tape.

The Turing machine has a tape head that is positioned over a cell on the tape. This tape head is able to read a symbol from a cell and write a new symbol onto a cell. The tape head can also move to an adjacent cell (either to the left or to the right).

A Turing machine has a finite number of states, and, at any point in time, a Turing machine is in one of these states. A Turing machine begins its operation in the start state. A Turing machine halts when it moves into one of the halt states.

When a Turing machine begins running, it is in its start state and its tape head is positioned over one of the cells on the tape; the symbol on this cell is the current symbol.

1. The Turing machine reads the tape symbol that is under the Turing machine's tape head. This symbol is referred to as the current symbol.
2. The Turing machine uses its transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.
3. The Turing machine changes its state to the next state, which was returned by the transition function.
4. The Turing machine overwrites the current symbol on the tape with the next symbol, which was returned by the transition function.
5. The Turing machine moves its tape head one symbol to the left or to the right, or does not move the tape head, depending on the value of the 'movement' that is returned by the transition function.
6. If the Turing machine's state is a halt state, then the Turing machine halts. Otherwise, repeat sub-step #1.

It's fairly easy to create a Turing machine that converts a string on the tape from lower case to upper case. However, for many simple tasks that can be performed with a few lines of Java or C, it's difficult and tedious to create Turing machines that performs these tasks. For example, many college students find it challenging to create a Turing machine that multiplies two numbers.

For more information about Turing machines and Alan Turing, please visit the following web sites:

• The Alan Turing Home Page
• Turing Machines and Computability
• The American Mathematical Society has a page describing Turing machines
• Online Turing Machine Simulator
• Turing machine article on Wikipedia

Powered by Turing Machines :-)