Turing Machines
Combination of Turing Machines
Subjects to be Learned
- Combination of Turing Machines
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