翻訳と辞書 Words near each other ・ ポスティングシステム ・ ポスティング・システム ・ ポスティング制度 ・ ポスト ・ ポスト (アルバム) ・ ポスト (南アフリカ) ・ ポスト-ハートリー-フォック ・ ポスト-ハートリー-フォック法 ・ ポスト24年組 ・ ポストの中の明日 ・ ポストの定理 ・ ポストアポカリプス ・ ポストイット ・ ポストイナ ・ ポストイナ鍾乳洞 ・ ポストインレー ・ ポストインレー窩洞 ・ ポストゥア ・ ポストゥミア街道 ・ ポストゥムス Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク ポストの定理 ： ウィキペディア日本語版 ポストの定理[ぽすとのていり] ポストの定理（英: Post's theorem）は、計算可能性理論における定理で、算術的階層とチューリング次数の関係を表している。名称はエミール・ポストに因んでいる。 == 背景 == ポストの定理は定義可能性と再帰理論に関連したいくつかの概念を必要とする。この節ではそれら概念の概要を解説する。 算術的階層は、ペアノ算術で定義可能な自然数の集合を階層的に分類するものである。ある論理式が $\backslash Sigma^\_m$ に属するとは、それが冠頭標準形（全ての量化子が先頭にある）の存在量化式で、存在量化と全称量化が $m$ 回交互にあって、それらが量化されていない論理式に適用されている場合である。次のような形式のペアノ算術の言語で書かれた論理式 $\backslash phi(s)$ は $\backslash Sigma^\_m$ 論理式である。 :$\backslash exists\; n\_1\; \backslash forall\; n\_2\; \backslash exists\; n\_3\; \backslash forall\; n\_4\; \backslash cdots\; Q\; n\_m\; \backslash rho(n\_1,\backslash ldots,n\_m,x\_1,\backslash ldots,x\_k)$ ここで ρ は量化子を含まない論理式で、''Q'' は ''m'' が偶数なら $\backslash forall$、''m'' が奇数なら $\backslash exists$ である。次のように $\backslash rho$ が限定量化子のみを含む論理式 :$\backslash left(\backslash exists\; n^1\_1\backslash exists\; n^1\_2\backslash cdots\backslash exists\; n^1\_\backslash right)\backslash left(\backslash forall\; n^2\_1\; \backslash cdots\; \backslash forall\; n^2\_\backslash right)\backslash left(\backslash exists\; n^3\_1\backslash cdots\backslash right)\backslash cdots\backslash left(Q\_1\; n^m\_1\; \backslash cdots\; \backslash right)\backslash rho(n^1\_1,\backslash ldots\; n^m\_,x\_1,\backslash ldots,x\_k)$ は、ペアノ算術の公理により、上記形式と等価である。そのため、$\backslash Sigma^\_m$ 論理式をこの代替形式で定義することも珍しくない。 自然数の集合 ''A'' が $\backslash Sigma^0\_m$ であるとは、それを $\backslash Sigma^0\_m$ 論理式で定義できることを意味し、すなわち、$\backslash Sigma^0\_m$ 論理式 $\backslash phi(s)$ を使って、自然数 ''n'' について $\backslash phi(n)$ が成り立つときのみ、その自然数が ''A'' に含まれる。ある集合が $\backslash Sigma^0\_m$ であるとき、$n\; >\; m$ である任意の ''n'' についての $\backslash Sigma^0\_n$ でもある。ただし、個々の ''m'' について $\backslash Sigma^0\_m$ ではない $\backslash Sigma^0\_$ 集合が存在する。従って、量化子の交代回数は、集合の複雑さの尺度を定義するのに必要である。 ポストの定理では、上で定義したような絶対的な算術的階層だけでなく、相対化された算術的階層も使う。自然数の集合 ''A'' が ''B'' に対して相対的に $\backslash Sigma^0\_m$ であることを $\backslash Sigma^\_m$ と表記する。これは、''B'' のメンバーシップを表す述語を含めた拡張言語で記述された $\backslash Sigma^0\_m$ 論理式で ''A'' を定義可能であることを意味する。 算術的階層が自然数の集合の定義可能性の尺度となる一方、チューリング次数は自然数の集合の計算不可能性のレベルの尺度となる。集合 ''A'' が集合 ''B'' にチューリング還元可能であることを $A\; \backslash leq\_T\; B$ と記述し、''B'' についての神託を与える神託機械によって ''A'' の特性関数を計算できることを意味する。集合 ''A'' のチューリングジャンプは、''A'' に関連する停止性問題の形式である。集合 ''A'' のチューリングジャンプ $A\text{'}$ は、''A'' についての神託機械を持ち ''0'' が入力されたときに停止するチューリング機械のインデックスの集合である。あらゆる集合 ''A'' はそのチューリングジャンプにチューリング還元可能であるが、ある集合のチューリングジャンプは決して元の集合にチューリング還元できない。 ポストの定理は有限回反復されたチューリングジャンプを使用する。任意の自然数の集合 ''A'' について、$A^$ とは ''A'' のチューリングジャンプを ''n'' 回反復したものを表す。従って、$A^$ は ''A'' そのものであり、$A^$ は $A^$ のチューリングジャンプである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ポストの定理」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.