Paavai Institutions Department of AIML

UNIT V

UNDECIDABILITY

UNIT V 1
 Paavai Institutions Department of AIML

Table of Contents

5.1 Unsolvable Problems and Computable Functions

5.2 Recursive and recursively enumerable languages
5.3 PCP-
5.3.1 MPCP Properties
5.4 Universal Turing machine
5.5 Tractable and Intractable problems
5.6 P and NP completeness
5.6.1 Kruskal‘s algorithm –
5.6.2 Travelling Salesman Problem
5.6.3 3-CNF SAT problems.
5.7 Question Bank

UNIT V 2
 Paavai Institutions Department of AIML

Technical Terms

S.No Technical Terms Literal Meaning Technical Meaning

1 Non Recursive A language is a subset of ∑*. A
Enumerable
language is any subset of ∑*.
Languages
Recursively enumerable languages are
known as type-0 languages in the
Chomsky hierarchy of formal
languages. All regular, context-free,
context-sensitive and recursive
languages are recursively enumerable
2 Recursive A recursively enumerable language is
Enumerable
a recursively enumerable subset in the
Languages
set of all possible words over the
alphabet of the language. A
recursively enumerable language is a
formal language for which there exists
a Turing machine (or other
computable function) which will
enumerate all valid strings of the
language
3 Tractable Problems Tractable Problem: a problem that is
solvable by a polynomial-time
algorithm. The upper bound is
polynomial. Intractable Problem: a
problem that cannot be solved by a
polynomial-time algorithm. The lower
bound is exponential.
4 Intractable From a computational complexity
Problems
stance, intractable problems are
problems for which there exist no
efficient algorithms to solve them.
Most intractable problems have an
algorithm where as the same algorithm
that provides a solution, and that
algorithm is the brute-force search.

UNIT V 3
 Paavai Institutions Department of AIML

S.No Technical Terms Literal Meaning Technical Meaning

5 Undecidable A problem is undecidable if there is no
Problems
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
6 Post’s Post correspondence problem. ... The
Correspondence
Post correspondence problem is an
Problem
undecidable decision problem that was
introduced by Emil Post in 1946.
7 NP Class Problem NP-Problem. A problem is assigned to
the NP (nondeterministic polynomial
time) class if it is solvable in
polynomial time by a nondeterministic
Turing machine. A problem is said to
be NP-hard if an algorithm for solving
it can be translated into one for
solving any other NP-problem.

UNIT V 4
 Paavai Institutions Department of AIML

5.1 Unsolvable Problems and Computable Functions

The problems for which we can’t construct an algorithm that can answer the
problem correctly in the infinite time are termed as Undecidable Problems in the theory of
computation (TOC).

A problem is undecidable if there is no Turing machine that will always halt an infinite
amount of time to answer as ‘yes’ or ‘no’.

Examples

The examples of undecidable problems are explained below. Here, CFG refers to Context
Free Grammar.

 Whether two CFG L and M equal − Since, we cannot determine all the strings of
any CFG, we can predict that two CFG are equal or not.
 Given a context-free language, there is no Turing machine (TM) that will always
halt an infinite amount of time and give an answer to whether language is
ambiguous or not.
 Given two context-free languages, there is no Turing machine that will always halt
an infinite amount of time and give an answer whether two context-free languages
are equal or not.
 Whether CFG will generate all possible strings of the input alphabet (∑*) is
undecidable.

Halting Problem

The Halting problem is the most famous of the undecidable problems.

5.2 Recursive and recursively enumerable languages

The recursive languages are also closed under set difference and complementation.

Recursive: They allow a function to call itself. Or, a recursive language is a recursive
subset in the set of all possible words over alphabet Σ of that language.

UNIT V 5
 Paavai Institutions Department of AIML

• Non-recursive should not be taken as simpler version of computation, i.e., e.g., obtaining

factorial value without recursion method. Regular languages ⊆ context free languages ⊆

context sensitive languages ⊆ recursive languages ⊆ recursive enumerable languages.

• A language is Recursive ly Enumerable (RE) if some Turing machine accepts it. –

A TM M ED with alphabet Σ accepts L if L = {w ∈ Σ ∗ |M halts with input w }.

• Let L be a RE language and M the Turing Machine that accepts it. ∴, for w ∈ L, M halts
in final state. For w ∈/ L, M halts in non-final state or loops for ever.

• A language is Recursive (R) if some Turing machine M recognizes it and halts on every

input string, w ∈ Σ ∗ . Recognizable = Decidable. Or A language is recursive if there is a

membership algorithm for it.

• Let L be a recursive language and M the Turing Machine that accepts (i.e. recognizes) it.
For string w, if w ∈ L, then M halts in final state. If w ∈/ L, then M halts in non-final
state. (halts always!).
Decidable and Undecidable Languages:

For an undecidable language, there is no Turing Machine which accepts the

language and makes a decision for every input string w (TM can make decision for
some input string though). A decision problem P is called “undecidable” if the
language L of all yes instances to P is not decidable.

UNIT V 6
 Paavai Institutions Department of AIML

TRACTABLE AND INTERACTABLE PROBLEMS:

Tractable Problem: A problem that is solvable by a polynomial-time algorithm. The

upper bound is polynomial.

Intractable Problem: A problem that cannot be solved by a polynomial-time

algorithm. The lower bound is exponential.

Generally we think of problems that are solvable by polynomial time algorithms as

being tractable, and problems that require super polynomial time as being
intractable.

• Sometimes the line between what is an ‘easy’ problem and what is a ‘hard’ problem
is a fine one.

• For example, “Find the shortest path from vertex x to vertex y in a given weighted
graph”. This can be solved efficiently without much difficulty.

• However, if we ask for the longest path (without cycles) from x to y, we have a
problem for which no one knows a solution better than an exhaustive search.

UNDECIDABLE PROBLEMS ABOUT TM:

The undecidable problem about turing machine is given by halting problem. Let us
understand this.

Halting Problem:

The Blank-tape halting Problem

Input: Turing Machine M

Question : Does M halt when started with a blank tape?

So this is the reduction :

This is going to be proven by "proof by contradiction".

UNIT V 7
 Paavai Institutions Department of AIML

Suppose that the halting problem is decidable. Then there is a Turing

machine T that solves the halting problem. That is, given a description of a Turing
machine M (over the alphabet ) and a string w, T writes "yes" if M halts on w and
"no" if M does not halt on w, and then T halts.

We are now going to construct the following new Turing machine

First we construct a Turing machine Tm by modifying T so that if T accepts

a string and halts, then Tm goes into an infinite loop (Tm halts if the original T
rejects a string and halts).

Next using Tm we are going to construct another Turing machine Tc as

follows:

Tc takes as input a description of a Turing machine M, denoted by d(M),

copies it to obtain the string d(M)*d(M), where * is a symbol that separates the two
copies of d(M) and then supplies d(M)*d(M) to the Turing machine Tm .

UNIT V 8
 Paavai Institutions Department of AIML

Let us now see what Tc does when a string describing Tc itself is given to it.

When Tc gets the input d(Tc) , it makes a copy, constructs the string
d(Tc)*d(Tc) and gives it to the modified T. Thus the modified T is given a
description of Turing machine Tc and the string d(Tc).

The way T was modified the modified T is going to go into an infinite loop
if Tc halts on d(Tc) and halts if Tc does not halt on d(Tc).

Thus Tc goes into an infinite loop if Tc halts on d(Tc) and it halts if Tc does
not halt on d(Tc). This is a contradiction. This contradiction has been deduced from
our assumption that there is a Turing machine that solves the halting problem.
Hence that assumption must be wrong. Hence there is no Turing machine that
solves the halting problem.

5.3 POST’S CORRESPONDENCE PROBLEM

In this section, we will discuss the undecidability of string and not of Turing
machines. The undecidability of the string is determined with the help of Post's
Correspondence Problem (PCP). Let us define the PCP.

UNIT V 9
 Paavai Institutions Department of AIML

`"The Post's correspondence problem consists of two lists of string that are
of equal length over the input. The two lists are A = w1, w2, w3, .... , wn and B =
x1, x2, x3, .... xn then there exists a non empty set of integers i1, i2, i3, .... , in such
that,
w1, w2, w3, .... wn = x1, x2, x3, .... xn"
To solve the post correspondence problem we try all the combinations of i1,
i2, i3, .... , in to find the w1 = x1 then we say that PCP has a solution.

Example 1:
Consider the correspondence system as given below
A = (b, bab3, ba) and B = (b3, ba, a). The input set is ∑ = {0, 1}. Find the solution.
Solution:
A solution is 2, 1, 1, 3. That means w2w1w1w3 = x2x1x1x3
The constructed string from both lists is bab3b3a.

Example 2:
Does PCP with two lists x = (b, a, aba, bb) and y = (ba, ba, ab, b) have a solution?

Solution: Now we have to find out such a sequence that strings formed by x and y
are identical. Such a sequence is 1, 2, 1, 3, 3, 4. Hence from x and y list

UNIT V 10
 Paavai Institutions Department of AIML

Example 3:
Obtain the solution for the following system of posts correspondence problem. A = {100,
0, 1}, B = {1, 100, 00}

Solution: Consider the sequence 1, 3, 2. The string obtained from A = babababb. The string
obtained from B = bababbbb. These two strings are not equal. Thus if we try various
combination from both the sets to find the unique sequence, we could not get such a
sequence. Hence there is no solution for this system.

Example 4:
Obtain the solution for the following system of posts correspondence problem, X = {100,
0, 1}, Y = {1, 100, 00}.

Solution: The solution is 1, 3, 1, 1, 3, 2, 2. The string is

X1X3X1X1X3X2X2 = 100 + 1 + 100 + 100 + 1 + 0 + 0 = 1001100100100

Y1Y3Y1Y1Y3Y2Y2 = 1 + 00 + 1 + 1 + 00 + 100 + 100 = 1001100100100

5.3.1 MPCP Properties

Definition:

First pair in the A and B lists must be the first pair in the solution, i.e., the
problem is to determine it there is a sequence of zero or more integers i1,i2,……,in
such that:

w1w2w3………wn = x1x2x3…..xn

Post's Correspondence Problem (PCP) is the problem of deciding whether a

set of dominos has a match or not.

UNIT V 11
 Paavai Institutions Department of AIML

The modified Post's Correspondence Problem (MPCP) is just like PCP

except that we specify both the set of tiles and also a special tile. Matches for
MPCP have to start with the special tile.

Reduction to MPCP to PCP We are almost done, but not quite. Since our
reduction only show that

MPCP is undecidable, but we want to show that PCP is decidable.

An instance of MPCP is a set of tiles (just like an instance of PCP), with the
additional constraint that a specific tile is denoted as an initial tile that must be used
as the first tile in the matching.

As such, to convert this instance T of MPCP into PCP we need to some how
remove the need to specify the initial tile.

5.4 Universal Turing machine

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.

UNIT V 12
 Paavai Institutions Department of AIML

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

UNIT V 13
 Paavai Institutions Department of AIML

If no transition for a given ID is formed, Mu halts as M must :

 In either case, Mu behaves as M would.

 If M halts, when presented with string w then Mu will halt when presented
with the encoded M and the encoded string on its tape.
 Moreover, the final string Mu .s tape will be the encoding of the string.
 When M halts, Mu can tell if it is in the single accepting state and so moves
to an accepting state of its own ( or not).
Difference between Universal Turing Machine and Turing Machine

UNIT V 14
 Paavai Institutions Department of AIML

5.5 Tractable and Intractable problems

Tractable Problem: A problem that is solvable by a polynomial-time algorithm.

The upper bound is polynomial.
Here are examples of tractable problems (ones with known polynomial-time
algorithms):
– Searching an unordered list
– Searching an ordered list
– Sorting a list
– Multiplication of integers (even though there’s a gap)
– Finding a minimum spanning tree in a graph (even though there’s a gap)

Intractable Problem: a problem that cannot be solved by a polynomial-time algorithm.

The lower bound is exponential.From a computational complexity stance, intractable
problems are problems for which there exist no efficient algorithms to solve them.
Most intractable problems have an algorithm that provides a solution, and that
algorithm is the brute-force search.
This algorithm, however, does not provide an efficient solution and is, therefore,
not feasible for computation with anything more than the smallest input.

Examples
Towers of Hanoi: we can prove that any algorithm that solves this problem must have a
worst-case running time that is at least 2n − 1.
* List all permutations (all possible orderings) of n numbers.

5.6 P and NP completeness

P-Class:

 The class P consists of those problems that are solvable in polynomial time, i.e.
these problems can be solved in time O(nk) in worst-case, where k is constant.
 These problems are called tractable, while others are called intractable or super
polynomial.

 Formally, an algorithm is polynomial time algorithm, if there exists a polynomial

p(n)such that the algorithm can solve any instance of size n in a time O(p(n)).

UNIT V 15
 Paavai Institutions Department of AIML

 Problem requiring Ω(n50)time to solve are essentially intractable for large n. Most
known polynomial time algorithm run in time O(nk) for fairly low value of k.
 The advantages in considering the class of polynomial-time algorithms is that all
reasonable deterministic single processor model of computation can be simulated
on each other with at most a polynomial slow-d.

NP-Class:

The class NP consists of those problems that are verifiable in polynomial time.
NP is the classofdecisionproblemsforwhichitiseasytocheckthecorrectnessofaclaimedanswer,
with the aid of a little extra information.
 Hence, we aren’t asking for a way to find a solution, but only to verify that an
alleged solution really is correct.
 Every problem in this class can be solved in exponential time using
exhaustive search
5.6.1 Example of P Class Problem:
Kruskal's algorithm is famous P-Class problem known to get MST. This algorithm generate
Minimum Spanning Tree in polynomial time. Related problems is one of the unit of Automata
Theory, where we learn complexity and decision problems.
Example for Kruskal’s Algorithm:

Step 1 : Remove all loops and Parallel Edges

Remove all loops and parallel edges from the given graph.

UNIT V 16
 Paavai Institutions Department of AIML

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 : Arrange all edges in their increasing order of weight

The next step is to create a set of edges and weight, and arrange them in an ascending order of
weightage (cost).

The least cost is 2 and edges involved are B,D and D,T. We add them. Adding them does not
violate spanning tree properties, so we continue to our next edge selection.
Next cost is 3, and associated edges are A,C and C,D. We add them again

UNIT V 17
 Paavai Institutions Department of AIML

Now we are left with only one node to be added. Between the two least cost edges available 7 and
8, we shall add the edge with cost 7.

UNIT V 18
 Paavai Institutions Department of AIML

Following are the differences between the P class problem and the NP class problem:

Sr. P class Problem NP class Problem

No

1. P problems are a set of problems that can be NP problems are problems that can be solved in
solved in polynomial time by deterministic nondeterministic polynomial time.
algorithms.

2. P Problems can be solved and verified in The solution to NP problems cannot be obtained in
polynomial time. polynomial time, but if the solution is given, it can be
verified in polynomial time.

3. P problems are a subset of NP problems. NP Problems are a superset of P problems.

4. All P problems are deterministic in nature. All the NP problems are non-deterministic in nature.

5. It takes polynomial time to solve a problem like It takes non-deterministic polynomial time to quickly check
n, n^2, n*logn, etc. a problem.

6. The solution to P class problems is easy to find. The solution to NP class problems is hard to find.

7. Examples of P problems are: Selection sort, Examples of NP problems are the Travelling salesman
Linear Search problem and the knapsack problem.

UNIT V 19
 Paavai Institutions Department of AIML

5.6.2 Travelling Salesman Problem

The travelling salesman problem(TSP) is a solution where a salesman has to start from one
place and go to all other cities just once and then come back to their own place. TSP is all about
finding the minimum distance path. The polynomial-time hardness is called NP Hard which
defines the property of a class of problems. The subset sum is a simple example of NP hard
problem.
NP-hard − The class of problem which cannot be solved within a polynomial time is called NP-
hard.
Let’s take an example of five cities to understand how salesmen travel to each city by taking the
minimum distance.

Which one we will prefer among these two possibilities of figure?

In these two figures, figure II represents the least/minimum distance path. In figure I, when
salesmen travel from Chennai (point 1) to Hyderabad(point 5) it takes a lot of time to reach its
own location and total distance covered i.e.( 1 -> 2 -> 3 -> 4 -> 5 -> 1 ) but in the case of figure
II the salesman directly reach the point at 3(Mumbai) which saves the time and also cover the
total minimum distance i.e. ( 1 -> 3 -> 5 -> 1 ).
Can we find the possibilities of 32 cities problem?
The possibility is given by (n-1)!/2 solution.

UNIT V 20
 Paavai Institutions Department of AIML
5.6.3 3CNF SAT
Concept: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost 3
literals or constants

Such as (X+Y+Z) (X+Y+Z) (X+Y+Z)

You can define as (XvYvZ) ᶺ (XvYvZ) ᶺ (XvYvZ)
V=OR operator
^ =AND operator
These all the following points need to be considered in 3CNF SAT.
To prove: -
Concept of 3CNF SAT
SAT≤ρ 3CNF SAT
3CNF≤ρ SAT
3CNF ϵ NPC
CONCEPT: - In 3CNF SAT, you have at least 3 clauses, and in clauses, you will have almost 3
literals or constants.
SAT ≤ρ 3CNF SAT:- In which firstly you need to convert a Boolean function created in SAT into
3CNF either in POS or SOP form within the polynomial time
F=X+YZ
= (X+Y) (X+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
3CNF ≤p SAT: - From the Boolean Function having three literals we can reduce the whole
function into a shorter one.
F= (X+Y+Z) (X+Y+Z') (X+Y'+Z)
= (X+Y+Z) (X+Y+Z') (X+Y+Z) (X+Y'+Z)
= (X+Y+ZZ') (X+YY'+Z)
= (X+Y) (X+Z)
= X+YZ
3CNF ϵ NPC: - As you know very well, you can get the 3CNF through SAT and SAT
through CIRCUIT SAT that comes from NP.

UNIT V 21
 Paavai Institutions Department of AIML

Proof of NPC:-
It shows that you can easily convert a Boolean function of SAT into 3CNF SAT and
satisfied the concept of 3CNF SAT also within polynomial time through Reduction
concept.
If you want to verify the output in 3CNF SAT then perform the Reduction and convert into
SAT and CIRCUIT also to check the output
If you can achieve these two points that means 3CNF SAT also in NPC

UNIT V 22
 Paavai Institutions Department of AIML

5.7 Question Bank

Part – A
1. When we say a problem is decidable? Give an example of undecidable problem?
2. Give examples of decidable problems.
3. Give examples of recursive languages?
4. Differentiate recursive and recursively enumerable languages.
5. What are UTMs or Universal Turing machines?
6. What is the crucial assumptions for encoding a TM?
7. What properties of recursive enumerable seta are not decidable?
8. What is a universal language Lu?
9. What is a Diagonalization language Ld?
10. What properties of r.e sets are recursively enumerable?
11. What properties of regular expression sets are not regular expression?
12. What is canonical ordering?
13. State a single tape TM started on blank tape scans any cell four or more times is
decidable?
14. Does the problem of “Given a TM M, does M make more than 50 moves on input B “?
15. Show that AMBIGUITY problem is un-decidable.
16. State the halting problem of TMs.
17. Define PCP or Post Correspondence Problem.
18. Define MPCP or Modified PCP.
19. What is the difference between PCP and MPCP?
20. What are the concepts used in UTMs?
21. What are(a) recursively enumerable languages (b) recursive sets?

PART – B
1. (i)Describe about the tractable and intractable problems.
(ii)Identify that “MPCP reduce to PCP”.
2. (i)Describe about Recursive and Recursive Enumerable languages with example.
(ii)State and describe RICE theorem.
3. (i)Summarize diagonalization language.
(ii)Discuss the significance of universal turing machine and also construct a turing
machine to add two numbers and encode it.

UNIT V 23
 Paavai Institutions Department of AIML

4. Discuss post correspondence problem .Let ∑={0,1}.Let A and B be the lists of three
strings each defined as
(i) Does the PCP have a solution?(7)
(ii) Prove that the universal language is recursively enumerable.
5. (i)Explain computable functions with suitable example.
(ii)Explain in detail notes on Unsolvable Problems.
6. (i) Describe in detail notes on universal Turing machines with example.
(ii) Collect and write the short notes on NP-complete problems.
7. (i) Show that the diagonalization language (Ld) is not a recursively enumerable.
(ii) Illustrate about unsolvability.
8. (i) Compare the difference between recursive and recursively enumerable
languages.
(ii) Explain about PCP.
9. Prove that for two recursive languages L1 and L2 their union and intersection is
recursive.

UNIT V 24