Recursively enumerable languages

The recursively enumerable (type-0) languages — the most general class, those a machine can semi-decide (accept exactly the members, possibly running forever otherwise).

• Grammars. Unrestricted grammars: rules α → β of arbitrary shape, where α contains at least one nonterminal.
• Automata. Turing machines (is_RE).

---

Table of contents

• TM equivalence
• Search procedures
• Closure properties