Next:
Recursively Enumerable Languages
Up:
Decidability Truth
Previous:
Problem instances as strings,
Recursive and Recursively Enumerable Languages
Recursively Enumerable Languages
r.e. languages enumerable by TMs
Enumeration means listing only valid strings
Some r.e. languages have no always-halting TM
TMs always halt for
w
in
L
(
M
)
Recursive Languages
Recursive languages = TMs that always halt
Are All Languages Recursively Enumerable?
Some languages not r.e.
root
6/10/1998
