ゲーデル数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/12/15 14:27 UTC 版)
ゲーデル数（ゲーデルすう、英: Gödel number）は、数理論理学において何らかの形式言語のそれぞれの記号や論理式に一意に割り振られる自然数である。クルト・ゲーデルが不完全性定理の証明に用いたことから、このように呼ばれている。また、ゲーデル数を割り振ることをゲーデル数化（英: Gödel numbering）と呼ぶ。
ゲーデル数のアイデアを暗に使っている例としては、コンピュータにおけるエンコードが挙げられる。 コンピュータでは何でも0と1で表し、「apple」のような文字列も0と1による数字で表す。 ゲーデル数化とは、このように文字列に数字を対応させる事を指す。
ゲーデル数化は、数式におけるシンボルに数を割り当てる符号化の一種でもあり、それによって生成された自然数の列が文字列を表現する。この自然数の列をさらに1つの自然数で表現することもでき、自然数についての形式的算術理論を適用可能となる。
ゲーデルの論文が発表された1931年以来、ゲーデル数はより広範囲な様々な数学的オブジェクトに自然数を割り振るのに使われるようになっていった。
ゲーデルによる符号化
ゲーデルはゲーデル数化を素因数分解に基づいて体系付けた。彼はまず、彼が使っている数式記法で出現する各基本シンボルにユニークな自然数を割り当てた。
シンボルの列である数式全体を符号化するため、ゲーデルは次のような体系を用いた。自然数の列 
