計算不可能なK自明集合の構成の概略
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/02/03 07:15 UTC 版)
「K自明集合」の記事における「計算不可能なK自明集合の構成の概略」の解説
実は、その集合はpromptly simpleに取ることもできる。証明のアイディアはprompt simple集合を作る際の要求 つまり、xが増えるにしたがって、sがステージを走るときのxのコストの上限が0に収束する。例えば、標準コスト関数はこの性質を満たす。構成の本質的なアイディアとしては、prompt simple集合を作る要求を満たすために、Aに数字を入れる前に、コストが十分小さくなるまで待つというものである。計算可能な枚挙を以下のように定義しよう。まず、。ステージにおいては、それぞれのにおいて、もし、が満たされておらず、かつを満たすようなが存在するなら、 xをに入れて、要求が満たされたと宣言する。構成は以上である。 この構成が実際にうまくいくことを確認しよう。まず、Aはコスト関数に従う。なぜなら、それぞれの要求があるのでAに入る数字は高々1つであって、合計Sは高々 であるからである。次に、それぞれの要求は満たされる。もし、が無限ならば、コスト関数が極限条件を満たすという事実から、ある数字がやがてはAに入り、要求が満たされるからである。
※この「計算不可能なK自明集合の構成の概略」の解説は、「K自明集合」の解説の一部です。
「計算不可能なK自明集合の構成の概略」を含む「K自明集合」の記事については、「K自明集合」の概要を参照ください。
ウィキペディア小見出し辞書の「計算不可能なK自明集合の構成の概略」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算不可能なK自明集合の構成の概略のページへのリンク
