Chapter 10: Decidability and Recursively Enumerable Languages ~ 315
Note: If A is reducible to Band B is decidable then A is decidable. If A is
reducible to B and A is undecidable. then B is undecidable.
Theorem 10.6 HALT rM = {(M, w) IThe Turing machine M halts on input
11'} is undecidable.
Proof We assume that HALT TM is decidable, and get a contradiction. Let Mj
be the TM such that T(M I ) = HALT rM and let M I halt eventually on aU
(M, w). We construct a TM M 2 as follows:
1. For M 2 , (M, w) is an input.
2. The TM M I acts on (M, w).
3. If M I rejects (M, w) then M 2 rejects (M, ,v).
4. If M I accepts (M, w), simulate the TM M on the input string w until
M halts.
5. If M has accepted w, M 2 accepts (M, w); otherwise M 2 rejects (M, w).
When M I accepts (M, iV) (in step 4), the Turing machine M halts on w.
In this case either an accepting state q or a state q' such that D(q', a) is
undefined tiU some symbol a in w is reached. In the first case (the first
alternative of step 5) M 2 accepts (M. w). In the second case (the second
alternative of step 5) M 2 rejects (M, w).
It follows from the definition of M 2 that M 2 halts eventually.
Also,
T(M 2 ) = {(M, vv) IThe Turing machine accepts w}
= A TM
This is a contradiction since An.1 is undecidable.
10.6 THE POST CORRESPONDENCE PROBLEM
The Post Correspondence Problem (PCP) was first introduced by Emil Post
in 1946. Later, the problem was found to have many applications in the theory
of formal languages. The problem over an alphabet 2: belongs to a class of
yes/no problems and is stated as foUows: Consider the two lists x =(Xl' .. X n ),
Y = (YI ... Yn) of nonempty strings over an alphabet 2: = {O, 1}. The PCP
is to determine whether or not there exist i lo ..• , i m , where 1 S ii S n, such
that
Note: The indices i j ' s need not be distinct and m may be greater than n.
Also, if there exists a solution to PCP, there exist infinitely many solutions.
EXAMPLE 10.1
Does the PCP with two lists x = (b, bab
3
, ba) and v = (b
3
, ba, a) have a
solution?
Note: If A is reducible to Band B is decidable then A is decidable. If A is
reducible to B and A is undecidable. then B is undecidable.
Theorem 10.6 HALT rM = {(M, w) IThe Turing machine M halts on input
11'} is undecidable.
Proof We assume that HALT TM is decidable, and get a contradiction. Let Mj
be the TM such that T(M I ) = HALT rM and let M I halt eventually on aU
(M, w). We construct a TM M 2 as follows:
1. For M 2 , (M, w) is an input.
2. The TM M I acts on (M, w).
3. If M I rejects (M, w) then M 2 rejects (M, ,v).
4. If M I accepts (M, w), simulate the TM M on the input string w until
M halts.
5. If M has accepted w, M 2 accepts (M, w); otherwise M 2 rejects (M, w).
When M I accepts (M, iV) (in step 4), the Turing machine M halts on w.
In this case either an accepting state q or a state q' such that D(q', a) is
undefined tiU some symbol a in w is reached. In the first case (the first
alternative of step 5) M 2 accepts (M. w). In the second case (the second
alternative of step 5) M 2 rejects (M, w).
It follows from the definition of M 2 that M 2 halts eventually.
Also,
T(M 2 ) = {(M, vv) IThe Turing machine accepts w}
= A TM
This is a contradiction since An.1 is undecidable.
10.6 THE POST CORRESPONDENCE PROBLEM
The Post Correspondence Problem (PCP) was first introduced by Emil Post
in 1946. Later, the problem was found to have many applications in the theory
of formal languages. The problem over an alphabet 2: belongs to a class of
yes/no problems and is stated as foUows: Consider the two lists x =(Xl' .. X n ),
Y = (YI ... Yn) of nonempty strings over an alphabet 2: = {O, 1}. The PCP
is to determine whether or not there exist i lo ..• , i m , where 1 S ii S n, such
that
Note: The indices i j ' s need not be distinct and m may be greater than n.
Also, if there exists a solution to PCP, there exist infinitely many solutions.
EXAMPLE 10.1
Does the PCP with two lists x = (b, bab
3
, ba) and v = (b
3
, ba, a) have a
solution?