Section: Turing Machines

def. Language is recursively enumerable iff there exists a TM such that .

→ The class of languages that TMs can represent is a recursively enumerable language. You can think of languages which are “countable.”

def. Language is recursive iff there exists a TM which, for every string in , it halts.

→ Recursive Languages are languages in which a TM always halts.

  • Distinction between RE and R languages. Untitled

lemma. If is a countable set, then [= the set of all subsets of ] may not be countable.

thm. There exists languages over alphabet that are not recursively enumerable. (proof using lemma.)

thm. If is recursively enumerable, may not be RE.

thm. If and are both RE, then and is Recursive.

thm. If is recursive, is recursive.