哥德尔数

图灵机 由作用于四个参数的规则集定义：（状态，纸带单元颜色，操作，状态）。设状态和纸带单元颜色被编号并由 序数 四元组表示。那么存在算法程序，可以按顺序列出所有一致的 图灵机 规则集。如果任何两个四元组在四个元素中的第一个或第二个元素上不同，则规则集被称为是一致的。任何这样的过程都给出了从任何整数到其对应的 图灵机 的算法，以及获得任何一致的 图灵机 规则集索引的算法。

假设选择了一个这样的过程。如果图灵机 由索引为 的四元组集定义，则 称为 的哥德尔数。哥德尔数为 的图灵机应用于 的结果通常表示为 。

鉴于可计算性和递归性的等价性，通常也使用哥德尔数作为 递归函数 的索引。可以将哥德尔数分配给 递归函数 这一事实意味着存在可数无限个 递归函数。因此，根据 康托尔定理，存在非递归函数。每个递归函数都有无限个不同的哥德尔数。

哥德尔数允许对通用图灵机 进行直接的形式化定义，如下所示：

(1)

许多 递归不可判定 问题是用哥德尔数来表述的。例如，哥德尔数被用于关于 停机问题 的递归不可判定性定理中。确定 的收敛性也是 递归不可判定 的。

哥德尔数可以用于根据下式唯一编码任何正整数列表 ：

(2)

其中 是第 个 素数。

当用于研究算术语句时，哥德尔数是给定语句的唯一数字，它可以形成为连续 素数 的 乘积，其指数是对应于组成句子的各个符号的数字。例如，语句 ，读作“存在一个 使得 是 的直接 后继”，可以编码为：

(3)

其中集合 (8, 4, 13, 9, 8, 13, 5, 7, 16, 9) 中的数字对应于组成 的符号。使用哥德尔数的素数幂编码也可以用于编码 图灵机 规则。