UNIT-V
UNDECIDABILITY
Design a Turing machine to add two given integers.
Solution:
Some unsolvable Problems are as follows:
(i) Does a given Turing machine M halts on all input?
(ii) Does Turing machine M halt for any input?
(iii) Is the language L(M) finite?
(iv) Does L(M) contain a string of length k, for some given k?
(v) Do two Turing machines M1 and M2 accept the same language?
It is very obvious that if there is no algorithm that decides, for an arbitrary given Turing machine
M and input string w, whether or not M accepts w. These problems for which no algorithms exist
are called “UNDECIDABLE” or “UNSOLVABLE”.
Code for Turing Machine:
Diagonalization language:
This table represents language acceptable by Turing
Proof that Ld is not recursively enumerable:
Recursive Languages:
Universal
Language:
Undecidability of Universal Language:
Problem -Reduction :
If P1 reduced to P2,
Then P2 is at least as hard as P1.
Theorem: If P1 reduces to P2 then,
• If P1 is undecidable the so is P2.
• If P1 is Non-RE then so is P2.
Post's Correspondence Problem (PCP)
A post correspondence system consists of a finite set of ordered pairs where
for some alphabet .
Any sequence of numbers
is called a solution to a Post Correspondence
The Post's Correspondence Problem is the problem of determining whether a
Post Correspondence system has a solutions.
Example 1 : Consider the post correspondence system
The list 1,2,1,3 is a solution to it.
Because
i xi yi
1
2
3
(A post correspondence system is also denoted as an instance of the PCP)
Example 2 : The following PCP instance has no solution
i xi yi
1
2
This can be proved as follows. cannot be chosen at the start, since than the LHS and RHS would
differ in the first symbol ( in LHS and in RHS). So, we must start with . The next pair must be
so that the 3 rd symbol in the RHS becomes identical to that of the LHS, which is a . After this
step, LHS and RHS are not matching. If is selected next, then would be mismatched in the 7 th symbol
( in LHS and in RHS). If is selected, instead, there will not be any choice to match the both side in
the next step.
Example3 : The list 1,3,2,3 is a solution to the following PCP instance.
i xi yi
1 1 101
2 10 00
3 011 11
The following properties can easily be proved.
Proposition The Post Correspondence System
has solutions if and only if
Corollary : PCP over one-letter alphabet is decidable.
Proposition Any PCP instance over an alphabet with is equivalent to a PCP instance over an
alphabet with
Proof : Let
Consider We can now encode every as any PCP instance over will now
have only two symbols, 0 and 1 and, hence, is equivalent to a PCP instance over
Theorem : PCP is undecidable. That is, there is no algorithm that determines whether an arbitrary
Post
Proof: The halting problem of turning machine can be reduced to PCP to show the undecidability of PCP. Since
halting problem of TM is undecidable (already proved), This reduction shows that PCP is also undecidable.
The proof is little bit lengthy and left as an exercise.
Some undecidable problem in context-free languages
We can use the undecidability of PCP to show that many problem concerning the context-free languages
are
undecidable. To prove this we reduce the PCP to each of these problem. The following discussion makes it
Let be a Post Correspondence System over the alphabet . We construct
two CFG's Gx and Gy from the ordered pairs x,y respectively as follows.
and
where
and
it is clear that the grammar generates the strings that can appear in the LHS of a sequence while solving
the PCP followed by a sequence of numbers. The sequence of number at the end records the sequence
strings from the PCP instance (in reverse order) that generates the string. generates the strings
that can be obtained from the RHS of a sequence and the corresponding sequence of numbers (in
reverse order).
Now, if the Post Correspondence System has a solution, then there must be a sequence
According to the construction of and
In this case
Hence , and implying
Conversely, let
Hence, w must be in the form w1w2 where and w2 in a sequence (since, only that kind of
strings can be generated by each of and ).
Now, the string is a solution to the Post Correspondence System.
It is interesting to note that we have here reduced PCP to the language of pairs of CFG,s whose intersection is
nonempty. The following result is a direct conclusion of the above.
Theorem : Given any two CFG's G1 and G2 the question "Is " is undecidable.
Proof: Assume for contradiction that there exists an algorithm A to decide this question. This would imply
that
For any Post Correspondence System, P construct grammars and by using the constructions
elaborated already. We can now use the algorithm A to decide whether and
Thus, PCP is decidable, a contradiction. So, such an algorithm does not
If and are CFG's constructed from any arbitrary Post Correspondence System, than it is not difficult
show that and are also context-free, even though the class of context-free languages are
closed under complementation.
and their complements can be used in various ways to show that many other questions
related to CFL's are undecidable. We prove here some of those.
Theorem : Foe any two arbitrary CFG's the following questions are undecidable
i. Is
ii. Is
iii. Is
Proof :
i. If then,
Hence, it suffice to show that the question “Is " is undecidable.
Since, and are CFl's and CFL's are closed under union, is also context-
free. By DeMorgan's theorem,
If there is an algorithm to decide whether we can use it to decide whether
or not. But this problem has already been proved to be undecidable.
Hence there is no such algorithm to decide or not.
ii.
Let P be any arbitrary Post correspondence system and and are CFg's constructed from the pairs of
strings.
must be a CFL and let G1generates L1. That is,
by De Morgan's theorem, as shown already, any string, represents a solution to the
PCP. Hence, contains all but those strings representing the solution to the PCP.
Let for same CFG G2.
It is now obvious that if and only if the PCP has no solutions, which is already proved to
undecidable. Hence, the question “Is ?" is undecidable.
iii.
Let be a CFG generating the language and G2 be a CFG generating
where and are CFG.s constructed from same arbitrary instance of
iff
iff the PCP instance has no solutions as discussed in part (ii).
Hence the proof.
Theorem : It is undecidable whether an arbitrary CFG is
Proof : Consider an arbitrary instance of PCP and construct the and from the ordered pairs of
CFG's
We construct a new grammar G from and as follows.
where
is same as that of and .
This constructions gives a reduction of PCP to the --------- of whether a CFG is ambiguous, thus leading to
the
undecidability of the given problem. That is, we will now show that the PCP has a solution if and only if G is
Only if Assume that is a solution sequence to this instance of PCP.
Consider the following two derivation in .
But ,
is a solution to the PCP. Hence the same string of terminals has two derivations. Both these
derivations are, clearly, leftmost. Hence G is ambiguous.
If It is important to note that any string of terminals cannot have more than one derivation and
Because, every terminal string which are derivable under these grammars ends with a sequence of
This sequence uniquely determines which productions must be used at every step of the derivation.
Hence, if a terminal string, , has two leftmost derivations, then one of them must begin with the
step.
then continues with derivations under
In both derivations the resulting string must end with a sequence for same The reverse of
this sequence must be a solution to the PCP, because the string that precede in one case
and in the other case. Since the string derived in both cases are identical, the
sequence
must be a solution to the PCP.
Hence the proof
Class p-problem solvable in polynomial time:
Non deterministic polynomial time:
A nondeterministic TM that never makes more than p(n) moves in any sequence of choices for
some
• NP is the set of languags that are accepted by polynomial time NTM’s
• Many problems are in NP but appear not to be in p.
• One of the great mathematical questions of our age: is there anything in NP that is not in
NP-complete problems:
If We cannot resolve the “p=np question, we can at least demonstrate that certain problems in NP
are
• These are called NP-complete.
• Intellectual leverage: Each NP-complete problem’s apparent difficulty reinforces the
belief that they are all hard.
Methods for proving NP-Complete problems:
• Polynomial time reduction (PTR): Take time that is some polynomial in the input size
to
• convert instances of one problem to instances of another.
• If P1 PTR to P2 and P2 is in P1 the so is P1.
• Start by showing every problem in NP has a PTR to Satisfiability of Boolean
formula. Then, more problems can be proven NP complete by showing that SAT
