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