Then the Turing machine TM 2 would decide L 1 . But L 1 is undeciable—a
contradiction.
4.6 RICE’S THEOREM
A Turing machine (TM) is a way to describe a language and the decision
problem can be interpreted as belonging to the general class of problems:
“Given a Turing machine, does L(TM) have the property P”?
In this case P is the property of containing the null string.
THE O REM: “If P is a property of languages that is satisfied by some but not
all recursively enumerable languages, then the decision problem.
D: Given a TM, does L(TM) have property P is unsolvable.”
Proof: Assume that P is a nontrivial language property. Starting with Turing
machine TM, an arbitrary instance of Accepts ( ∧). (Which is the other
unsolvable problem), we need to find an instance TM′ of D so that the answer
for TM and TM′ are the same.
The machine TM′ is constructed so that the first things it does it to move its
tape head past the input string and execute TM on input ∧. What TM′ does with
its original input after that depends on the outcome of Accepts (∧).
We would like TM′ to proceed with its original input as if its goal were to
accept some original input as if its goal were to accept some language L A so
that it halts if and only if the original input is in L A . Also we would want TM′ to
proceed as if it were accepted as a different language L.
In order to get everything right, we want L A to be a language satisfying P
and L B to be a language not satisfying P and L B to be a language not satisfying
P. This ensures that if TM′ is a yes-instance of D if and only if TM is a
yes-instance of Accepts (∧).
The problem that exists here is that if TM does not accept ∧, then it will go
into infinite loop. Then TM′ could not accept anything. Therefore L B is an
empty language. Therefore if TM crashed on input ∧, then TM′ also crashes. If
∅ happens to be a language not satisfying the property P, then we have exactly
what we want.
The choice of the language L A is arbitrary subject to the condition L A must
satisfy P; then we have such a language L A , since P is nontrival.
There fore it is proved that if P is any nontrivial prop erty not sat is fied by the
empty lan guage, then D is unsolv able, which proves the Rice’s Theorem. ¨
GLOSSARY
Turing machine: Finite-state machine with storage.
Turing Machines
203
contradiction.
4.6 RICE’S THEOREM
A Turing machine (TM) is a way to describe a language and the decision
problem can be interpreted as belonging to the general class of problems:
“Given a Turing machine, does L(TM) have the property P”?
In this case P is the property of containing the null string.
THE O REM: “If P is a property of languages that is satisfied by some but not
all recursively enumerable languages, then the decision problem.
D: Given a TM, does L(TM) have property P is unsolvable.”
Proof: Assume that P is a nontrivial language property. Starting with Turing
machine TM, an arbitrary instance of Accepts ( ∧). (Which is the other
unsolvable problem), we need to find an instance TM′ of D so that the answer
for TM and TM′ are the same.
The machine TM′ is constructed so that the first things it does it to move its
tape head past the input string and execute TM on input ∧. What TM′ does with
its original input after that depends on the outcome of Accepts (∧).
We would like TM′ to proceed with its original input as if its goal were to
accept some original input as if its goal were to accept some language L A so
that it halts if and only if the original input is in L A . Also we would want TM′ to
proceed as if it were accepted as a different language L.
In order to get everything right, we want L A to be a language satisfying P
and L B to be a language not satisfying P and L B to be a language not satisfying
P. This ensures that if TM′ is a yes-instance of D if and only if TM is a
yes-instance of Accepts (∧).
The problem that exists here is that if TM does not accept ∧, then it will go
into infinite loop. Then TM′ could not accept anything. Therefore L B is an
empty language. Therefore if TM crashed on input ∧, then TM′ also crashes. If
∅ happens to be a language not satisfying the property P, then we have exactly
what we want.
The choice of the language L A is arbitrary subject to the condition L A must
satisfy P; then we have such a language L A , since P is nontrival.
There fore it is proved that if P is any nontrivial prop erty not sat is fied by the
empty lan guage, then D is unsolv able, which proves the Rice’s Theorem. ¨
GLOSSARY
Turing machine: Finite-state machine with storage.
Turing Machines
203