Next:
problems with recursive languages
Up:
Decidability Truth
Previous:
Some languages not r.e.
Decidability
problems with recursive languages decidable
Trivial Decidability
one string = recursive language
Decidable Doesn't Mean Solved
e.g.
Fermat's conjecture
decidable doesn't mean we know how to solve it
Decidability Theorems
Theorem 1
The complement of a recursive language is recursive
Theorem 2
The union of two recursive languages is recursive
Theorem 3
If a language and it's complement are r.e, they are both recursive
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
