Figure 12.6. Therefore, no algorithm for deciding whether or not L (M) is finite
can exist.
Figure 12.6
Notice that in the proof of Theorem 12.4, the specific nature of the question
asked, namely “Is L (M) finite?”, is immaterial. We can change the nature of the
problem without significantly affecting the argument.
Example 12.4
Show that for an arbitrary Turing machine M with Σ = {a, b}, the problem “L
(M) contains two different strings of the same length” is undecidable.
To show this, we use exactly the same approach as in Theorem 12.4, except
that when reaches a halting configuration, it will be modified to accept the
two strings a and b. For this, the initial input is saved and at the end of the
computation compared with a and b, accepting only these two strings. Thus, if
(M,w) halts, will accept two strings of equal length, otherwise will accept
nothing. The rest of the argument then proceeds as in Theorem 12.4.
In exactly the same manner, we can substitute other questions such as “Does
L (M) contain any string of length five?” or “Is L (M) regular?” without affecting
the argument essentially. These questions, as well as similar questions, are all
undecidable. A general result formalizing this is known as Rice's theorem. This
theorem states that any nontrivial property of a recursively enumerable language
is undecidable. The adjective “nontrivial” refers to a property possessed by some
but not all recursively enumerable languages. A precise statement and a proof of
can exist.
Figure 12.6
Notice that in the proof of Theorem 12.4, the specific nature of the question
asked, namely “Is L (M) finite?”, is immaterial. We can change the nature of the
problem without significantly affecting the argument.
Example 12.4
Show that for an arbitrary Turing machine M with Σ = {a, b}, the problem “L
(M) contains two different strings of the same length” is undecidable.
To show this, we use exactly the same approach as in Theorem 12.4, except
that when reaches a halting configuration, it will be modified to accept the
two strings a and b. For this, the initial input is saved and at the end of the
computation compared with a and b, accepting only these two strings. Thus, if
(M,w) halts, will accept two strings of equal length, otherwise will accept
nothing. The rest of the argument then proceeds as in Theorem 12.4.
In exactly the same manner, we can substitute other questions such as “Does
L (M) contain any string of length five?” or “Is L (M) regular?” without affecting
the argument essentially. These questions, as well as similar questions, are all
undecidable. A general result formalizing this is known as Rice's theorem. This
theorem states that any nontrivial property of a recursively enumerable language
is undecidable. The adjective “nontrivial” refers to a property possessed by some
but not all recursively enumerable languages. A precise statement and a proof of