ゲーデル数（読み）ゲーデルすう（英語表記）Gödel number

改訂新版　世界大百科事典

ゲーデル数 (ゲーデルすう)
Gödel number

数学の形式的体系における対象の項，式，命題，証明は，いずれも，あらかじめ用意されている可算個の変数，いくつかの定数，述語，論理記号から体系固有の規則によって構成される記号の有限系列である。したがって，これらの対象の全体は可算集合であるから，おのおのの対象に一意のしかたで，しかもその構造を完全に反映するように，自然数を対応させることができる。この対応を用いて，形式的体系の超数学的命題を自然数論の命題として翻訳できる。これを形式的体系の算術化という。このような手法を初めて導入したのはK.ゲーデルであって，各対象に対応させる自然数をゲーデル数という。ゲーデルはこれを用いて不完全性定理を得た。
執筆者：柘植 利之

出典　株式会社平凡社「改訂新版　世界大百科事典」

世界大百科事典（旧版）内のゲーデル数の言及

【計算可能性】より

…このように拡張された関数を計算可能部分関数という。　プログラムをコンピューター内部のデータとして表現するというプログラム内蔵方式のコンピューターの原理も，計算可能性に関係する重要な概念である符号化(ゲーデル数化ともいう)と密接な関係にある。プログラムが0，1のビット列で表現できるのと同様に，計算可能部分関数もすべて自然数で表現することができる。…

※「ゲーデル数」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」