14/09/22 22:56:41.54 UZeuYMIm.net
ゲーデル数 - Wikipedia
ゲーデル数は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。
一般化
計算可能性理論において、「ゲーデル数化」は上述よりさらに一般化した意味を持つ用語として使われる。
1.形式言語の構成要素に自然数を割り当てて、形式言語の構成要素の操作を、数を操作するアルゴリズムでシミュレートできるようにする。
2.より一般化して、枚挙可能な数学的オブジェクトに自然数を割り当てて、その数学的オブジェクトにアルゴリズム的操作ができるようにする。
これは数というよりも文字列を操作する計算模型（チューリングマシンなど）に必須の考え方である。
チューリングマシン - Wikipedia
チューリング機械とは次の7つ組である。
URLﾘﾝｸ(upload.wikimedia.org)
Q は有限集合であり、その元を状態という。
Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
b は Γ の元であり、空白記号とよばれる。
Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
δ は Q × Γ から Q × Γ × {left, right} への写像であり、遷移函数とよばれる。δ(q, a) = (q', a', m) は、
「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
qinit は Q の元であり、初期状態とよばれる。
qacc は Q の元であり、受理状態とよばれる。