UNIT-5

Types of Turing machine: Turing machines and halting

Undecidability: Undecidability, A Language that is Not
Recursively Enumerable, An Undecidable Problem That is RE,
Undecidable Problems about Turing Machines, Recursive
languages, Properties
of recursive languages, Post's Correspondence Problem, Modified
Post Correspondence problem, Other Undecidable Problems,
Counter machines.
TYPES/ VARIANTS OF TURING MACHINE

1. Two-way infinite Tape Turing Machine

2. Multi-tape Turing Machine

3. Non-deterministic Turing Machine

4. Multi-dimensional Tape Turing Machine

5. Multi-head Turing Machine

6. Offline Turing Machine

7. Multiple track Turing Machine

1. TWO-WAY INFINITE TAPE TURING MACHINE

 A two-way infinite tape Turing machine allows the tape to extend

infinitely in both directions, unlike the standard machine where
the tape extends infinitely in only one direction.
 This removes the boundary on the left side of the tape.
EXAMPLE
L = { w ∈ {a, b}* | w has the same number of a’s to
the left and right of a central marker # }
KEY DIFFERENCE FROM STANDARD TURING MACHINE

Standard Turing Two-Way Infinite

Feature
Machine Tape

Tape direction Infinite to the right Infinite both ways

Cannot move past left

Left-end restriction No boundary at all
end

Power Equal (same languages) Equal

Simpler algorithms? Sometimes Yes (can simplify logic)

2. MULTI-TAPE TURING MACHINE

 It has multiple tapes and

controlled by a single head.
 The Multi-tape Turing
machine is different from k-
track Turing machine but
expressive power is same.
 Multi-tape Turing machine
can be simulated by single-
tape Turing machine
EX: Palindrome String: The heads start at both ends of the string and move towards each other, checking if
the corresponding symbols are identical.
EXAMPLE
L = { ww | w ∈ {a, b}* } This language contains any

string repeated twice, like abbaabba

BENEFITS OF MULTI-TAPE MACHINES, SINGLE TAPE , TWO WAY INFINITE

Two-Way Infinite
Feature Single-Tape Multi-Tape
Tape
Tapes 1 2 or more 1
Infinite both
Tape Direction Infinite right only Infinite right only
directions
Heads 1 1 per tape 1
Power (Language
Same Same Same
Capability)
Similar to single-
Speed Slower Faster (more efficient)
tape
Easier for complex Easier for
Design Simplicity Basic
logic symmetric designs
Efficient algorithms, Palindromes,
Ideal Use Teaching, theory
copying symmetry checks
3. NON-DETERMINISTIC TURING
MACHINE
 A non-deterministic Turing
machine has a single, one way
infinite tape.
 For a given state and input
symbol has atleast one choice
to move (finite number of
choices for the next move),
each choice several choices of
path that it might follow for a
given input string.
 A non-deterministic Turing
machine is equivalent to
EXAMPLE
L = { w ∈ {a, b}* | w contains a substring "aba" }
4. MULTI-DIMENSIONAL TAPE TURING MACHINE
 It has multi-dimensional tape where head can move any
direction that is left, right, up or down.
 Multi dimensional tape Turing machine can be simulated by
one-dimensional Turing machine
EXAMPLE
COMPARISON TABLE
2D/3D Turing
Feature 1D Turing Machine
Machine

Tape Structure Linear (one row) Grid or cube (2D/3D)

Up, Down, Left, Right

Head Movement Left/Right
(and more)

Grid problems, 2D
Suitable for Strings, linear problems
patterns, simulations

Language Power Equivalent Equivalent

Design Complexity Easier Higher

Simulation of 2D by 1D Possible but slower Native and efficient

5. MULTI-HEAD TURING MACHINE
 A multi-head Turing machine contain two or more heads to
read the symbols on the same tape.
 In one step all the heads sense the scanned symbols and
move or write independently.
 Multi-head Turing machine can be simulated by single head
Turing machine.
EXAMPLE
L = { ww | w ∈ {a, b}* } This is the set of strings

where the first half is exactly the same as the

second half — e.g., abbaabba

6. OFFLINE TURING MACHINE
 An "offline" Turing Machine, also
known as a multi-tape Turing
Machine, utilizes multiple tapes to
process input. One tape acts as
the input (read-only) and another
as a working tape for
manipulation.
 This contrasts with a standard
single-tape Turing Machine where
input and work are on the same
tape.
EXAMPLE
L = { w ∈ {a, b}* | w has equal number of a's and

b's }
7. MULTIPLE TRACK TURING MACHINE

 A k-tack Turing machine(for some k>0) has k-tracks and

one R/W head that reads and writes all of them one by one.

A k-track Turing Machine can be simulated by a single track
Turing machine
EXAMPLE
L = { ww^R | w ∈ {a, b}* } This is the set of strings

that are followed by their reverse, like abbaabba

COMPARISON TABLE
Purpose / Why It's
Type What It Is Special Feature
Useful
Can read/write and Base model for
Basic TM Single tape, one head
move left/right computation
Tape goes infinitely in Easier handling of input
Two-way Infinite TM No left-end limit
both directions growing both ways
Faster, handles
Multiple tapes with one Can read/write on all
Multi-Tape TM complex tasks in fewer
head each tapes in one step
steps
One tape, divided into Each cell stores Stores extra info like
Multi-Track TM
several "layers" or rows multiple symbols marks, counters
Two tapes: input tape
Input cannot be Keeps input safe, useful
Offline TM (read-only), and work
changed in parsing or compilers
tape (read/write)
One tape, but multiple Reads/writes in Faster comparisons,
Multi-Head TM
heads different positions scanning multiple areas
Solves problems on
Multi-Dimensional Tape is a 2D grid or 3D Moves in 4 or more
grids/images/matrices
TM block directions
easily
Theoretical model to
Non-Deterministic Can try many paths at
Multiple possible moves explore hard problems
TM once from a state
DECIDABLE PROBLEMS
 A problem is said to be Decidable if we can always
construct a corresponding algorithm that can answer
the problem correctly.
 Decidability in terms of a Turing machine, a
problem is said to be a Decidable problem if there
exists a corresponding Turing machine which halts
on every input with an answer- yes or no.
 It is also important to know that these problems are
termed as Turing Decidable since a Turing machine
always halts on every input, accepting or rejecting it.
WE WILL NOW CONSIDER FEW IMPORTANT
DECIDABLE PROBLEMS
 Are two regular languages L and M equivalent?
We can easily check this by using Set Difference
operation. L-M =Null and M-L =Null. Hence (L-M) U
(M-L) = Null, then L,M are equivalent.
 Membership of a CFL?
We can always find whether a string exists in a given
CFL by using an algorithm based on dynamic
programming.
 Emptiness of a CFL By checking the production
rules of the CFL we can easily state whether the
language generates any strings or not.
SEMI- DECIDABLE PROBLEMS

 Semi-Decidable problems are those for which a Turing

machine halts on the input accepted by it but it

can either halt or loop forever on the input which is

rejected by the Turing Machine. Such problems are

termed as Turing Recognizable problems.

UNDECIDABLE PROBLEMS
 The problems for which we can’t construct an
algorithm that can answer the problem correctly in
finite time are termed as Undecidable Problems.
These problems may be partially decidable but they
will never be decidable.
 That is, there will always be a condition that will lead
the Turing Machine into an infinite loop without
providing an answer at all.
 Simply, A problem is undecidable if there is no
Turing machine which will always halt in finite
amount of time to give answer as ‘yes’ or ‘no’. An
undecidable problem has no algorithm to determine
the answer for a given input.
UNDECIDABLE PROBLEMS ABOUT TURING MACHINE
 Ambiguity of context-free languages: Given a context-free
language, there is no Turing machine which will always halt in
finite amount of time and give answer whether language is
ambiguous or not.
 Equivalence of two context-free languages: Given two
context-free languages, there is no Turing machine which will
always halt in finite amount of time and give answer whether two
context free languages are equal or not.
 Everything or completeness of CFG: Given a CFG and input
alphabet, whether CFG will generate all possible strings of input
alphabet (∑*)is undecidable.
 Regularity of CFL, CSL, REC and REC: Given a CFL, CSL, REC or
UNDECIDABLE PROBLEMS ABOUT TURING
Problem Description
MACHINES Given a Turing machine MM and input ww,
Halting Problem
determine if MM halts on ww.
Acceptance Problem (ATM) Given MM and ww, does MM accept ww?

Post Correspondence Given string pairs, can top and bottom strings
Problem (PCP) match using some sequence of indices?

Modified PCP (MPCP) Same as PCP, but must start with the first pair.

Ambiguity Problem for CFG Is a given context-free grammar ambiguous?

Are two CFGs equivalent (generate the same

Equivalence of CFGs
language)?

Given two TMs M1M_1 and M2M_2, is

Emptiness of TM Intersection
L(M1)∩L(M2)=∅L(M_1) \cap L(M_2) = \emptyset?
RECURSIVE LANGUAGES: 1. REC, 2. RE
RECURSIVE LANGUAGE (REC):
 A recursive language (subset of RE) can be decided
by Turing machine which means it will enter into
final state for the strings of language and
rejecting state for the strings which are not
part of the language.
 Ex: L= {anbncn|n>=1} is recursive because we can
construct a turing machine which will move to final
state if the string is of the form anbncn else move to
non-final state. So the TM will always halt in this case.
 REC languages are also called as Turing decidable
Recursive Enumerable (RE) or Type -0 Language:
RE languages or type-0 languages are generated by
type-0 grammars.
 An RE language can be accepted or recognized by
Turing machine which means it will enter into final
state for the strings of language and may or may not
enter into rejecting state for the strings which are
not part of the language.
 It means TM can loop forever for the strings which
are not a part of the language. RE languages are also
called as Turing recognizable languages.
THE RELATIONSHIP BETWEEN RE AND REC
LANGUAGES CAN BE
CLOSURE PROPERTIES OF RECURSIVE LANGUAGES
 Union: If L1 and If L2 are two recursive languages,
their union L1∪L2 will also be recursive because if TM
halts for L1 and halts for L2, it will also halt for
L1∪L2.
 Concatenation: If L1 and If L2 are two recursive
languages, their concatenation L1.L2 will also be
recursive.
For Example:
 Kleene Closure: If L1is recursive, its kleene closure
L1* will also be recursive.
For Example:

 Intersection and complement: If L1 and If L2 are

two recursive languages, their intersection L1 ∩ L2 will
also be recursive.
For Example:
UNIVERSAL TURING MACHINE
 The Turing Machine (TM) is the machine level
equivalent to a digital computer.
 It was suggested by the mathematician Turing in the
year 1930 and has become the most widely used model
of computation in computability and complexity theory.
 A Turing machine is said to be universal Turing machine
if it can accept:
 The input data, and
 An algorithm (description) for computing.
 The input is given in binary format form on to the
machine's tape and the output consists of the contents
of the tape when the machine halts
A UNIVERSAL TURING MACHINE IS A TURING
MACHINE WHICH WHEN SUPPLIED WITH AN
APPROPRIATE DESCRIPTION OF A TURING
MACHINE M AND AN INPUT STRING W, CAN
SIMULATE THE COMPUTATION OF W.
CONSTRUCTION OF UTM

Without loss of generality, we assume the following for M:

Q = {q1, q2, ….qn} where q1=initial state and q2=Final
State
τ = {σ1, σ2,,…σn} where σ represent blanks
Select an encoding on which q1 is representable by 1, q2 by
11, and so on. Similarly, σ1 is encoded as 1, σ2 as 11, etc.
Finally, let us represent R/W head directions by 1 for L (Left)
and 11 for R(Right).
The symbol 0 will be used as a separator between 1s.With
this scheme, any transition of M can be given as :
 The problem with the Turing machine is that a
different machine must be constructed for every new
computation to be performed for every input output
relation.
 This is the reason the Universal Turing machine was
introduced which along with input on the tape takes
the description of a machine M.
This machine would have three bits of
information for the machine it is simulating
 A basic description of the machine.
 The contents of machine tape.
 The internal state of the machine.

Representation of a Universal Turing Machine

 The Universal machine would simulate the machine
by looking at the input on the tape and the state of
the machine.
 It would control the machine by changing its state
based on the input. This leads to the idea of a
“computer running another computer”.
 It would control the machine by changing its state
based on the input. This leads to the idea of a
“computer running another computer”
IMPLEMENTATION OF UTM
A UTM Mu then has an input
alphabet = {0, 1} and the
structure of a multi-tape TM.
Mu looks first at the contents of
Tape 2 and Tape 3 to determine
the instantaneous description
(ID) of M.
It then consults Tape1 to see
what M would do with this ID.
Finally, Tape 2 and Tape 3 will
be modified to reflect the result
of the move.
DIFFERENCE BETWEEN UNIVERSAL TURING
MACHINE AND TURING MACHINE
Turing Machine Universal Turing Machine

Turing Machine is a mathematical model A Universal Turing Machine is similar to a

of computation which manipulates regular Turing Machine but it has
symbols on tape according to the rules solutions to all problems that are
defined. computable.

The Universal Turing Machine takes a

Turing machine’s temporary storage is
Turing Machine description and an input
tape. The infinite cells of the Turing
string as input, then runs the Turing
machine can contain input symbols and
Machine on the input and returns the
blanks.
result.

It does not minimize the space complexity It minimizes space complexity

A Turing machine is a formal model of a

The Universal Turing Machine solves
computer that runs a predetermined
problems that can be computed.
program
A LANGUAGE THAT IS NOT RECURSIVELY ENUMERABLE
AN UNDECIDABLE PROBLEM THAT IS RE- TURING MACHINE HALTING PROBLEM

 The halting problem is a problem in computer science that asks

whether a given algorithmic program will eventually halt (terminate)
when given a particular input.
 It has been proven that there is no algorithm that can solve the
halting problem for all possible inputs, and it is one example of a
problem that cannot be solved by any Turing Machine.
 Input − A Turing machine and an input string w.
 Problem − Does the Turing machine finish computing of the
string w in a finite number of steps? The answer must be either yes or
no.
 Proof − At first, we will assume that such a Turing machine exists to
solve this problem and then we will show it is contradicting itself. We
will call this Turing machine as a Halting machine that produces a yes
or no in a finite amount of time. If the halting machine finishes in a
finite amount of time, the output comes as yes, otherwise as no.
HALTING MACHINE
INVERTED HALTING MACHINE (HM)
 If H returns YES, then loop forever.
 If H returns NO, then halt.

a machine (HM)2 which

input itself is constructed
as follows −
• If (HM)2 halts on input,
loop forever.
• Else, halt.

we have got a contradiction.

Hence, the halting problem
is undecidable.
POST CORRESPONDENCE PROBLEM
 The Post Correspondence Problem (PCP), introduced by
Emil Post in 1946, is an undecidable decision problem.
The PCP problem over an alphabet ∑ is stated as
follows − Given the following two lists, M and N of non-
empty strings over ∑ −
M = (x1, x2, x3,………, xn)
N = (y1, y2, y3,………, yn)
We can say that there is a Post Correspondence Solution,
if for some i1,i2,………… ik, where 1 ≤ ij ≤ n, the
condition xi1 …….xik = yi1 …….yik satisfies.
Find whether the lists M = (abb, aa, aaa) and N = (bba,
aaa, aa) have a Post Correspondence Solution?

Solution:
X1 X2 x3
M abb aa aaa
N bba aaa aa

x2x1x3 = ‘aaabbaaa’ and y2y1y3 = ‘aaabbaaa’

We can see that
x2x1x3 = y2y1y3
Hence, the solution is i = 2, j = 1, and k = 3.
Find whether the lists M = (ab, bab, bbaaa) and N = (a,
ba, bab) have a Post Correspondence Solution?
Solution:
X1 X2 x3
M ab bab bbaaa
N a ba bab

In this case, there is no solution because −

| x2x1x3 | ≠ | y2y1y3 | (Lengths are not same) Hence,
it can be said that this Post Correspondence Problem
is undecidable.
MODIFIED POST CORRESPONDENCE PROBLEM

 In the Modified Post Correspondence Problem,

you are given two lists of strings:
EXAMPLE

The lists are: Top list A: [a, ab, b],Bottom list B: [a, b,
abb] Bottom
Index Top (A)
(B)
1 a a
2 ab b
3 b abb
COUNTER MACHINES
 Counter machine has the same structure as the multi-stack
machine but in place of each stack is a counter. Counters
hold any non-negative integer, but we can only distinguish
between zero and nonzero counters.
 A counter machine is a simple kind of computer model used
to understand how computation works. It’s similar to a Turing
machine but uses counters instead of tapes. These counters
can hold any non-negative number (like 0, 1, 2, 3...), and we
can perform basic operations on them, like:
 Increment (add 1 to the counter)
 Decrement (subtract 1 from the counter, but only if it’s not zero)
 Check if zero (see if the counter is zero, which can decide what
to do next).
EXAMPLE
Suppose we have a counter machine
with two counters, and we want to
make it add two numbers. Let's say
Counter A has 3 and Counter B has
2. We want the result (5) to end up
in Counter A, and Counter B to
become 0.
 Here's what the machine might do:
 Check if Counter B is zero. If it is, stop.
If not, continue.
 Decrement Counter B (subtract 1 from
it).
 Increment Counter A (add 1 to it).
 Go back to Step 1.
 This repeats until Counter B becomes
0. Then Counter A holds the sum.