Type 0——递归可枚举语言（无限带 = 图灵机）
顶层的这一档：无限制文法 = Turing machines，配无限长的纸带。这里是一切可计算之物的范围——也是不可判定性的所在之处。
- 文法： 无限制文法（
α → β，任意字符串）。 - 自动机： 图灵机。
- 类别： 递归可枚举（r.e. / 半可判定）——一台机器恰好在其成员上停机接受，但对非成员可能永远运行下去。
- 例子： 停机集
{ ⟨M,x⟩ : M halts on x }；有效的first-order语句（枚举证明）；任意形式系统的定理；{ ⟨p⟩ : the Diophantine equation p has a solution }（MRDP）；{ ⟨M⟩ : M ever prints 0 }。这些都只能确认"是"（semi-decidable）——你可以通过 dovetailing 把成员一个个列出来，但无法判定非成员。
r.e. 与 recursive 的关键分野
Recursive 与 recursively enumerable一个集合是递归的（可判定的），如果某台机器对所有输入都能停机并给出正确的是/否结果。它是r.e. 的，如果某台机器恰好在是的实例上停机。 一个集合是递归的 ⟺ 它和它的补集都是 r.e. 的。
停机集是 r.e. 的，但不是递归的——你可以确认停机（等着看就行），但无法确认不停机。这种不对称就是不可判定性本身（history）。
闭包性质： r.e. 在并、交、连接、星号运算下封闭——但在补运算下不封闭（否则它就会是递归的）。
Rice 定理r.e. 语言的任何非平凡语义性质（关于程序计算的是什么，而非怎么算）都是不可判定的。
所以在 Type 0 这一档，关于行为的事情几乎没有什么是可判定的——这正是为什么you relax（引入证书、容忍度、鲁棒性）才能重新换回一些有用东西的原因。