Transcript C SC 473 Notes

Automata, Grammars and Languages
Discourse 08
Rice’s Theorem
C SC 473 Automata, Grammars and Languages
Predicates, Properties and Sets
• predicate, n. 1. Logic. That which is predicated or said of
the subject in a proposition; the second term of a
proposition, which is affirmed or denied of the first term by
means of the copula, as in ‘paper is white’, ‘ink is not
white’. 2. a. Gram. The statement made about a subject,
including the logical copula (`is’, `are’, etc.). b. Math. An
assertion or propositional function. c. Synonyms:
`assertion’, `proposition’
• Mathematically: a function which returns a truth-value
(true or false). If the function P returns `true’ for an
argument x, this indicates the property holds for that x:
P( L)  L is empty P( )   is total P(n)  n is prime
• Predicates can be about objects of any universe:
P(G)  G is context-free P( M )  M halts for all inputs
P( x)  x is rational P( y)  y is green
C SC 473 Automata, Grammars and Languages
2
Predicates, Properties and Sets
• property: the quality or attribute that is asserted to hold by a
predicate, as in `whiteness (or white) is a property of paper’,
`blackness (or black) is a property of ink’. Used
synonymously with quality or attribute.
• A property of Turing-recognizable sets is defined by a
predicate on Turing-recognizable sets.

example: the property of “emptiness” for a language is defined
by the predicate P (L )  [ L = ].
C SC 473 Automata, Grammars and Languages
3
Rice’s Theorem
• A machine tool for proving problems undecidable
• Any property of TMs that can be expressed as a property
of languages [a machine independent property] is
undecidable—except trivial properties.



Trivial property: a property true for all Turing-recognizable sets, or
for none.
Michine independent properties:
 “the language accepted by M is a regular set.”
 P ( L )  L is finite
Machine dependent properties
 " M started with  eventually writes a non-blank symbol on its tape"

" M started on w never shifts left"
C SC 473 Automata, Grammars and Languages
4
Rice’s Theorem (cont.)
• Theorem (Rice’s Theorem). The language
LP  { M | L(M ) has property P} is decidable iff P is a
trivial property. (Hence no non-trivial property of the
Turing-recognizable sets can be decided.)
Proof: (). If P is true for all TMs M, then
LP  { M | M is a TM} is decidable. If P is false for all
TMs then LP   is decidable.
(  ). (contrapositive). Assume that P is non-trivial.
Without loss of generality, we can assume that
P()  false.
[ For if not, we can use the property
 P and show that the complementary language
LP  { M | L(M ) has property P} is undecidable.]
C SC 473 Automata, Grammars and Languages
5
Rice’s Theorem (cont.)
• Since property P is non-trivial, there is some recognizable
language B with P( B)  true. Our goal is to reduce
ATM to LP .
To prove ATM m LP we assume there
is a decider M P for LP , and from it plus a reduction
function, construct a decider for ATM .
What is decider M P good at? Given an input M
it can tell whether M has property P or not. Our reduction
function (“program translator”) will transform a pair M , w
to a program C M , w
having “dual” behavior: if M
accepts w then C M , w behaves like an acceptor M B
for B; otherwise it behaves like an acceptor for . Since B
has the property P while  does not, the decider M P will
say “yes” iff M accepts w.
C SC 473 Automata, Grammars and Languages
6
Rice’s Theorem (cont.)
Construct from input M , w a transformed program
C ( M , w ) so that the following holds:
 B if w  L( M )  P( B)  true
(*) L(C ( M , w ))  
 if w  L( M )  P()  false
Here is what the “translator” C constructs:
x
C( M , w ) :
M
w
MB
U
yes
yes
start
Note: if w  L( M ) then: L(C ( M , w ))  L(M B )  B.
if w  L( M e ) then : L(C( M , w ))  
So (*) holds as desired. With this reduction function, we
proceed to the reduction itself.
C SC 473 Automata, Grammars and Languages
7
Rice’s Theorem (Cont.)
Reduction: Suppose there is a decider M P for P
N:
M,w
C
C( M , w )
yes
MP
no
yes
no
M , w  L( N )  C ( M , w )  L( M P )  C ( M , w )  LP
 P( L(C ( M , w )))  true  L(C ( M , w ))  B  w  L( M )
 L( N )  ATM & ATM m LP .
Since the language
be undecidable. 
C SC 473 Automata, Grammars and Languages
ATM
is undecidable, so must
LP
8
Rice’s Theorem (Cont.)
• Corollary: Given a TM M the following properties of the
language L(M) are all undecidable:
• Is L(M) empty?
• Is L(M) finite?
• Is L(M) regular?
• Is L(M) a CFL?
• Is the string foo  L(M) ?
• Does L(M) have more than 3 members?
• Does L(M) have fewer than 10 members?
• …
C SC 473 Automata, Grammars and Languages
9
Machine-Dependent Problems
• Not all problems about TM-recognizable sets can be
settled by Rice’s Theorem
• Rice’s Theorem only applies to properties of languages
recognized
• Properties of the TM itself might be decidable or
undeciable—the approach has to be ad hoc.
• Ex: Given a TM M, does it have an even number of
states? Easily decidable
• Ex: Given TM M,q. Is there any configuration with p  q
yielding a configuration with state q? Decidable. If there
is a transition in  of form (p,a) = (q,-,-), pq, then yes
else no. (We do not require any of these configurations to
be reachable from the initial configuration.)
C SC 473 Automata, Grammars and Languages
10
Machine-Dependent Problems
• Ex: Undecidable Machine-Dependent Problem 111TM
• Predicate: Given TM M with ={0,1,blank}, does it ever
print 3 consequtive 1’s on its tape (for any input).
• Reduction: ETTM m 111TM reduction func. in 2 stages.
M
C1
M
C2
M 
M  uses 01 for 0 and 10 for 1, making changes in the
rules accordingly. When M has a 0 in cell j then M  has
a 0 in cell 2j and a 1 in cell 2j+1 (never a 111 on tape)
• C2 modifies M  so that if M  accepts, M  prints 111
and halts in the accept state.
• M  prints 111  M  accepts   M accepts  
•
C SC 473 Automata, Grammars and Languages
11