7. Undecidability and Computability – Formal Languages and Automata Theory

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 non-computability inherent in any solution.

Definition 1: A decision problem is any arbitrary yes-or-no 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 well-formed 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 non-trivial 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.

Example  7.1

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.

  1. Simulate B on input w.
  2. If the simulation ends in an accept state, accept. If it ends in a non-accepting state, reject.

To construct such a turing machine, the five components of DFA Q, ∑, δ, q0 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 q0, 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 non-accepting state.

Example   7.2

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.

  1. Convert Nondeterministic FA B to an equivalent DFA C, using NFA-to-DFA-conversion procedure.
  2. Run turing machine M to simulate C on input w, as explained in previous example.
  3. If M accepts the string w; then B accepts w, otherwise rejects.
Example   7.3

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.

  1. Convert regular expression R to an equivalent NFA A, by using RE-to-NFA- conversion procedure.
  2. Run turing machine M on input <A, w>.
  3. If M accepts w then ρ accepts, otherwise rejects.
Example   7.4

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.

  1. Mark the start state of A.
  2. Mark any state that has a transition coming into it from any state that is already marked.
  3. Repeat step-2 until no new states get marked.
  4. If no accept state is marked, then accept; otherwise reject.
Example   7.5

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

 

L(C) = (L(A) ∩ (L(B))′) ∪ ((L(A))′ ∩ L(B))

We can construct a turing machine F such that F = <A, B> where A and B are DFAs.

  1. Construct a DFA C as described. Mark the start state of A.
  2. Run TM T as explained in previous example on input <C>.
  3. 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.

Example   7.6

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 2n1 steps to generate the string. Hence, it ensures that the turing machine would halt after generating strings using at most 2n1 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:

  1. Convert the G to CNF.
  2. List all derivations of the grammar starting from 1 to a maximum of 2n1 steps, where n is the length of w.
  3. If any of these derivations correspond to w, then accept; otherwise, reject.
Example   7.7

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.

  1. Mark all terminal symbols of the grammar.
  2. Repeat until no new variables are marked.
  3. Mark any variable A of G if the rule for A is of the form A → X1X2X3 … Xn where all Xi’s are already marked.
  4. 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

  1. Simulate M on w;
  2. 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

  1. All problems may be solvable, but all are not decidable.
  2. Since a TM is undecidable, to solve this problem, we need to expand the problem-solving 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 one-to-one 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.

Example   7.8

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.

Example   7.9

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 first diagonal is selected

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.

= {reject if M does not 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.

  1. Runs H on input <M, <M>>.
  2. If H accepts, it rejects, if H rejects, it accepts.

In summary,

image

When we run D with its own description <D> as input? In that case, we get

image

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 (gi, hi) ( i = 1 ... s s ≥ 1) over the alphabet S. A solution of length n ≥ 1 to this instance is a sequence i1 i2 ... in of selections such that the strings gi1 gi2 ... gin and hi1 hi2 ... hin formed by concatenation are identical.

Width of a PCP instance is the length of the longest string in gi and hi (i = 1, 2, ..., s). We use Pair i as a short name for pair (gi, hi), where gi and hi 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 gi is located at (i, 1) and hi at (i, 2). The following is the matrix representation of the instance {{100, 1}, {0, 100}, {1, 00}} in PCP [3, 3].

i
gi
hi
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

 

1001100100100

 

1001100100100

Now, the string in the top is identical to the one in the bottom. Therefore, these selections form a solution to the PCP problem.

Example   7.10

Consider the following sequence and find whether it has solution or not.

I

gi
hi

1

01

0

2

110010

0

3

1

1111

4

11

01

The tuple (i1, i2, i3, i4, i5, i6) = (1, 3, 2, 4, 4, 3) is a witness for a positive solution because x1x3x2x4x4x3 = y1y3y2y4y4y3 = 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.

Example   7.11

Consider the following sequence and find whether it has a solution or not.

i
gi
hi
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 Lu.

The Modified Post’s Correspondence Problem (MPCP) is described as given lists G and H of k-strings each from Σ*, say

 

G = g1, g2, … gk and H = h1, h2, …. Hk,

 

does there exist a sequence of integers, i1, i2….ir such that

 

g1, gi1, gi2….gir = h1, hi1, hi2… hir

 

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:

  1. Let the lists G and H be the given instance of MPCP.
  2. Let Σ be the smallest alphabet containing all the symbols in the lists G and H.
  3. Consider two special symbols {θ, $} not present in Σ, and find two new lists X from G and Y from H using the following rules.
  4. xi of list X is obtained from gi by inserting $ symbol after each character of gi.
  5. yi of list Y is obtained from hi by inserting $ symbol before each character of hi.
  6. Create new words as follows:
    x0 = $g1,
    y0 = h1
    xk+1 = θ,
    yk+1 = $θ
Example   7.12

Consider the following MPCP instance and find whether it has a solution.

i
gi
hi
1

100

1

2

0

100

3

1

00

Solution: This problem can be converted to MPCP by applying the above procedure.

i
xi
yi
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, i1, i2, i3… ir, k + 1, which is solution with the list X and Y. Then there is sequence as i1, i2, i3… ir 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.

Example   7.13

Does the following PCP problem have a solution.

 

X = {b, babbb, ba} Y = {bbb, ba, a}

Solution:

 

String formed from list X: babbbbbba
String formed from list Y: babbbbbba

 

There is a solution for PCP and is 2, 1, 1, 3.

Example   7.14

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 Ai Bi as shown below:

Ai: a1a2a3
Upper Half
Bi: b1b2b3
Lower Half

To win a game, the same string must appear in Ai and Bi, that is, a1a2a3 = b1b2b3.

Winning the game is equivalent to getting solution for PCP.

Example   7.15

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:

String formed from list X: 10101001011
String formed from list Y: 10101001011

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 #q0w#α1q1β1#.......#αkqkβk# where strings between successive #’s are successive IDs in a computation of M with input w, and qk is a final state.

Procedure to convert decidability of TM to MPCP:

 

List X

List Y

Basic string to be added

#

#q0w#

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).

Example   7.16

Consider the following Turing machine defined as

M = ({q0, q1, qA}, {a, b}, {a, b, B}, δ, q0, B, {qA})

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

#
q0ab#

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 τ

 

 

δ(q0, a) = (q1, b, R)

q0a
bq1

 

 

 

δ(q0, b) = (q1, a, L)

aq0b
q1aa

 

bq0b
q1ba

δ(q0, B) = (q1, b, L)

aq0#
q1ab#

 

bq0#
q1ab#

δ(q1, a) = (qA, a, L)

aq1a
qAaa

 

bq1a
qAba

δ(q1, b) = (q0, a, R)

q1b
aq0

δ(q1, B) = (q1, a, R)

q1#
aq1#

Group III

aqAa
qA

For each q in F, and X and Y in τ

bqAa
qA

aqAb
qA

bqAb
qA

qAa
qA

qAb
qA

aqA
qA

bqA
qA

Group IV

qA ##
#

For each q in F

 

 

To find a solution for the instance w = ab, we start with a partial solution (#, #q0ab#).

Choose the pair (q0a, bq1) that would result in partial solution as (#q0a, #q0ab# bq1).

Similarly, make the choices in the following order:

Choice used

Partial solution

(b, b)

(#q0ab, #q0ab#bq1b)

(#, #)

(#q0ab#, #q0ab#bq1b#)

(b, b)

(#q0ab#b, #q0ab#bq1b#b)

(q1b, aq0)

(#q0ab#bq1b, #q0ab#bq1b#baq0)

(#, #)

(#q0ab#bq1b#, #q0ab#bq1b#baq0 #)

(b, b)

(#q0ab#bq1b#b, #q0ab#bq1b#baq0 #b)

(aq0#, q1ab#)

(#q0ab#bq1b#baq0#, #q0ab#bq1b#baq0#bq1ab#)

(bq1a, qAba)

(#q0ab#bq1b#baq0#bq1a, #q0ab#bq1b#baq0#bq1ab#qAba)

(b, b)

(#q0ab#bq1b#baq0#bq1ab, #q0ab#bq1b#baq0#bq1ab#qAba)

(#, #)

(#q0ab#bq1b#baq0#bq1ab#, #q0ab#bq1b#baq0#bq1ab#qAba#)

(qAb, qA)

(#q0ab#bq1b#baq0#bq1ab#qAb, #q0ab#bq1b#baq0#bq1ab#qAba#qA)

 

 

(qAb, qA)

(#q0ab#bq1b#baq0#bq1ab#qAbab#qAab#, #q0ab#bq1b#baq0#bq1ab#qAbab#qAab#qAb#)

(qA##, #)

(#q0ab#bq1b#baq0#bq1ab# qAbab#qAab#qAb#qA##, #q0ab#bq1b#baq0#bq1ab# qAbab#qAab#qAb#qA##)

Thus, the shortest word that can be composed of corresponding strings from lists X and Y, starting with pair 1 is #q0ab#bq1b#baq0#bq1ab# qAbab#qAab#qAb#qA##.

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.

Example   7.17

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:

  1. Repeated addition of 10 by 8 times.
  2. Square 10 and subtract 10 twice.
  3. If both are even numbers, then compute ((a + b)/2)2 – (a − (a + b)/2)2.

((a + b)/2)2 = ((10 + 8)/2)2 = 92 = 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: NN which is closed under composition, A is called reducible to B under F if

 

∃ f ∈ F, ∀ x ∈ N. x ∈ A ⇔ f(x) ∈ B

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

 

∀ s ∈ S. A ∈ P(N). A ≤ s ⇒ A ∈ S.

A subset A of N is called hard for S if

 

∀ s ∈ S. s ≤ A

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 pre-ordering (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 non-empty. 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:

  1. Compute f(w).
  2. 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 self-similar way.

Simple examples

  1. Person’s ancestors:
    1. One’s parents are one’s ancestors (base case).
    2. The parents of one’s ancestors are also one’s ancestors (recursion step).
  2. Mathematical functions – Fibonacci sequence
    1. Fib(0) is 1 [base case]
    2. Fib(1) is 1 [base case]
    3. 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 non-recursively 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 non-recursive 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 non-trivial 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 non-members of S.

Theorem 4: Every non-trivial set of programs that respects equivalence is undecidable.

Proof: Let S be a non-trivial 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.

 

PDECIDE(p) = yes    whenever p ∈ S.
PDECIDE(p) = no    whenever p ∉ S.

We prove by contradiction showing if the program PDECIDE exists then there exists a member P belong to S. We prove by a contradiction from the assumption that this program PDECIDE exists. (Or, if you prefer, we will find a program p on which PDECIDE gives the wrong answer. That is the contradiction).

Write a program called PLOOP that loops for ever on all inputs. It is either in S or not. We can assume without loss of generality that PLOOP is not in S. If PLOOP 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 non-trivial. So it must have a member. Choose any member of S, and call it PGEORGE. Now we have one member of S (PGEORGE) and one non-member of S (PLOOP).

In order to show that PDECIDE 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 Qr. It goes like this.

Program Qr(x): Run the interpreter on input (r, r). This is equivalent to running program r on itself.

Run program PGEORGE on input x, and produce the same result that PGEORGE produces.

Notice, by inspecting the text of the program, that Qr has the following properties. We are making use of the fact that S respects equivalence here.

Observation Q1: For every r:

      Pr(r) terminates

            ⇒ Qr is equivalent to PGEORGE

            ⇒ Qr is a member of S

Observation Q2: For every r:

      Pr(r) does not terminate

           ⇒ Qr is equivalent to PLOOP

           ⇒ Qr is not a member of S

Now write a second program called PFOOL as follows.

PFOOL (r): Build program Qr by building parameter r into Q.

Run PDECIDE on input Qr, and call its answer y. (We are asking PDECIDE whether Qr is in S.)

If y = ‘yes’, then loop for ever, else stop.

Now we are ready to prove that PDECIDE does not get the correct answer on every input. That is the contradiction that we are looking for (since we presumed that PDECIDE got the right answer on every input.)

Once the following claim is proved, we are done.

Claim: PDECIDE gets the wrong answer on input PFOOL.

Proof of Claim: Imagine running PFOOL on input PFOOL. The following are evident.

PDECIDE(QFOOL) = ‘yes’

⇒ PFOOL(PFOOL) does not terminate [by inspecting the definition of PFOOL]

⇒ QFOOL is not a member of S [by Observation Q2]

So if PDECIDE answers yes on input QFOOL, it got the wrong answer. (The correct answer is no, since QFOOL is not a member of S.)

PDECIDE(QFOOL) = ‘no’

⇒ PFOOL(PFOOL) terminates [by inspecting the definition of PFOOL]

⇒ QFOOL is a member of S [by Observation Q1]

So if PDECIDE answers ‘no’ on input QFOOL, it got the wrong answer. (The correct answer is yes, since QFOOL is a member of S.)

Regardless of what answer PDECIDE gives on input QFOOL, the answer is wrong.

Note: Program Qr needs to be constructed by program PFOOL. One mechanism for doing that is to use parameter fixing. Write Q as a program with two parameters, rr and x. Then what PFOOL needs to do is fix the parameter rr to the value of PFOOL’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 PPARAM where PPARAM(Q, r) = T where PT(x) = Q(r, x). That is, PPARAM 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

  1. If x = 0, then A(x, y) = y + 1
  2. If y = 0, then A(x, y) = A(x − 1, 1)
  3. 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 tail-call elimination, you will see a very large performance gain.

Example   7.18

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) = 22.....2 − 3 (n + 3 terms)

...

Remember that 2222 = 2(2(22)) = 65536, and not ((22)2)2 = 22 × 2 × 2 = 256

Solved Problems

Problem 1: Consider the following sequence and find whether it has solution or not.

i
gi
hi
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)

= A(1, A(2, 0))
= A(1, A(1, 1))
= A(1, 3)
= A(0 + 1, 2 + 1)
= A(0, A(1, 2))
= A(0, 4) = 4 + 1 = 5

Problem 4: Find A(2, 2).

Solution: A(2, 2) = A(1 + 1, 1 + 1)

= A(1, A(2, 1))
= A(1, 5)
= A(0 + 1, 4 + 1)
= A(0, A(1, 4)) = 1 + A(1, 4)
= 1 + A(0 + 1, 3 + 1) = 1 + A(0, A(1, 3))
= 1 + 1 + A(1, 3) = 1 + 1 + 1 + A(1, 2)
= 1 + 1 + 1 + 4 = 7

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

  1. 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.

  2. Give examples of decidable problems.

    Answer:

    1. Given a DFSM M and string w, does M accept w?
    2. Given a DFSM M, is L(M) = Φ?
    3. Given two DFSMs M1 and M2, is L(M1) = L(M2)?
    4. Given a regular expression α and a string w, does α generate w?
    5. Given a NFSM M and string w, does M accept w?
  3. Give examples of recursive languages?

    Answer:

    1. The language L defined by L = {‘M’, ‘w’: M is a DFSM that accepts w} is recursive.
    2. L defined by {‘M1’ ∪ ‘M2’: DFSMs M1 and M2 and L(M1) = L(M2)} is recursive.
  4. 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.

  5. 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.

  6. 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.

  7. What properties of recursive enumerable seta are not decidable?

    Answer:

    • Emptiness
    • Finiteness
    • Regularity
    • Context freedom.
  8. Define L1 When is l a trivial property?

    Answer: L1 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.

  9. What is a universal language Lu?

    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.: Lu = {<Mw> | M accepts w}.

  10. What is a diagonalization language Ld?

    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.

  11. 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 ∩ Lu ≠ Φ
  12. 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 − Lu ≠ Φ.
  13. 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.

  14. 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.

  15. Define PCP or Post’s Correspondence Problem.

    Answer: An instance of PCP consists of two lists, A = w1, w2, ….wk and B = x1,….. xk, of strings over some alphabet Σ.

    This instance of PCP has a solution if there is any sequence of integers i1, i2,..im with m ≥ 1 such that

     

    wi1, wi2,…wim = xi1,xi2, …xim

    The sequence i1, i2, …im is a solution to this instance of PCP.

  16. Define MPCP (or Modified PCP).

    Answer: The MPCP is the following: Given lists A and B of K strings from Σ*, say

     

    A = w1, w2, …wk and B = x1, x2,…..xk

    does there exist a sequence of integers i1, i2,…ir such that

     

    w1wi1wi2…..wir = x1xi1xi2…xir?
  17. 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

  1. The language generated by an unrestricted grammar is____________.
  2. _______________ problems will always have two possible solutions.
  3. A decision problem that can be solved by an algorithm is said to be _________.
  4. A decision problem A is called decidable if A is _______________.
  5. A partial decision problem A is called undecidable if A is _______________.
  6. ____________ problem of TM is formulated as “given an arbitrary input the Turing machine will halt”.
  7. ____________ method is used to prove the undecidability of halting problem.
  8. The other name for many--one reducibility is _____________.
  9. __________ theorem characterizes the sets of partial recursive functions.
  10. ___________ theorem says that all non-trivial properties about the language of a TM are undecidable.

Answers

  1. xxxx
  2. Decision
  3. Decidable
  4. Recursive set
  5. Recursively enumerable set
  6. Halting
  7. Diagonalization
  8. Mapping reducibility
  9. Extended Rice’s theorem
  10. Rice’s

Objective Question Bank

  1. Which one of the following is not decidable:
    1. Given a TM M, a string s and an integer k, M accepts s within k steps.
    2. Equivalence of two given TMs
    3. Language accepted by a given FSM is non-empty.
    4. Language generated by a CFG is non-empty.
  2. Consider the following decision problems:

    (P1) does a given FSM accept a given string.

    (P2) does a given CFG generate an infinite number of strings.

    Which of the following statements is true?

    1. Both (P1) and (P2) are decidable
    2. Neither (P1) nor (P2) is decidable
    3. Only (P1) is decidable
    4. Only (P2) is decidable
  3. 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?

    1. X is decidable
    2. X is undecidable, but partially decidable
    3. X is undecidable and not even partially decidable
    4. X is not a decision problem
  4. Which of the following are true?
    1. The member ship problem of CFLs is undecidable
    2. It is undecidable if a CFL is regular
    3. The halting problem of finite automata is undecidable
    4. The membership problem for type languages is decidable
  5. Which of the following is the strongest correct statement about a finite language over some finite alphabet Σ?
    1. It could be undecidable
    2. It is TM recognizable
    3. It is a CSL
    4. It is a regular language
    5. None of the above
  6. Consider two languages L1 and L2, each on the alphabet Σ, f: Σ*→Σ* be a polynomial time computable bisection such that (∀x) {x ∈ L1 iff f(x) ∈ L2}. Further let f1 be also polynomial time computable. Which of the following cannot be true?
    1. L1 ∈ P and L2 is finite
    2. L1 ∈ NP and L2 ∈ P
    3. L1 is undecidable and L2 is decidable
    4. L1 is recursively enumerable and L2 is recursive
  7. Define language L0 and L1 as follows:

    L0 = {<M, w, 0> / M halts on w}, L1 = {<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 = L0 ∪ L1. Which of the following is true?

    1. L is recursively enumerable, but L is not.
    2. L is recursively enumerable, but L is not
    3. Both L and L are recursive
    4. Neither L, nor L, is recursively enumerable
  8. If PCP is decidable then MPCP is
    1. decidable
    2. undecidable
    3. cannot say
    4. none of these
  9. The value of A(2, 1) is
    1. 1
    2. 2
    3. 3
    4. 4
  10. The value of A(4, 3) is
    1. 216
    2. 6
    3. 7
    4. 8

Answers

  1. b
  2. c
  3. b
  4. b
  5. d
  6. b
  7. d
  8. a
  9. d
  10. a

Exercises

  1. Given an instance of TM show that this instance has no solution.
     
    LIST A
    LIST B
    i
    Wi
    Xi
    1
    10
    101
    2
    11
    11
    3
    101
    11
  2. Write short notes on Post’s Correspondence Problem. Explain how it can be used to prove whether a given problem is decidable or not.
  3. Find whether there is a solution for the following PCP instance:

    A = {ba, aba, baa, b} B = {bab, baa, a, aba}.

  4. What do you mean by ‘decidable problems’ and ‘undecidable problems’? Give examples.
  5. What is a halting problem? Is halting problem solvable?
  6. What is a modified version of PCP? State whether the following has a solution and whether it is decidable.
     
    LIST A
    LIST B
    i
    Wi
    Xi
    1
    11
    111
    2
    100
    001
    3
    111
    11
  7. Prove that whether TM halts on all inputs is undecidable.

    Hint: Prove that some TM for ever remains in a loop on some inputs.