Turing Machine

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.

The operation of a Turing machine proceeds as follows:

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.



Conceptually a Turing machine, like finite automata, consists of a finite control and a tape. At any time it is in one of the finite number of states. The tape has the left end but it extends infinitely to the right. It is also divided into squares and a symbol can be written in each square. However, unlike finite automata, its head is a read-write head and it can move left, right or stay at the same square after a read or write.
        



Given a string of symbols on the tape, a Turing machine starts at the initial state. At any state it reads the symbol under the head, either erases it or replaces it with a symbol (possibly the same symbol). It then moves the head to left or right or does not move it and goes to the next state which may be the same as the current state. One of its states is the halt state and when the Turing machine goes into the halt state, it stops its operation.

Formally a Turing machine is a 5-tuple T = < Q, , , q₀, > , where
Q is a finite set of states, which is assumed not to contain the symbol h. The symbol h is used to denote the halt state.
is a finite set of symbols and it is the input alphabet.
is a finite set of symbols containing as its subset and it is the set of tape symbols.
q₀ is the initial state.
is the transition function but its value may not be defined for certain points.
It is a mapping from Q ( {} ) to ( Q { h } ) ( {} ) { R , L , S } . 
Here denotes the blank and R, L and S denote move the head right, left and do not move it, respectively. A transition diagram can also be drawn for a Turing machine. The states are represented by vertices and for a transition ( q, X ) = ( r, Y, D ) , where D represents R, L or S , an arc from q to r is drawn with label ( X/Y , D ) indicating that the state is changed from q to r, the symbol X currently being read is changed to Y and the tape head is moved as directed by D.

Example 1 : The following Turing machine < Q₁ , , , q₀ , > accepts the language aba^* , where Q₁ = { q₀, q₁, q₂, q₃ } , = { a , b } , = { a , b } and is as given by the table below.

State (q)	Input (X)	Move ( (q, X) )
q0		( q1 , , R )
q1	a	( q2 , a , R )
q2	b	( q3 , b , R )
q3	a	( q3 , a , R )
q3		( h , , S )

A transition diagram of this Turing machine is given below. It is assumed that the tape has at the left end and the head is initially at the left end of the tape.