|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 数 ： [すう, かず] 1. (n,n-suf) number 2. figure
ゲーデル数（ゲーデルすう、）は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。クルト・ゲーデルが不完全性定理の証明に用いたことから、このように呼ばれている。また、ゲーデル数を割り振ることをゲーデル数化（）と呼ぶ。 ゲーデル数のアイデアを暗に使っている例としては、コンピュータにおけるエンコードが挙げられる。 コンピュータでは何でも0と1で表し、「apple」のような文字列も0と1による数字で表す。 ゲーデル数化とは、このように文字列に数字を対応させる事を指す。 ゲーデル数化は、数式におけるシンボルに数を割り当てる符号化の一種でもあり、それによって生成された自然数の列が文字列を表現する。この自然数の列をさらに1つの自然数で表現することもでき、自然数についての形式的算術理論を適用可能となる。 ゲーデルの論文が発表された1931年以来、ゲーデル数はより広範囲な様々な数学的オブジェクトに自然数を割り振るのに使われるようになっていった。 == ゲーデルによる符号化 == ゲーデルはゲーデル数化を素因数分解に基づいて体系付けた。彼はまず、彼が使っている数式記法で出現する各基本シンボルにユニークな自然数を割り当てた。 シンボルの列である数式全体を符号化するため、ゲーデルは次のような体系を用いた。自然数の列 があるとき、ゲーデルによるその数列の符号化とは、小さいほうから ''n'' 個の素数を数列の各数値でべき乗したものの積となる。 : 算術の基本定理によれば、このようにして得られた値の素因数分解は一意に定まる。従って、ゲーデル数から元の数列を効率的に復元可能である。 ゲーデルはこの手法を2つのレベルで使った。第一に数式を構成するシンボル列を符号化するのに用い、第二に証明を表している数式列の符号化に用いた。これによって彼は、自然数に関する文と自然数の定理の立証性に関する文の間で対応を示した。 数列のゲーデル数化（Gödel numbering for sequences）には、より洗練され簡潔な方法が存在する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ゲーデル数」の詳細全文を読む スポンサード リンク
|