哥德爾數

圖靈機 由作用於四個引數的規則集定義：（狀態，紙帶單元顏色，操作，狀態）。設狀態和紙帶單元顏色被編號並由 序數 四元組表示。那麼存在演算法程式，可以按順序列出所有一致的 圖靈機 規則集。如果任何兩個四元組在四個元素中的第一個或第二個元素上不同，則規則集被稱為是一致的。任何這樣的過程都給出了從任何整數到其對應的 圖靈機 的演算法，以及獲得任何一致的 圖靈機 規則集索引的演算法。

假設選擇了一個這樣的過程。如果圖靈機 由索引為 的四元組集定義，則 稱為 的哥德爾數。哥德爾數為 的圖靈機應用於 的結果通常表示為 。

鑑於可計算性和遞迴性的等價性，通常也使用哥德爾數作為 遞迴函式 的索引。可以將哥德爾數分配給 遞迴函式 這一事實意味著存在可數無限個 遞迴函式。因此，根據 康托爾定理，存在非遞迴函式。每個遞迴函式都有無限個不同的哥德爾數。

哥德爾數允許對通用圖靈機 進行直接的形式化定義，如下所示：

(1)

許多 遞迴不可判定 問題是用哥德爾數來表述的。例如，哥德爾數被用於關於 停機問題 的遞迴不可判定性定理中。確定 的收斂性也是 遞迴不可判定 的。

哥德爾數可以用於根據下式唯一編碼任何正整數列表 ：

(2)

其中 是第 個 素數。

當用於研究算術語句時，哥德爾數是給定語句的唯一數字，它可以形成為連續 素數 的 乘積，其指數是對應於組成句子的各個符號的數字。例如，語句 ，讀作“存在一個 使得 是 的直接 後繼”，可以編碼為：

(3)

其中集合 (8, 4, 13, 9, 8, 13, 5, 7, 16, 9) 中的數字對應於組成 的符號。使用哥德爾數的素數冪編碼也可以用於編碼 圖靈機 規則。