Turing Machines

Combination of Turing Machines



Subjects to be Learned

Contents

Combination of Turing Machines

We have seen the definition of Turing machine and a few simple examples. One can construct many more Turing machines that perform various functions. In fact Turing machines that simulate computers and Turing machines that perform computations done by any algorithm can be constructed. Furthermore according to the Church's thesis, any "computation" done by human beings or machines can be done by some Turing machine. Here we are going to study how complex Turing machines can be constructed using simple Turing machines and how computers can be simulated by Turing machines.

Let us start with some basic Turing machines.
We have already seen TR . It moves the head to the first symbol (which may be ) to the right of the current position. Similarly by TL we denote a Turing machine that moves the head to the first symbol (which may be ) to the left of the current position. Then by T we denote a Turing machine that writes symbol at the current position and does not move the head (stays). Also by TR and TL we denote Turing machines that move the head to right and left one position, respectively.

To combine Turing machines we use the following conventions:

Let T1 and T2 represent arbitrary Turing machines.
T1T2 and T1 -> T2 denote the Turing machine that behaves initially like T1 and when T1 halts T2 takes over inheriting the head position and the tape contents of T1 . The halt state of T1 becomes the initial state of T2 .

T1 -> T2 denote the Turing machine that first executes T1. Then if T1 halts and if the symbol currently under the head is , then T2 is started as in the case of T1T2 . Otherwise it crashes.

Using these basic machines and the convention, let us construct a little more complex Turing machines. Below is assumed to be at the left end of the tape initially.

Example 4: The following machine shifts the tape contents to the left one position, takes the head to the right end of the string and halts.





               



For example with the initial tape contents of ab , it goes through the following sequence of tape contents and ends with ab:

                ab
                -> ab

                -> aab

                -> ab
                -> ab

                -> abb

                -> ab
                -> ab
                -> ab

Example 5: The left-shift machine of Example 4 can be used to construct an adder for natural numbers. First, natural numbers are represented on a Turing machine using symbol I. For example the number 3 is represented by three consecutive I's on the tape and 5 by five I's. In general to represent a natural number k, k consecutive I's are put on the tape. To add two numbers m and n, m I's and n I's with a blank between them are placed on the tape. So the initial configuration for adding 2 and 3 is ( q0 , IIIII ) . After the addition the configuration becomes ( h , IIIII ) .

An adder can be constructed for example as   TR -> TSL TL . After adding two numbers placed on the tape it moves the head to the left end and halts.

Example 6:
The following Turing machine copies the tape contents at the left end to their right separated by a blank , that is ( q0 , x ) * ( h ,xx ) .




               



Today's computers are very complex machines and their instruction sets contain complicated operations. However, all of those instructions can be realized using combinations of a small number of basic instructions. In fact many of the earlier computers had a much smaller instruction set but still could do everything today's computers can do albeit much more slowly. A bare minimum instruction set would contain addition, branching, store and load operations. All the other operations can be realized by using those basic operations. On the other hand as we have seen above, there is a Turing machine that performs addition; the branch operation is already in Turing machines because next configurations are determined based on the current state and tape symbol being looked at; and store and load operations can be taken care of by a Turing machine that copies tape contents. Furthermore if the subtraction operation is necessary, it is not difficult to construct a Turing machine that performs subtraction using the same representation of numbers as for the addition. Thus by combining appropriate Turing machines a computer with a minimal instruction set can be constructed. Since any complex computer instructions can be realized using those basic instructions, one can say that computers can be simulated by Turing machines.



Test Your Understanding of Combination of Turing Machines

Indicate which of the following statements are correct and which are not.
Click True or Fals , then Submit.

The following notations are used in the questions:

T_a    : Ta
T_R   : TR
->^b   : ->b








Next -- Types of Turing Machines

Back to Study Schedule

Back to Table of Contents