Next:
Strategy for decidability
Up:
Decidability
Previous:
Implications of Theorem 3
Decidability analysis
Strategy for decidability
first principles or reduction
A non-r.e. language:
L
d
definition of
w
i
and
M
j
acceptance table
The language
L
d
is not r.e.
A r.e, non-recursive language:
L
u
The Universal Language
Rice's Theorem
Rice's theorem applies to languages, not to TMs
Post's Correspondence Problem
root
6/10/1998