ゲーデル数化は、形式言語におけるすべての記号、数式、証明に固有の自然数（ゲーデル数）を割り当てる基礎的な手法です。この構文の算術化により、形式体系に関するメタ数学的記述（例：「この数式は証明可能である」）を数値に関する算術的記述として符号化することが可能になり、体系内でその記述について推論することができます。
ゲーデル数
1931
- Kurt Gödel
（画像はイメージです）
ゲーデル数化は、構文（形式言語の記号構造）と数論（整数の性質）の間のギャップを埋める独創的な仕組みです。このプロセスにより、論理に関する記述を数値に関する記述に変換することができます。この方法は、まず形式言語の各基本記号に一意の整数を割り当てることによって機能します（例：¬→1、∨→2、∀→3、x→4など）。
A formula, which is a sequence of these symbols, can then be assigned its own unique number. Gödel’s original method used prime factorization. For a sequence of symbols with numbers [latex]s_1, s_2, …, s_k[/latex], the formula’s Gödel number would be [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], where [latex]p_k[/latex] is the k-th prime number. Due to the fundamental theorem of arithmetic (unique prime factorization), this mapping is injective; every formula gets a unique number, and from any such number, the original formula can be uniquely recovered.
最後に、証明（一連の式）も同様に、構成要素となる式のゲーデル数を取り、素数べき乗符号化を再度適用することで符号化できる。この完全な算術化により、「数列 F は式 P の有効な証明である」といった複雑なメタ数学的性質は、F と P のゲーデル数を含む純粋に算術的な述語となる。これにより、ゲーデルは自身の証明可能性を参照する式を構築することができ、これは彼の不完全性証明における重要なステップとなった。
UNESCO Nomenclature: 1201
純粋数学
タイプ
抽象システム
混乱
実質的な
使用法
概念的／理論的
前駆物質
- 解析幾何学（デカルトによる幾何学から代数学へのマッピング）
- ライプニッツの「普遍的特徴」の概念
- 算術の基本定理（一意素因数分解）
- フレーゲとラッセルによる論理学における言語の形式化
- カントールの集合間の写像に関する研究
アプリケーション
- 計算可能性理論（チューリングマシンとプログラムを数値で表現する理論）
- コンピュータ科学（コードはデータであるという原則）
- 情報理論
- 暗号学
- 形式言語理論
- 停止問題などの決定不能性の証明
特許:
NA
潜在的なイノベーションのアイデア
ボットによるトラフィック（現在1日あたり4万件以上）を排除するため、このコンテンツはコミュニティメンバー限定となっています。
> ログイン < または > 登録 < （100%無料）でこれにアクセスできます。他のすべての制限付きコンテンツとツールも同様です。
関連概念：ゲーデル数、算術化、構文、メタ数学、符号化、形式言語、証明論、計算可能性、自己参照、素因数分解。
歴史的背景
ゲーデル数
（日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。）
