- Definition of Turing Machine
- Configuration
- Operation of Turing Machine

We have studied two types of languages from the Chomsky hierarchy: regular languages and context-free languages. These languages can describe many practically important systems and so they are heavily used in practice. They are, however, of limited capability and there are many languages that they can not process. In this chapter we are going to study the most general of the languages in Chomsky hierarchy, the phrase structure languages (also called Type 0 languages), and the machines that can process them: Turing machines. Turing machines were conceived of by the English mathematician Alan Turing as a model of human "computation". Later Alonzo Church conjectured that any computation done by humans or computers can be carried out by some Turing machine. This conjecture is known as Church's thesis and today it is generally accepted as true. Computers we use today are as powerful as Turing machines except that computers have finite memory while Turing machines have infinite memory.

We are going to study Turing machines here and through that limitations of computers and computation as we know today.

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

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 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.

State (q) | Input (X) | Move ( (q, X) ) |

q_{0} | ( q_{1} , , R ) | |

q_{1} | a | ( q_{2} , a , R ) |

q_{2} | b | ( q_{3} , b , R ) |

q_{3} | a | ( q_{3} , a , R ) |

q_{3} | ( 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.

To describe the operation of Turing machine we use configuration. A

A string x is said to be

( q

For example the Turing machine of Example 1 above goes through the following sequence of configurations to accept the string aba:

( q

( q

( q

( q

( h ,aba )

The first of the following figures shows a Turing machine that accepts but does not decide the language { a }, the second is a Turing machine that accepts { a } but goes into a loop if a string is not in the language (hence it accepts but doe not decide { a }) and the third decides { a }, where = { a }.

When a string is not accepted by a Turing machine, that is when a Turing machine does not halt on a string, one of the following three things happens:

(1) The Turing machine goes into an infinite loop,

(2) no transition is specified for the current configuration and

(3) the head is at the left end and it is instructed to move left.

In cases (2) and (3), the operation of the Turing machine is aborted. For example the following Turing machine accepts the language a

Let S

( q

and for every x

As far as the material discussed in this class note, there is no difference between these two definitions of "accept".

A language is a phrase structure (type 0) langauage if and only if it is Turing-acceptable in either sense and it has no effects on decidablility.

Click True or Fals , then Submit.

There are two sets of questions.