[科普中国]-算数阶层

算术阶层是递归论或可计算性理论中的概念，将自然数的子集按照定义它们的公式的复杂度分类。

定义按公式定义设 为自然数的语言中的公式，定义 为 公式当且仅当 中的所有量词都是有界量词（即形如 或 的量词，其中 为该语言中的项）。

定义 为 公式当且仅当 ，其中 为 ；定义 为 公式当且仅当 ，其中 为 。

更进一步定义 为 公式当且仅当 ，其中 为 公式；定义 为 公式当且仅当 ，其中 为 公式。

设 ；若存在 公式定义 则称 为 集合，若存在 公式定义 则称 为 公式。（若有公式 与集合 ，使 ，则称 定义 。）1

按可计算性定义若集合 可以用图灵机（或任何等价的计算模型）计算得出，则称 为 集合。若 为递归可枚举集合则称 为 集合，若 的补集 递归可枚举则称 为 集合。这一定义实际上与上面给出的定义是等价的。

更高阶层的算术类可以通过波斯特定理与可计算性联系起来：设 为零不可解度的第 次图灵跳跃，则任何集合 是 集合当且仅当 可以用具备 的预言机递归枚举；任何集合是 集合当且仅当其补集满足以上条件。1

举例所有递归集合都是 集合、所有递归可枚举集合都是 集合（逆命题亦成立）。

停机集合（即所有停机的图灵机）是 集合，它在 类中是完全的。

所有有限递归可枚举集合的编号（记作 ）是 -完全集合（因此所有无限递归可枚举集合的编号是 -完全集合）。

所有 -完全集合作为递归可枚举集合的编号是 -完全集合。2

可计算性理论在计算机科学中，可计算性理论（Computability theory）作为计算理论的一个分支，研究在不同的计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，计算复杂性理论考虑一个问题怎样才能被有效的解决。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所