设 为自然数的
语言中的公式，定义 为 公式当且仅当 中的所有量词都是有界量词（即形如 或 的量词，其中 为该语言中的项）。
若集合 可以用
图灵机（或任何等价的
计算模型）计算得出，则称 为 集合。若 为
递归可枚举集合则称 为 集合，若 的补集 递归可枚举则称 为 集合。这一定义实际上与上面给出的定义是等价的。
更高阶层的算术类可以通过波斯特定理与可计算性联系起来：设 为零
不可解度的第 次图灵跳跃，则任何集合 是 集合当且仅当 可以用具备 的
预言机递归枚举；任何集合是 集合当且仅当其补集满足以上条件。
停机集合（即所有停机的图灵机）是 集合，它在 类中是
完全的。
在
计算机科学中，可计算性理论（Computability theory）作为
计算理论的一个分支，研究在不同的
计算模型下哪些算法问题能够被解决。相对应的，计算理论的另一块主要内容，
计算复杂性理论考虑一个问题怎样才能被有效的解决。