ゲーデル数化

数理論理学において、ゲーデル数とは、ある形式言語の各記号および整形式論理式に、ゲーデル数と呼ばれる一意の自然数を割り当てる関数である。クルト・ゲーデルは、自身の不完全性定理の証明のためにこの概念を開発した。^{[ 1 ]： 173-198}

ゲーデル数化は、数学記号の各記号に数値を割り当てる符号化方式と解釈でき、その後、自然数の列で記号の列を表すことができる。これらの自然数の列は、さらに単一の自然数で表すことができ、形式的な算術理論における操作を容易にする。

1931年にゲーデルの論文が発表されて以来、「ゲーデル数」または「ゲーデル符号」という用語は、数学的対象に自然数を割り当てるより一般的な方法を指すために用いられてきた。

ゲーデルは、体系内の各命題は自然数（ゲーデル数）で表すことができると指摘した。このことの意義は、命題の真偽といった性質が、そのゲーデル数が特定の性質を持つかどうかを判断することと同等であるという点にある。関係する数は非常に大きくなる可能性があるが、それは障害にはならない。重要なのは、そのような数を構成できるということである。

簡単に言うと、ゲーデルは、システム内で定式化できるすべての数式や命題に一意の番号を割り当てる方法を考案しました。これにより、数式とゲーデル数を機械的に相互変換できるようになります。これには多くの方法があります。簡単な例としては、英語がASCIIを使用してコンピュータで数値のシーケンスとして格納される方法があります。ASCIIコードは0から127の範囲なので、3桁の10進数にパディングしてから連結すれば十分です。

• 「foxy」という単語は102 111 120 121。
• 論理式x=y => y=xは次のように表されます。120 061 121 032 061 062 032 121 061 120。

ゲーデルは素因数分解に基づく体系を用いた。彼はまず、自身が扱っていた算術の形式言語における各基本記号に、固有の自然数を割り当てた。

記号の列である数式全体を符号化するために、ゲーデルは次のシステムを使用した。${\displaystyle (x_{1},x_{2},x_{3},...,x_{n})}$正の整数の列のゲーデル符号化は、最初のn個の素数を、その列における対応する値に累乗した積である。

${\displaystyle \mathrm {enc} (x_{1},x_{2},x_{3},\dots ,x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdots p_{n}^{x_{n}}.}$

算術の基本定理によれば、任意の数（特に、この方法で得られた数）は一意に素因数分解できるため、（符号化する記号の数nが与えられた場合）ゲーデル数から元の数列を復元することが可能です。

ゲーデルはこの方式を特に2つのレベルで使用した。1つ目は、数式を表す記号の列を符号化するため、2つ目は、証明を表す数式の列を符号化するためである。これにより、自然数に関する記述と、自然数に関する定理の証明可能性に関する記述との間の対応関係を示すことができた。これが証明の重要な観察である（ゲーデル 1931）。

数列のゲーデル番号付けを構築するには、より洗練された（そしてより簡潔な）方法があります。

無限に多くの異なるゲーデル数体系が可能である。例えば、K個の基本記号があると仮定すると、この記号の集合を（例えば、可逆関数hを介して）全単射な基数Kの数字体系の桁の集合に可逆的にマッピングすることによって、別のゲーデル数体系を構築することができる。n個の記号の列からなる式$s_1s_2s_3\dots s_n$すると、その番号にマッピングされます

${\displaystyle h(s_{1})\times K^{n-1}+h(s_{2})\times K^{n-2}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.}$

K を 10 のべき乗に選ぶと、この方式では、10 進数で表されたゲーデル数は単に次の文字列の連結であるため、人間が記号列とそのゲーデル数の間を簡単に変換できます。${\displaystyle n}$小数点${\displaystyle h(s_{i})}$。

例えば、ここで説明する番号付けでは、K=1000となります。^{[ ii ]}

計算可能性理論において、「ゲーデル数化」という用語は、上記で説明したよりも一般的な設定で使用されます。それは以下を指す場合があります。

1. 形式言語の要素を自然数に割り当てることで、アルゴリズムによってその自然数を操作し、形式言語の要素の操作をシミュレートできるようにする。
2. より一般的には、可算群などの可算な数学的対象の要素を自然数に割り当てることで、その数学的対象をアルゴリズム的に操作できるようにすることである。

また、割り当てられた「数値」が実際には文字列である場合にも、ゲーデル数という用語が用いられることがあります。これは、数値ではなく文字列を操作するチューリングマシンなどの計算モデルを考察する際に必要となります。

ゲーデル集合は、集合論において数式を符号化するために用いられることがあり、ゲーデル数と似ていますが、符号化に数ではなく集合を用いる点が異なります。単純な場合、遺伝的に有限な集合を用いて数式を符号化することは、本質的にゲーデル数を用いるのと同等ですが、数式のツリー構造を集合のツリー構造でモデル化できるため、定義がやや容易になります。ゲーデル集合は、無限言語における数式の符号化にも用いることができます。

• 教会の暗号化
• 説明番号
• 数列のゲーデル番号付け
• ゲーデルの不完全性定理
• チャイティンの不完全性定理

• ネーゲル、アーネスト；ニューマン、ジェームズ・R. (1959)。ゲーデルの証明。

• ホフスタッター、ダグラス（1979）。ゲーデル、エッシャー、バッハ：永遠の黄金の鎖。ベーシックブックス。ISBN 978-0-465-02656-2。代替のゲーデル数化を定義し、使用する。
• ホフスタッター、ダグラス（2007）。『私は奇妙なループ』。ベーシックブックス。ISBN 978-0-465-03078-1。ゲーデルの数化の歴史も含まれています。
• ヘマン、ジェイソン；ホルク、エリック（2013年6月15日）「チューリング・タールピットの可視化」（PDF）。第1回ACM SIGPLANワークショップ「機能的アート、音楽、モデリング、デザイン」議事録。71 ～ 76ページ。doi ： 10.1145 /2505341.2505348。ISBN  978-1-4503-2386-42016年9月27日にオリジナル（PDF）からアーカイブされました。プログラムの符号化にゲーデル数を用いる。