Type 0 — recursively enumerable (unbounded tape = Turing)
Parent: chomsky-hierarchy
The top tier: unrestricted grammars = Turing machines, with unbounded tape. This is everything computable — and where undecidability lives.
- Grammar: unrestricted (
α → β, any strings). - Automaton: the Turing machine.
- Class: recursively enumerable (r.e. / semi-decidable) — a machine that halts-and-accepts exactly on the members, but may run forever on non-members.
- Examples: the halting set
{ ⟨M,x⟩ : M halts on x }; the valid first-order sentences (enumerate proofs); the theorems of any formal system;{ ⟨p⟩ : the Diophantine equation p has a solution }(MRDP);{ ⟨M⟩ : M ever prints 0 }. All are confirm-yes-only (semi-decidable) — you list members by dovetailing, but can't decide non-members.
r.e. vs recursive (the crucial split)
Recursive vs recursively enumerableA set is recursive (decidable) if some machine halts on all inputs with the right yes/no. It is r.e. if some machine halts exactly on the yes-instances. A set is recursive ⟺ both it and its complement are r.e.
The halting set is r.e. but not recursive — you can confirm halting (wait and see) but not non-halting. That asymmetry is undecidability (history).
Closure: r.e. is closed under union, intersection, concatenation, star — but not complement (else it'd be recursive).
Rice's theoremEvery non-trivial semantic property of r.e. languages (of what a program computes, not how) is undecidable.
So at Type 0 almost nothing about behaviour is decidable — the reason you relax (certificates, tolerance, robustness) to get anything useful back.