Turing machine M halts is if it enters a state q for which some transition
function δ( , )
q a
i
i is undefined. Add a new final state z to the Turing machine,
and add all these missing transitions to lead to state z. Now use the assumed
state-entry procedure to test if state z, is ever entered when M is given input w.
This will let us know if the original machine M halts. We conclude that it
should not be possible to build the assumed state-entry procedure.
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 M 1 and M 2 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”.
4.5.4 Post’s Cor re spon dence Prob lem
Let Σ be a finite alphabet, and let A and B be two lists of nonempty strings over
Σ, with | | | |
A B
= , i.e.,
A w w w
w k
= ( , , ,
)
1
2
3 KK
and
B
x x x
x k
= ( , , ,
)
1
2
3 KK
Post’s Cor re spon dence Prob lem is the fol low ing.
Does there exist a sequence of integers i i
i m
1 2
, , KK such that m ≥1 and
w w w
w
i
i
i
im
1 2 3 KK
= x x x
x
i i i
im
1 2 3 KK
?
Example: Suppose A = (a, abaaa, ab) and B = (aaa, ab, b). Then the required
sequence of integers is 2, 1, 1, 3 giving
abaaa a a ab = abaaa aaa b.
This example has a solution. It will turn out that Post’s correspondence
problem is insolvable in general.
Ì Exam ple 4.5.1: Prove that if L 1 is not recursive, and there is a reduction
from L 1 to L 2 , then L 2 is also not recursive.
Solu tion
Assume that L 2 is recursive, as decided by Turing machine M 2 and let T be the
Turing machine that computes the reduction τ.
202
Theory of Automata, Formal Languages and Computation
function δ( , )
q a
i
i is undefined. Add a new final state z to the Turing machine,
and add all these missing transitions to lead to state z. Now use the assumed
state-entry procedure to test if state z, is ever entered when M is given input w.
This will let us know if the original machine M halts. We conclude that it
should not be possible to build the assumed state-entry procedure.
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 M 1 and M 2 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”.
4.5.4 Post’s Cor re spon dence Prob lem
Let Σ be a finite alphabet, and let A and B be two lists of nonempty strings over
Σ, with | | | |
A B
= , i.e.,
A w w w
w k
= ( , , ,
)
1
2
3 KK
and
B
x x x
x k
= ( , , ,
)
1
2
3 KK
Post’s Cor re spon dence Prob lem is the fol low ing.
Does there exist a sequence of integers i i
i m
1 2
, , KK such that m ≥1 and
w w w
w
i
i
i
im
1 2 3 KK
= x x x
x
i i i
im
1 2 3 KK
?
Example: Suppose A = (a, abaaa, ab) and B = (aaa, ab, b). Then the required
sequence of integers is 2, 1, 1, 3 giving
abaaa a a ab = abaaa aaa b.
This example has a solution. It will turn out that Post’s correspondence
problem is insolvable in general.
Ì Exam ple 4.5.1: Prove that if L 1 is not recursive, and there is a reduction
from L 1 to L 2 , then L 2 is also not recursive.
Solu tion
Assume that L 2 is recursive, as decided by Turing machine M 2 and let T be the
Turing machine that computes the reduction τ.
202
Theory of Automata, Formal Languages and Computation