Multi Head, Multi Tape Turing Machine

Turing Machine Types & Halting Problem ( Undecidability)

1. UNIT IV– TURING MACHINE
October 11, 2018 1UNIT IV TURING MACHINE

2. A multi head Turing machine is a single tape TM having n heads
reading symbols on the same tape. In one step all the heads sense the
scanned symbols and move or write independently.
The heads are numbered 1 through n and move of TM depends upon
the state and symbols scanned by each head.
In one move the heads may move left , right or remain stationary.
This type of TM is as powerful as one tape Turing machine.
The multi head Turing Machine is as shown in the following
October 11, 2018 2UNIT IV TURING MACHINE

3. October 11, 2018 3UNIT IV TURING MACHINE

4. The multi tape Turing Machine is a type of Turing machine in which
there are more than one input tapes. Each tape is divided into cells
and each cells can hold any symbol of finite tape alphabet. The multi
tape Turing machine is as shown in the following image.
This TM is more powerful than the basic Turing machine. Because
finite control reads more than one input tape and more symbols can
be scanned at a time.
October 11, 2018 UNIT IV TURING MACHINE 4

5. October 11, 2018 UNIT IV TURING MACHINE 5

6. Turing Machine has a great computational
capabilities and hence it can be used as a general
mathematical model for modern computers.
Turing Machine can model even recursive
enumerable languages. Thus the advantage of
Turing machine is that it can model all the
computable functions as well as the languages for
which the algorithm is possible.
October 11, 2018 UNIT IV TURING MACHINE 6

7. Halting Problem
An important question of computing science is “Are there
problems that cannot be solved?”
There are, and probably the most famous of these is the
halting problem described by Turing.
He was thinking in terms of Turing machines (there were
no computers), but it is easy to extend the idea.
 Can we write a program that will look at any computer
program and its input and decide if the program will halt
(not run infinitely)?
A practical solution might be to run the program and if it
halts you have your answer. If after a given amount of
time it doesn’t halt, guess that it won’t halt. However, you
wouldn’t know if the program would eventually halt.

8. Halting Problem
The state halting problem we will consider the given
configuration of a turing machine. The output of TM
can be
HALT The machine starting at this configuration
will halts after a finite number of states.
No HALT The machine starting at this
configuration never reaches a halt state, no matter
how long it turns.
Now question is arises on these two observation.
Given any functional matrix , input data tape and
initial configuration, then it is possible to determine
whether the process will ever halts? This is called HP.
Yes Solvable and No Unsolvable. Now we prove
why it is unsolvable.

9. Halting Problem
October 11, 2018 UNIT IV TURING MACHINE 9
Consider TM M1 which decides whether or not any
computation by a TM T will ever halt when a
description dT of T and tape t of T is given.
Then for every input (t,dT) to M1 if T halt for input t,
M1 also halts which is called accept halt. Similarly if T
does not halt for input t then the M1 will halt which is
called reject halt.

10. Halting Problem
October 11, 2018 UNIT IV TURING MACHINE 10
Now consider another TM M2 which takes an input
dT.
It first copies dT and duplicates dT on its tape and
then this duplicated tape information is given as
input to machine M1. but machine M1 is a modified
machine with the modification that whenever M1 is
supposed to reach an accept halt, M2 never loops
forever.
It loops if T halts for input t=dT and halts if T does
not halt for T=dT.