翻訳と辞書
Words near each other
・ ポスティングシステム
・ ポスティング・システム
・ ポスティング制度
・ ポスト
・ ポスト (アルバム)
・ ポスト (南アフリカ)
・ ポスト-ハートリー-フォック
・ ポスト-ハートリー-フォック法
・ ポスト24年組
・ ポストの中の明日
ポストの定理
・ ポストアポカリプス
・ ポストイット
・ ポストイナ
・ ポストイナ鍾乳洞
・ ポストインレー
・ ポストインレー窩洞
・ ポストゥア
・ ポストゥミア街道
・ ポストゥムス


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

ポストの定理 : ウィキペディア日本語版
ポストの定理[ぽすとのていり]
ポストの定理: Post's theorem)は、計算可能性理論における定理で、算術的階層チューリング次数の関係を表している。名称はエミール・ポストに因んでいる。
== 背景 ==
ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。
算術的階層は、ペアノ算術で定義可能な自然数の集合を階層的に分類するものである。ある論理式\Sigma^_m に属するとは、それが冠頭標準形(全ての量化子が先頭にある)の存在量化式で、存在量化と全称量化m 回交互にあって、それらが量化されていない論理式に適用されている場合である。次のような形式のペアノ算術の言語で書かれた論理式 \phi(s)\Sigma^_m 論理式である。
:\exists n_1 \forall n_2 \exists n_3 \forall n_4 \cdots Q n_m \rho(n_1,\ldots,n_m,x_1,\ldots,x_k)
ここで ρ は量化子を含まない論理式で、''Q'' は ''m'' が偶数なら \forall、''m'' が奇数なら \exists である。次のように \rho限定量化子のみを含む論理式
:\left(\exists n^1_1\exists n^1_2\cdots\exists n^1_\right)\left(\forall n^2_1 \cdots \forall n^2_\right)\left(\exists n^3_1\cdots\right)\cdots\left(Q_1 n^m_1 \cdots \right)\rho(n^1_1,\ldots n^m_,x_1,\ldots,x_k)
は、ペアノ算術の公理により、上記形式と等価である。そのため、\Sigma^_m 論理式をこの代替形式で定義することも珍しくない。
自然数の集合 ''A'' が \Sigma^0_m であるとは、それを \Sigma^0_m 論理式で定義できることを意味し、すなわち、\Sigma^0_m 論理式 \phi(s) を使って、自然数 ''n'' について \phi(n) が成り立つときのみ、その自然数が ''A'' に含まれる。ある集合が \Sigma^0_m であるとき、n > m である任意の ''n'' についての \Sigma^0_n でもある。ただし、個々の ''m'' について \Sigma^0_m ではない \Sigma^0_ 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。
ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 ''A'' が ''B'' に対して相対的に \Sigma^0_m であることを \Sigma^_m と表記する。これは、''B'' のメンバーシップを表す述語を含めた拡張言語で記述された \Sigma^0_m 論理式で ''A'' を定義可能であることを意味する。
算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数は自然数の集合の計算不可能性のレベルの尺度となる。集合 ''A'' が集合 ''B'' にチューリング還元可能であることを A \leq_T B と記述し、''B'' についての神託を与える神託機械によって ''A'' の特性関数を計算できることを意味する。集合 ''A'' のチューリングジャンプは、''A'' に関連する停止性問題の形式である。集合 ''A'' のチューリングジャンプ A' は、''A'' についての神託機械を持ち ''0'' が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 ''A'' はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。
ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 ''A'' について、A^ とは ''A'' のチューリングジャンプを ''n'' 回反復したものを表す。従って、A^ は ''A'' そのものであり、A^A^ のチューリングジャンプである。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「ポストの定理」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.