7
Undecidability and Computability
 Decidability and computability are the basic factors to analyse the algorithms.
In this chapter, we try to understand the importance and procedure to check whether the problem is solvable or not. As we know, computers have capabilities and limitations, and it becomes essential to have a mechanism by which we can identify an unsolvable problem, so that the problem can be altered or simplified before finding an algorithmic solution.
In the computability theory and the computational complexity theory, a decision problem is like a question in some formal system with a yes or no answer, depending on the values of some input parameters. For example, In two given numbers x & y, does x evenly divide y?’ is a decision problem. The answer can be either ‘yes’ or ‘no’, and it depends upon the values of x and y.
7.1 Decision Problems
Decision problems are closely related to function problems, which can have answers that are more complex than a simple ‘yes’ or ‘no’. A corresponding function problem is ‘given two numbers x and y, how to program for x divided by y?’ This is related to optimization problems, which is concerned with finding the best answer to a particular problem.
A method for solving a decision problem given in the form of an algorithm is called a decision procedure for that problem. A decision procedure for the decision problem ‘given two numbers x and y, does x evenly divide y?’ would give the steps for determining whether x evenly divides y. One such algorithm is by long division, taught to many school children. If the remainder is zero, the answer produced is ‘yes’; otherwise, it is ‘no’. A decision problem that can be solved by an algorithm, such as the example of divisibility discussed above, is called decidable.
The field of Computational Complexity categorizes the decidable decision problems depending on difficulty with which they are solved. ‘Difficulty’, in this sense, is described in terms of the computational resources needed by the most efficient algorithm for a certain problem.
The field of Recursion Theory, categorizes undecidable decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution.
Definition 1: A decision problem is any arbitrary yesorno question on an infinite set of inputs. Because of this, it is usual to define the decision problem equivalently as follows: The set of inputs for which the problem returns yes. These inputs can be natural numbers, but values of some other kind, such as strings of a formal language, can also be inputs.
Using some encoding, such as Gödel numbers (Gödel numbering is a function that assigns to each symbol and wellformed formula of some formal language, a unique natural number, called its Gödel number), the strings can be encoded as natural numbers. Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.
Formally, a decision problem is a subset of the natural numbers. The corresponding informal problem is that of deciding whether a given number is in the subset.
A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is a prime by testing every possible nontrivial factor.
7.2 Decidability and Decidable Languages
A decision problem ‘A’ is called decidable or effectively solvable if ‘A’ is a recursive set. A problem is called partially decidable, solvable, or provable if ‘A’ is a recursively enumerable set. Partially decidable problems and other problems that are not decidable are called undecidable.
In this section, we give examples of languages that are decidable by algorithms.
7.2.1 Decidable Problems Concerning Regular Languages
We can find some algorithms for testing whether a finite automaton accepts a string, whether the language of a finite automaton is empty and whether two finite automata given are equivalent.
A DFA defines a decidable language.
Solution: We need to construct a turing machine M such that M = <B, a> where B is the description of DFA and w is a string to be processed.
 Simulate B on input w.
 If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject.
To construct such a turing machine, the five components of DFA Q, ∑, δ, q_{0} and F can be used in the TM. When M receives its input, M first determines whether machine properly represents a DFA B and a string w. If not, M rejects. Then M carries out simulation directly. It keeps track of B’s current state and B’s current position in the input w by writing the information down on its tape. Initially, B’s current state is q_{0}, and B’s current input position is the leftmost symbol of w. The states are updated according to a specified transition function δ. When M finishes processing the last symbol of w, M accepts the input if B is in an accepting state, and M rejects the input if B is in a nonaccepting state.
Language accepted by NFA is decidable.
Solution: We need to construct a turig machine N such that N = <B, a>, where B is the description of NFA and w is a string.
 Convert Nondeterministic FA B to an equivalent DFA C, using NFAtoDFAconversion procedure.
 Run turing machine M to simulate C on input w, as explained in previous example.
 If M accepts the string w; then B accepts w, otherwise rejects.
Language generated by regular expression is a decidable language.
Solution: We can construct a turing machine P such that P = <R, w>, where R is a regular expression and w is the string.
 Convert regular expression R to an equivalent NFA A, by using REtoNFA conversion procedure.
 Run turing machine M on input <A, w>.
 If M accepts w then ρ accepts, otherwise rejects.
Emptiness of DFA is a decidable language.
Solution: We can construct a turing machine T such that T = <A, w> where A is a DFA.
 Mark the start state of A.
 Mark any state that has a transition coming into it from any state that is already marked.
 Repeat step2 until no new states get marked.
 If no accept state is marked, then accept; otherwise reject.
Equivalence of DFA’s is a decidable language.
Solution: To prove this, we construct a new DFA C from A and B, where C accepts only those strings that are accepted by either A or B, but not by both. Thus if A and B recognize the same language, C will accept nothing. The language of C is
We can construct a turing machine F such that F = <A, B> where A and B are DFAs.
 Construct a DFA C as described. Mark the start state of A.
 Run TM T as explained in previous example on input <C>.
 If T accepts, then accept; otherwise reject.
7.2.2 Decidable Problems Concerning Context Free Languages
In this section, we describe the algorithms that can be used to determine whether the given CFG can generate the given string or to find whether the given CFG is empty.
Language of context free grammar G is a decidable.
Solution: We need to find whether the given string can be generated by the grammar G. One approach that can be used is to generate all the strings and check whether the given string w is generated. But this approach does not work, sometimes the turing machine may not halt. It may enter into an infinite loop trying to recognize rather than decide and report whether it is valid or not.
Second procedure is to convert the given grammar to CNF, so that for a string w of length n, there would be at most 2^{n}^{−}^{1} steps to generate the string. Hence, it ensures that the turing machine would halt after generating strings using at most 2^{n}^{−}^{1} steps. It can also decide and say whether the string is valid or not.
TM for this can be defined as S = <G, w> where G is the given grammar and w is the string given:
 Convert the G to CNF.
 List all derivations of the grammar starting from 1 to a maximum of 2^{n}^{−}^{1} steps, where n is the length of w.
 If any of these derivations correspond to w, then accept; otherwise, reject.
Emptiness of Context free grammar G, is decidable.
Solution: Consider the given grammar G and to check if the grammar is empty simple approach is to write an algorithm that may go through all possible w’s one by one. But this may go into an infinite loop.
Emptiness of the language can be found out in finite amount of time. Start with the start symbol and check whether it can generate the string of terminals. To do this in simple way, first mark all the terminals, then scan all the rules and mark the variables that can be replaced by terminal or by a variable that is already marked. Repeat until no new symbols are marked. If the start symbol is marked, then the language of the grammar is not empty.
Let R be the TM given by R = <G> where G is the given context free grammar.
 Mark all terminal symbols of the grammar.
 Repeat until no new variables are marked.
 Mark any variable A of G if the rule for A is of the form A → X_{1}X_{2}X_{3} … X_{n} where all X_{i}’s are already marked.
 If the start symbol is not marked, then accept; otherwise, reject.
7.3 Halting Problem
In the previous section, we stated that the problems are said to be decidable if there exists an algorithm that can solve the problem in finite amount of time. There are some specific problems that are algorithmically unsolvable. Although the computers are so powerful, there are some limitations. For example, computers cannot easily avoid crashing, or rather, they cannot predict when they are about to crash and avoid it. In this section, we try to understand a few problems that are unsolvable and learn techniques for proving unsolvability.
Turing machines
A Turing machine is an extremely powerful model of a computing device, and could be programmed to solve many problems. The TM is a theoretical computer, which works by storing data on a tape of infinite length and moving back and forth along it according to the program. Even the program itself can be stored on the tape, and these machines are called Universal TM. Turing programs either halt when they have arrived at the results or else they continue for ever. No Turing program can be said to have produced any result until it has halted.
7.3.1 The Halting Problem for Turing Machines
Halting problem of the TM is formulated as follows: Given an arbitrary TM and an arbitrary input for the machine, will the given machine halt on the given input?
In other words, Turing wondered whether it would be possible to write a TM program that would take two inputs <program P, input i> and would answer ‘Yes’ if the TM halts when executing program P on input i, and would answer ‘No’ if it wouldn’t halt, that is, if it would loop for ever.
Solution can be found by giving a description number to every possible TM program, so that no possible programs is left out. One way to figure out if there is a program that can solve the halting problem would be to look through all the whole numbers, interpreting each as the description number of a TM program, and checking to see if it is the program that solves the halting problem.
Of course, this is completely impractical. But Turing realized that if we could prove that no whole number was the right one, then we would know that no program to solve the halting problem exists.
Theorem 1: A TM is recognizable, but not decidable. A recognizer of a TM is called the Turing Universal Machine U, where U = <M, w>, where M is a TM and w is a string
 Simulate M on w;
 If M ever enters its accept state, accept; if M ever enters its reject state, reject’.
Note: U is a universal because it simulates any other TM from its description. Important points to understand here are
 All problems may be solvable, but all are not decidable.
 Since a TM is undecidable, to solve this problem, we need to expand the problemsolving methodology by a new method for proving undecidability.
7.4 Diagonalization Method
The method used to prove the undecidability of the halting problem is proposed by Georg Cantor in 1873, and this method is called diagonalization. Suppose there are two sets to be compared. Suppose set one is the set of even numbers less than 20. Let the other set be the set of multiples of 2 till 10. To find whether these sets are equal, simple method is to count the number of elements in both the sets and find the answer. For finite sets, it is easy to find the answer, but for infinite sets counting the elements is a difficult task.
Cantor proposed a solution to this problem. The two sets would be of same size if every element of one set can be paired with the elements of the other set. This kind of solution does not require counting of elements in either set. The same procedure can be extended to infinite sets.
Definition 2: Assume two sets A and B, and let function f: A → B. If f is onetoone and onto, i.e, if f(a) ≠ f(b) or if every element of B is mapped with element of A such that f(a) = b ∀ a ∈ A,b ∈ B. This correspondence can be used to find solutions to problems corresponding to size.
Let N be the set of natural numbers {1, 2, 3, 4,…..}, and let E be the set of even numbers {2, 4, 6,……}. Are these sets of same size
Solution: Using Cantor’s definition of size, we can say that these two sets are of same size. The relation between N and E can be given by a function F(n) = 2n. It appears that E is a subset of N, but pairing each member of N with its own member if E is possible. Hence, these sets are of same size.
Can the natural numbers set be compared with set of rational numbers , Justify.
Solution: The set Q appears to be larger than N, but these two sets are of same size according to Cantor’s definition. We give a correspondence with N to show that Q is countable. To show this
 Pair the first element on the list with number 1 in N.
 Pair each consecutive element on the list with successive elements in N.
 Ensure that every member of Q appears only once on the list.
To construct a unique list Q, we make use of the infinite matrix containing all positive elements as shown below.
In the above infinite matrix, the ith row contains all numbers with numerator as I, and the jth column has all the numbers with denominator as j. So he number i/j is in ith row and jth column.
List is formed by reading the elements diagonally skipping the elements which give same value.
In second diagonal and are selected
In third diagonal and are selected, is skipped as it is same as
Similarly the list Q is formed. Now it is easy to show correspondence of N with Q.
From the above two examples, it is clear that if we can show the correspondence, it is easy to find the solution. But for some cases, it is difficult even to show this correspondence. Such sets are called uncountable. Set of real numbers is an example of uncountable sets.
7.4.1 Undecidable Problems
M = {<M, w> M is a TM, w is a string, M accepts w} Assume a TM is decidable, which halts and says accepted or rejected. Let H be a machine for a TM <M, w>. Then, H halts and accepts, if M accepts w; or H rejects, if M fails to accept w. To put more formally,
H(<H, w>) = {accept if M accept w.
Construct a new truing machine D with H as subroutine. D calls H to find what M does when input to M is its own description <M>. that is, D is running a machine as its own description. It is just like a compiler written and compiled in the same language. D gets information and complements the action.
D is defined as <M> where M is a TM.
 Runs H on input <M, <M>>.
 If H accepts, it rejects, if H rejects, it accepts.
In summary,
When we run D with its own description <D> as input? In that case, we get
It is forced to do opposite to what D does. Thus neither TM D nor TM H exists.
7.5 Post’s Correspondence Problem
Definition 3: Given an alphabet S, one instance of Post’s Correspondence Problem (PCP) of size s is a finite set of pairs of strings (g_{i}, h_{i}) ( i = 1 ... s s ≥ 1) over the alphabet S. A solution of length n ≥ 1 to this instance is a sequence i_{1} i_{2} ... i_{n} of selections such that the strings g_{i1 }g_{i2} ... g_{in} and h_{i1 }h_{i2} ... h_{in} formed by concatenation are identical.
Width of a PCP instance is the length of the longest string in gi and h_{i} (i = 1, 2, ..., s). We use Pair i as a short name for pair (g_{i}, h_{i}), where g_{i} and h_{i} are the top string and bottom string of the pair, respectively. Mostly, people are interested in optimal solution, which has the shortest length over all possible solutions to an instance. The corresponding length is called optimal length. We use the word hard or difficult to describe instances whose optimal lengths are very large. For simplicity, we restrict the alphabet S to {0, 1}, and it is easy to transform other alphabets to their equivalent binary format.
To describe subclasses of Post’s Correspondence Problem, we use PCP[s] to represent the set of all PCP instances of size s, and PCP[s, w] to represent the set of all PCP instances of size s and width w.
For convenience, we use a matrix of 2 rows and s columns to represent instances of PCP[s], where string g_{i} is located at (i, 1) and h_{i} at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP [3, 3].
i 
g_{i} 
h_{i} 
1 
100 
1 
2 
0 
100 
3 
1 
0 
Let us consider the results of selections of sequence {1, 3, 1, 1, 3, 2, 2} accordingly. They are shown in the following table and each selection is shown in the table.
After the elimination of blanks and concatenation of strings in the top and bottom rows separately, we get
Now, the string in the top is identical to the one in the bottom. Therefore, these selections form a solution to the PCP problem.
Consider the following sequence and find whether it has solution or not.
I 
g_{i} 
h_{i} 
1 
01 
0 
2 
110010 
0 
3 
1 
1111 
4 
11 
01 
The tuple (i_{1}, i_{2}, i_{3}, i_{4}, i_{5}, i_{6}) = (1, 3, 2, 4, 4, 3) is a witness for a positive solution because x_{1}x_{3}x_{2}x_{4}x_{4}x_{3} = y_{1}y_{3}y_{2}y_{4}y_{4}y_{3} = 01111001011111. The positive solution has also the witnesses (1, 3, 2, 4, 4, 3, 1, 3, 2, 4, 4, 3), (1, 3, 2, 4, 4, 3, 1, 3, 2, 4, 4, 3, 1, 3, 2, 4, 4, 3), etc.
Consider the following sequence and find whether it has a solution or not.
i 
g_{i} 
h_{i} 
1 
0 
10 
2 
1 
1 
This problem has no solution as the strings formed by g’s would always start with 0, and the strings formed by h’s would always start with 1.
7.5.1 The Undecidability of Post’s Correspondence Problem
Post’s correspondence problem is very useful for showing the undecidability of many other problems by means of reducibility. Its undecidability follows from its capacity for simulating the computations of TMs, as exhibited indirectly in the following proof through derivations in Type 0 grammars.
7.5.2 Modified Version of PCP
We can show that PCP is decidable if the modified version of PCP is decidable. To show it is decidable, we would have an algorithm for L_{u}.
The Modified Post’s Correspondence Problem (MPCP) is described as given lists G and H of kstrings each from Σ*, say
does there exist a sequence of integers, i_{1}, i_{2}….i_{r} such that
The difference between the MPCP and PCP is that in the MPCP, a solution is required to start with the first string on each list.
If we have a problem instance represented in MPCP, then it can be reduced to PCP. If there is a solution for PCP instance, then there exists a solution for MPCP instance.
Lemma 1: If PCP were decidable, then MPCP would be decidable, that is MPCP reduces to PCP.
Procedure to convert MPCP to PCP:
 Let the lists G and H be the given instance of MPCP.
 Let Σ be the smallest alphabet containing all the symbols in the lists G and H.
 Consider two special symbols {θ, $} not present in Σ, and find two new lists X from G and Y from H using the following rules.
 x_{i} of list X is obtained from g_{i} by inserting $ symbol after each character of g_{i}.
 y_{i} of list Y is obtained from h_{i} by inserting $ symbol before each character of h_{i}.
 Create new words as follows:
x_{0} = $g1,y_{0} = h1x_{k+1} = θ,y_{k+1} = $θ
Consider the following MPCP instance and find whether it has a solution.
i 
g_{i} 
h_{i} 
1 
100 
1 
2 
0 
100 
3 
1 
00 
Solution: This problem can be converted to MPCP by applying the above procedure.
i 
x_{i} 
y_{i} 
0 
$1$0$0$ 
$1 
1 
1$0$0$ 
$1 
2

0$ 
$1$0$0 
3 
1$ 
$0$0 
4 
θ 
$θ 
PCP problem would have solution if there is a sequence in MPCP as 0, i_{1}, i_{2}, i_{3}… i_{r}, k + 1, which is solution with the list X and Y. Then there is sequence as i_{1}, i_{2}, i_{3}… i_{r} which is a solution with lists G and H.
Let the sequence be 0, 3, 1, 1, 3, 2, 2, 4
String formed from list X: $1$0$0$1$1$0$0$1$0$0$1$0$0$θ
String formed from list Y: $1$0$0$1$1$0$0$1$0$0$1$0$0$θ
Since there is solution for MPCP, the solution for PCP is 3, 1, 1, 3, 2, 2, 4.
Does the following PCP problem have a solution.
Solution:
There is a solution for PCP and is 2, 1, 1, 3.
Explain how PCP can be treated as a game of dominoes.
Solution: In the game of dominoes, upper half and lower half have strings say A_{i} B_{i} as shown below:
A_{i}: a_{1}a_{2}a_{3} 
Upper Half 
B_{i}: b_{1}b_{2}b_{3} 
Lower Half 
To win a game, the same string must appear in A_{i }and_{ }B_{i}, that is, a_{1}a_{2}a_{3} = b_{1}b_{2}b_{3}.
Winning the game is equivalent_{ }to getting solution for PCP.
Consider the PCP system with two strings A and B with A = {1, 0, 010, 11} and B = {10, 10, 01, 1}. Find whether PCP problem has a solution or not.
Solution:
There is solution for PCP and it is 1, 2, 1, 3, 3, 4.
Theorem 2: The PCP is an undecidable problem.
Proof: From the above lemma, it is sufficient to show that if MPCP were decidable, then it would be decidable whether a TM accepts a given word. We reduce the Lu to MPCP, which is reduced to PCP. For each M and w, we construct an instance of MPCP that has a solution if and only if M accepts w. We do this by constructing an instance of MPCP that, if it has a solution, has one that starts with #q_{0}w#α_{1}q_{1}β_{1}#.......#α_{k}q_{k}β_{k}# where strings between successive #’s are successive IDs in a computation of M with input w, and q_{k} is a final state.
Procedure to convert decidability of TM to MPCP:

List X 
List Y 
Basic string to be added 
# 
#q_{0}w# 
Group I 
X 
X 
For each X in τ add strings to both x & y list 
# 
# 
Group II 


For each q in Q − F, p in Q, and X, Y and Z in τ 


If δ(q, X) = (p, Y, R) 
qX 
Yp 
If δ(q, X) = (p, Y, L) 
ZqX 
pZY 
If δ(q, B) = (p, Y, R) 
q# 
Yp# 
If δ(q, B) = (p, Y, L) 
Zq# 
pZY# 
Group III 
XqY 
q 
For each q in F, and X and Y in τ 
Xq 
q 

qY 
q 
Group IV 
q## 
# 
For each q in F 


Let us say that (x, y) is a partial solution to MPCP with lists X and Y if s is a prefix of y, and x and y are the concatenation of corresponding strings of lists A and B, respectively. If xz = y, then call z the remainder of (x, y).
Consider the following Turing machine defined as
State whether for the string w = ab, Turing machine halts.
Solution: First let us convert this problem instance to MPCP form:

List X 
List Y 
Basic string to be added 
# 
q_{0}ab# 
Group I 
a 
a 
For each X in τ add strings as 
b 
b 

# 
# 
Group II 


For each q in Q − F, p in Q, and X, Y and Z in τ 


δ(q_{0}, a) = (q_{1}, b, R) 
q_{0}a 
bq_{1} 



δ(q_{0}, b) = (q_{1}, a, L) 
aq_{0}b 
q_{1}aa 

bq_{0}b 
q_{1}ba 
δ(q_{0}, B) = (q_{1}, b, L) 
aq_{0}# 
q_{1}ab# 

bq_{0}# 
q_{1}ab# 
δ(q_{1}, a) = (q_{A}, a, L) 
aq_{1}a 
q_{A}aa 

bq_{1}a 
q_{A}ba 
δ(q_{1}, b) = (q_{0}, a, R) 
q_{1}b 
aq_{0} 
δ(q_{1}, B) = (q_{1}, a, R) 
q_{1}# 
aq_{1}# 
Group III 
aq_{A}a 
q_{A} 
For each q in F, and X and Y in τ 
bq_{A}a 
q_{A} 
aq_{A}b 
q_{A} 

bq_{A}b 
q_{A} 

q_{A}a 
q_{A} 

q_{A}b 
q_{A} 

aq_{A} 
q_{A} 

bq_{A} 
q_{A} 

Group IV 
q_{A} ## 
# 
For each q in F 


To find a solution for the instance w = ab, we start with a partial solution (#, #q_{0}ab#).
Choose the pair (q_{0}a, bq_{1}) that would result in partial solution as (#q_{0}a, #q_{0}ab# bq_{1}).
Similarly, make the choices in the following order:
Choice used 
Partial solution 
(b, b) 
(#q_{0}ab, #q_{0}ab#bq_{1}b) 
(#, #) 
(#q_{0}ab#, #q_{0}ab#bq_{1}b#) 
(b, b) 
(#q_{0}ab#b, #q_{0}ab#bq_{1}b#b) 
(q_{1}b, aq_{0}) 
(#q_{0}ab#bq_{1}b, #q_{0}ab#bq_{1}b#baq_{0}) 
(#, #) 
(#q_{0}ab#bq_{1}b#, #q_{0}ab#bq_{1}b#baq_{0} #) 
(b, b) 
(#q_{0}ab#bq_{1}b#b, #q_{0}ab#bq_{1}b#baq_{0} #b) 
(aq_{0}#, q_{1}ab#) 
(#q_{0}ab#bq_{1}b#baq_{0}#, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#) 
(bq_{1}a, q_{A}ba) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}a, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}ba) 
(b, b) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}ba) 
(#, #) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}ba#) 
(q_{A}b, q_{A}) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}b, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}ba#q_{A}) 
… 

… 

(q_{A}b, q_{A}) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}bab#q_{A}ab#, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab#q_{A}bab#q_{A}ab#q_{A}b#) 
(q_{A}##, #) 
(#q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab# q_{A}bab#q_{A}ab#q_{A}b#q_{A}##, #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab# q_{A}bab#q_{A}ab#q_{A}b#q_{A}##) 
Thus, the shortest word that can be composed of corresponding strings from lists X and Y, starting with pair 1 is #q_{0}ab#bq_{1}b#baq_{0}#bq_{1}ab# q_{A}bab#q_{A}ab#q_{A}b#q_{A}##.
7.6 Reducibility
In Computability Theory and Computational Complexity Theory, a reduction is a transformation of one problem into another problem. Problem A is reducible to problem B if solutions to B exist and give solutions to A whenever A has solutions. Thus, solving A cannot be harder than solving B. We write A ≤ B, usually with a subscript on the ≤ to indicate the type of reduction being used.
A quick way of solving the new problem is to transform each instance of the new problem into instances of the old problem, solve the instance of problem using our existing solution, and then use the solutions to obtain our final solution. This is perhaps the most obvious use of reductions. Reducibility can be used to measure the complexity of the problem depending on the kind of transformation used.
Another, more subtle use is the following: We have a problem that is proved to be hard to solve, we have a similar new problem or suspect that the new problem is hard to solve. If our hunch is correct, we can try to prove it by contradiction. For this, we suppose the new problem is easy to solve. Then, if we can show that every instance of the old problem can be solved easily by transforming it into instances of the new problem and solving those, then we have a contradiction. This way we can establish that the new problem is also hard.
Let us assume that we know addition, subtraction, division by two or squaring. Using this knowledge, we can multiply two numbers. For instance, multiplying 10 and 8 can be carried out as follows:
 Repeated addition of 10 by 8 times.
 Square 10 and subtract 10 twice.
 If both are even numbers, then compute ((a + b)/2)^{2} – (a − (a + b)/2)^{2}.
((a + b)/2)^{2} = ((10 + 8)/2)^{2} = 9^{2} = 81
(a − (a + b)/2)^{2} = (10 − (10 + 8)/2))^{2} = (10 − 8)^{2} = 1
((a + b)/2)^{2} – (a − (a + b)/2)^{2} = 81 − 1 = 80
We can propose many possible solutions. Problem comes when there is constraint on number of operations or on the type of operation to be applied. The reduction becomes much harder if we add the restriction that we can only use the squaring function one time only, and only at the end. This shows that the reduced problem is hard to solve. This kind of reduction corresponds to Turing reduction.
Definition 4: Given two subsets A and B of N and a set of functions F: N → N which is closed under composition, A is called reducible to B under F if
Then we write A ≤_{F} B. Let S be a subset of P(N) and let ≤ be a reduction. Then S is called closed under ≤ if
A subset A of N is called hard for S if
A subset A of N is called complete for S if A is hard for S and A is in S.
7.6.1 Properties
A reduction is a preordering (i.e. a reflexive and transitive relation) on P(N) P(N), where P(N) is the power set of the natural numbers.
Detailed Example
The following example shows how to use reduction from the halting problem to prove that a language is undecidable.
Suppose H(M, w) is the problem of determining whether a given turing machine M halts (by accepting or rejecting) on input string w. This language is known to be undecidable. Suppose E(M) is the problem of determining whether the language a given turing machine M accepts is empty (in other words, whether M accepts any strings at all). We show that E is undecidable by a reduction from H.
To obtain a contradiction, suppose R is a decider for E. We will use this to produce a decider S for H (which we know does not exist). Given input M and w (a TM and some input string), define S(M, w) with the following behaviour: S creates a TM N that accepts only if the input string to N is w and M halts on input w, and does not halt otherwise.
The decider S can now evaluate R(N) to check whether the language accepted by N is empty. If R accepts N, then the language accepted by N is empty. So, in particular, M does not halt on input w. So, S can reject. If R rejects N, then the language accepted by N is nonempty. So M does halt on input w, so S can accept. Thus, if we had a decider R for E, we would be able to produce a decider S for the halting problem H(M, w) for any machine M and input w. Since we know that such a S cannot exist, it follows that the language E is also undecidable.
7.6.2 Mapping Reducibility
We have various techniques to prove that some problems are undecidable (PCP in chapter 7.5). To prove certain languages are not Turing recognizable, we can use reducibility in a refined way. There are many ways, and the choice depends on the application. One such technique is mapping reducibility, also called as many–one reducibility.
Reducing problem A to problem B by using mapping reducibility means that there exists a computable function that converts every instance of A to a unique instance of B. If such conversion function is available, then A can be reduced to B, and A can be solved with a solver for B.
7.6.3 Formal Definition of Mapping Reducibility
Definition 5: Language A is mapping reducible to language B, written A ≤_{m} B, if there is a computable function f: Σ* → Σ*, where for every w, w ∈ A ⇔ f(w) ∈ B. The function f is called the reduction of A to B.
To test whether w ∈ A, we use reduction f to map w to f(w) and test whether f(w) ∈ B. The term mapping reduction comes from the function of mapping that provides the means of doing reduction. If one problem is mapped to another solved problem, then solution can be obtained for the first problem.
Theorem 3: If A ≤_{m} B and B is decidable, then A is decidable.
Proof: Let M be a decider for B and let f be the reduction from A to B. We describe a decider N for A as follows.
N = ‘On input w:
 Compute f(w).
 Run M on input f(w) and output whatever M outputs’.
Clearly, if w ∈ A, then f(w) ∈ B because f is a reduction from A to B. Thus M accepts f(w) whenever w ∈ A. Therefore, N works as desired.
7.7 Recursion Theorem
In mathematics and computer science, Recursion is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a selfsimilar way.
 Person’s ancestors:
 One’s parents are one’s ancestors (base case).
 The parents of one’s ancestors are also one’s ancestors (recursion step).
 Mathematical functions – Fibonacci sequence
 Fib(0) is 1 [base case]
 Fib(1) is 1 [base case]
 For all integers n > 1: Fib(n) is (Fib(n − 1) + Fib(n − 2)) [recursive definition]
7.7.1 Applications and Uses of Recursion
Recursion in language
In 5th century BC an ancient Indian linguist Pāṇini used recursion in defining the grammar rules of Sanskrit. Linguist Noam Chomsky theorizes that unlimited extension of a language such as English is possible only by the recursive definitions of grammar rules to enable embedding sentences in sentences. Recursion in linguistics enables ‘discrete infinity’ by embedding phrases within phrases of the same type in a hierarchical structure. Without recursion, language does not have ‘discrete infinity’ and cannot embed sentences into infinity.
Functional recursion
A function may be partly defined in terms of itself. A familiar example is the Fibonacci number sequence: F(n) = F(n − 1) + F(n − 2). For such a definition to be useful, it must lead to values that are nonrecursively defined, in the present case F(0) = 0 and F(1) = 1.
A famous recursive function is the Ackermann function which, unlike the Fibonacci sequence, cannot be expressed without recursion (see Section 7.9).
Recursion in computer science
Recursion in computer programming is exemplified when a function is defined in terms of itself. One example of application of recursion is in parsers for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.
Recurrence relations are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be ‘solved’ to obtain a nonrecursive definition.
An example of recursion is the definition of the factorial function, given here in C code:
unsigned int factorial(unsigned int n)
{
if (n <= 1) return 1;
else
{
return n * factorial(n−1);
}
}
The function calls itself recursively on a smaller version of the input (n − 1) and multiplies the result of the recursive call by n, until reaching the base case, analogous to the mathematical definition of factorial.
Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large. It has been claimed that recursive algorithms are easier to understand because the code is shorter and is closer to a mathematical definition, as seen in these factorial examples.
It is often possible to replace a recursive call with a simple loop, as the following example of factorial shows:
unsigned int factorial(unsigned int n) {
if (n <= 1) return 1;
unsigned int result = n;
while (–n) result *= n;
return result;
}
It should be noted that on most CPUs, the above examples give correct results only for small values of n, due to arithmetic overflow.
7.8 Rice’s Theorem
Rice’s theorem is an important result in the theory of recursive functions. A property of partial functions is trivial if it holds for all partial recursive functions or for none. At any given time
 Programs p and q are equivalent if they compute the same partial function.
 A set of strings S is nontrivial if S is not the empty set and S does not contain all strings.
 A set of programs S respects equivalence if, whenever programs p and q are equivalent, either both p and q are members of S or both p and q are nonmembers of S.
Theorem 4: Every nontrivial set of programs that respects equivalence is undecidable.
Proof: Let S be a nontrivial set of programs that respects equivalence. We prove that S is undecidable using proof by contradiction.
Assume that S is decidable. Then there must be a program called PDECIDE that decides membership in S.
This program has two answers.
We prove by contradiction showing if the program P_{DECIDE} exists then there exists a member P belong to S. We prove by a contradiction from the assumption that this program P_{DECIDE }exists. (Or, if you prefer, we will find a program p on which P_{DECIDE} gives the wrong answer. That is the contradiction).
Write a program called P_{LOOP} that loops for ever on all inputs. It is either in S or not. We can assume without loss of generality that P_{LOOP} is not in S. If P_{LOOP} is in S, then if we consider the complement of S The complement of S is decidable if and only if S is decidable.
S is nontrivial. So it must have a member. Choose any member of S, and call it P_{GEORGE}. Now we have one member of S (P_{GEORGE}) and one nonmember of S (P_{LOOP}).
In order to show that P_{DECIDE} does not work, we need to write two programs. The first we write has another program r built into it. For any r, you can build program Q_{r}. It goes like this.
Program Q_{r}(x): Run the interpreter on input (r, r). This is equivalent to running program r on itself.
Run program P_{GEORGE} on input x, and produce the same result that P_{GEORGE} produces.
Notice, by inspecting the text of the program, that Q_{r} has the following properties. We are making use of the fact that S respects equivalence here.
Observation Q1: For every r:
P_{r}(r) terminates
⇒ Q_{r} is equivalent to P_{GEORGE}
⇒ Q_{r} is a member of S
Observation Q2: For every r:
P_{r}(r) does not terminate
⇒ Q_{r} is equivalent to P_{LOOP}
⇒ Q_{r} is not a member of S
Now write a second program called P_{FOOL} as follows.
P_{FOOL} (r): Build program Q_{r} by building parameter r into Q.
Run P_{DECIDE} on input Q_{r}, and call its answer y. (We are asking PDECIDE whether Q_{r} is in S.)
If y = ‘yes’, then loop for ever, else stop.
Now we are ready to prove that P_{DECIDE} does not get the correct answer on every input. That is the contradiction that we are looking for (since we presumed that P_{DECIDE} got the right answer on every input.)
Once the following claim is proved, we are done.
Claim: P_{DECIDE} gets the wrong answer on input P_{FOOL}.
Proof of Claim: Imagine running P_{FOOL} on input P_{FOOL}. The following are evident.
P_{DECIDE}(Q_{FOOL}) = ‘yes’
⇒ P_{FOOL}(P_{FOOL}) does not terminate [by inspecting the definition of P_{FOOL}]
⇒ Q_{FOOL} is not a member of S [by Observation Q2]
So if P_{DECIDE} answers yes on input Q_{FOOL}, it got the wrong answer. (The correct answer is no, since Q_{FOOL} is not a member of S.)
⇒ P_{FOOL}(P_{FOOL}) terminates [by inspecting the definition of P_{FOOL}]
⇒ Q_{FOOL} is a member of S [by Observation Q1]
So if P_{DECIDE} answers ‘no’ on input Q_{FOOL}, it got the wrong answer. (The correct answer is yes, since Q_{FOOL} is a member of S.)
Regardless of what answer P_{DECIDE} gives on input Q_{FOOL}, the answer is wrong.
Note: Program Q_{r} needs to be constructed by program P_{FOOL}. One mechanism for doing that is to use parameter fixing. Write Q as a program with two parameters, rr and x. Then what P_{FOOL} needs to do is fix the parameter rr to the value of P_{FOOL}’s parameter r. That can be done by the computable function that fixes a parameter of a program to some particular value. That is, we use function P_{PARAM} where P_{PARAM}(Q, r) = T where P_{T}(x) = Q(r, x). That is, P_{PARAM} has fixed the first parameter of Q to a given value, r, yielding new program T.
7.9 Ackermann’s Function
Ackermann’s function is a simple example of a total function that is computable, but not primitive recursive. The function f(x) = A(x, x) grows much faster than polynomials or exponentials. A(x, y) is defined by
 If x = 0, then A(x, y) = y + 1
 If y = 0, then A(x, y) = A(x − 1, 1)
 Otherwise, A(x, y) = A(x − 1, A(x, y − 1))
To compute Ackermann’s function, A(x, y), for x = 3 and y = n, is given as
A(3, n) = 2^{(n}^{+}^{3)} − 3 and it requires at least 4^{(n}^{+}^{1)} function calls, and reaches a recursive depth of 2^{(n}^{+}^{3)} − 1.
Thus, computation of it stresses your compiler’s ability to do deep recursion efficiently. In particular, it tests your code generation for function calls. If you happened to implement tailcall elimination, you will see a very large performance gain.
Compute A(1, 1) and A(1, 2).
Solution:
A(1, 1) = A(1 − 1, A(1, 1 − 1)) 
by 3 
= A(0, A(1, 0)) 
by 2 
= A(0, A(0, 1)) 
by 1 
= A(0, 2) 
by 1 
= 3 

A(1, 2) = A(1 − 1, A(1, 2 − 1)) 

= A(0, A(1, 1)) 
by 3 
= A(0, 3) 
by 2 
= 4 
by 1 
The values for A(m, n) where 0 ≤ m ≤ 5 and 0 ≤ n ≤ 5 are shown in the following table.
Ackermann’s function, while Turing computable, grows faster than any primitive recursive function. The reason can be seen from the table: The index for the next value is also growing.
An equivalent definition is:
A(0, n) = n + 1
A(1, n) = 2 + (n + 3) − 3
A(2, n) = 2 × (n + 3) − 3
A(3, n) = 2 ^{n }^{+}^{ 3 }− 3
A(4, n) = 2^{2.....2} − 3 (n + 3 terms)
...
Remember that 2^{222} = 2^{(2(22))} = 65536, and not ((2^{2})^{2})^{2} = 2^{2 }^{×}^{ 2 }^{×}^{ 2} = 256
Solved Problems
Problem 1: Consider the following sequence and find whether it has solution or not.
i 
g_{i} 
h_{i} 
1 
0 
10 
2 
1 
1 
Solution: This problem has no solution as the strings formed by g’s would always start with 0 and the strings formed by h’s would always start with 1.
Problem 2: Prove that the PCP with two lists a = {01, 1, 1} and b = {111, 10, 11} has no solution.
Solution: Each string in a is smaller in length than each string in b. Hence, the sequence generated by strings of a will be always shorter than the sequence generated by b. Hence, the PCP has no solution.
Problem 3: Find A(2, 1).
Solution: A(2, 1) = A(1 + 1, 0 + 1)
Problem 4: Find A(2, 2).
Solution: A(2, 2) = A(1 + 1, 1 + 1)
Summary
 The languages accepted by TM are called recursively enumerable, and the subset languages are recursive languages for which a TM always halts.
 The languages that are recursive are decidable languages. The languages that are not recursive are undecidable languages.
 Rice’s theorem can be used to show problem of deciding if a language is empty is undecidable.
 Post’s correspondence problem has a solution if the concatenated strings of xi’s list and yi’s list are same.
 Any TM problem can be reduced to PCP form, and if the problem has solution then that problem is decidable.
 Any PCP can be converted to an MPCP, and solution to the problem instance is computed with some starting string.
Short Answers
 When do we say a problem is decidable? Give an example of an undecidable problem?
Answer: A problem whose language is recursive is said to be decidable. Otherwise, the problem is said to be undecidable. Decidable problems have an algorithm that takes as input an instance of the problem and determines whether the answer to that instance is ‘yes’ or ‘no’. An example of an undecidable problem is the Halting problem of the TM.
 Give examples of decidable problems.
Answer:
 Give examples of recursive languages?
Answer:
 The language L defined by L = {‘M’, ‘w’: M is a DFSM that accepts w} is recursive.
 L defined by {‘M_{1}’ ∪ ‘M_{2}’: DFSMs M_{1} and M_{2} and L(M_{1}) = L(M_{2})} is recursive.
 Differentiate recursive and recursively enumerable languages.
Answer:
Recursive languages Recursively enumerable languages 1. A language is said to be recursive iff there exists a membership algorithm for it.
2. A language L is recursive iff there is a TM that decide languages have algorithms.
1. A language is said to be r.e. if there exists a TM that accepts it.
2. L is recursively enumerable iff there is a TM that partially decidable L. (Turingacceptable languages). TMs that partially decides languages are not algorithms.
 What are UTMs or Universal Turing machines?
Answer: Universal TMs are TMs that can be programmed to solve any problem that can be solved by any Turing machine. A specific Universal Turing machine U is the following: Input to U: The encoding ‘M’ of a TM M and encoding ‘w’ of a string w. Behaviour: U halts on input ‘M’ ‘w’ if and only if M halts on input w.
 What are the crucial assumptions for encoding a TM?
Answer: There are no transitions from any of the halt states of any given TM. Apart from the halt state, a given TM is total.
 What properties of recursive enumerable seta are not decidable?
Answer:
 Emptiness
 Finiteness
 Regularity
 Context freedom.
 Define L_{1} When is l a trivial property?
Answer: L_{1} is defined as the set {<M>  L(M) is in 1}.
1 is a trivial property if 1 is empty or it consists of all r.e. languages.
 What is a universal language L_{u}?
Answer: The universal language consists of a set of binary strings in the form of pairs (M, w) where M is a TM encoded in binary, and w is the binary input string.: L_{u} = {<Mw>  M accepts w}.
 What is a diagonalization language L_{d}?
Answer: The diagonalization language consists of all strings w such that the TM M whose code is w does not accept when w is given as input.
 What properties of r.e. sets are recursively enumerable?
Answer:
 L ≠ Φ
 L contains at least 10 members.
 w is in L for some fixed w.
 L ∩ L_{u} ≠ Φ
 What properties of r.e. sets are not r.e.?
Answer:
 L = Φ.
 L = Σ *.
 L is recursive.
 L is not recursive.
 L is singleton.
 L is a regular set.
 L − L_{u} ≠ Φ.
 Show that AMBIGUITY problem is undecidable.
Answer: Consider the ambiguity problem for CFGs. Use the ‘yes–no’ version of AMB. An algorithm for FIND is used to solve AMB. FIND requires producing a word with two or more parses if one exists and answers ‘no’ otherwise. By the reduction of AMB to FIND, we conclude there is no algorithm for FIND and hence there is no algorithm for AMB.
 State the halting problem of TMs.
Answer: The halting problem for TMs is the following:
Given any TM M and an input string w, does M halt on w? This problem is undecidable as there is no algorithm to solve this problem.
 Define PCP or Post’s Correspondence Problem.
Answer: An instance of PCP consists of two lists, A = w_{1}, w_{2}, ….w_{k} and B = x_{1},….. x_{k}, of strings over some alphabet Σ.
This instance of PCP has a solution if there is any sequence of integers i_{1}, i_{2},..i_{m} with m ≥ 1 such that
w_{i1}, w_{i2},…w_{im} = x_{i1},x_{i2}, …x_{im}The sequence i_{1}, i_{2}, …i_{m} is a solution to this instance of PCP.
 Define MPCP (or Modified PCP).
Answer: The MPCP is the following: Given lists A and B of K strings from Σ*, say
A = w_{1}, w_{2}, …w_{k} and B = x_{1}, x_{2},…..x_{k}does there exist a sequence of integers i1, i2,…ir such that
w_{1}w_{i1}w_{i2}…..w_{ir} = x_{1}x_{i1}x_{i2}…x_{ir}?  What is the difference between PCP and MPCP?
Answer: The difference between MPCP and PCP is that in the MPCP, a solution is required to start with the first string on each list.
Fill in the Blanks
 The language generated by an unrestricted grammar is____________.
 _______________ problems will always have two possible solutions.
 A decision problem that can be solved by an algorithm is said to be _________.
 A decision problem A is called decidable if A is _______________.
 A partial decision problem A is called undecidable if A is _______________.
 ____________ problem of TM is formulated as “given an arbitrary input the Turing machine will halt”.
 ____________ method is used to prove the undecidability of halting problem.
 The other name for manyone reducibility is _____________.
 __________ theorem characterizes the sets of partial recursive functions.
 ___________ theorem says that all nontrivial properties about the language of a TM are undecidable.
Answers
 xxxx
 Decision
 Decidable
 Recursive set
 Recursively enumerable set
 Halting
 Diagonalization
 Mapping reducibility
 Extended Rice’s theorem
 Rice’s
Objective Question Bank
 Which one of the following is not decidable:
 Given a TM M, a string s and an integer k, M accepts s within k steps.
 Equivalence of two given TMs
 Language accepted by a given FSM is nonempty.
 Language generated by a CFG is nonempty.
 Consider the following decision problems:
(P_{1}) does a given FSM accept a given string.
(P_{2}) does a given CFG generate an infinite number of strings.
Which of the following statements is true?
 Both (P_{1}) and (P_{2}) are decidable
 Neither (P_{1}) nor (P_{2}) is decidable
 Only (P_{1}) is decidable
 Only (P_{2}) is decidable
 Consider the following problem X:
Given a TM M over the input alphabet E, any state q of M and a word w ∈ Σ^{*}, does the computation of M on w visit the state. Which of the following statements about X is correct?
 X is decidable
 X is undecidable, but partially decidable
 X is undecidable and not even partially decidable
 X is not a decision problem
 Which of the following are true?
 The member ship problem of CFLs is undecidable
 It is undecidable if a CFL is regular
 The halting problem of finite automata is undecidable
 The membership problem for type languages is decidable
 Which of the following is the strongest correct statement about a finite language over some finite alphabet Σ?
 It could be undecidable
 It is TM recognizable
 It is a CSL
 It is a regular language
 None of the above
 Consider two languages L_{1} and L_{2}, each on the alphabet Σ, f: Σ*→Σ* be a polynomial time computable bisection such that (∀x) {x ∈ L_{1} iff f(x) ∈ L_{2}}. Further let f^{−}^{1} be also polynomial time computable. Which of the following cannot be true?
 L_{1} ∈ P and L_{2} is finite
 L_{1} ∈ NP and L_{2} ∈ P
 L_{1} is undecidable and L_{2} is decidable
 L_{1} is recursively enumerable and L_{2} is recursive
 Define language L_{0} and L_{1} as follows:
L_{0} = {<M, w, 0> / M halts on w}, L_{1} = {<M, w, 1> / M halt on w}
Here <M, w, 1> is a triplet, whose first component, M, is an encoding of a TM; second component, w, is a string, and third component, i, is a bit. Let L = L_{0} ∪ L_{1}. Which of the following is true?
 L is recursively enumerable, but L is not.
 L is recursively enumerable, but L is not
 Both L and L are recursive
 Neither L, nor L, is recursively enumerable
 If PCP is decidable then MPCP is
 decidable
 undecidable
 cannot say
 none of these
 The value of A(2, 1) is
 1
 2
 3
 4
 The value of A(4, 3) is
 2^{16}
 6
 7
 8
 b
 c
 b
 b
 d
 b
 d
 a
 d
 a
Exercises
 Given an instance of TM show that this instance has no solution.
LIST ALIST BiW_{i}X_{i}11010121111310111
 Write short notes on Post’s Correspondence Problem. Explain how it can be used to prove whether a given problem is decidable or not.
 Find whether there is a solution for the following PCP instance:
A = {ba, aba, baa, b} B = {bab, baa, a, aba}.
 What do you mean by ‘decidable problems’ and ‘undecidable problems’? Give examples.
 What is a halting problem? Is halting problem solvable?
 What is a modified version of PCP? State whether the following has a solution and whether it is decidable.
LIST ALIST BiW_{i}X_{i}1111112100001311111
 Prove that whether TM halts on all inputs is undecidable.
Hint: Prove that some TM for ever remains in a loop on some inputs.