ポストの問題と優先度法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 05:45 UTC 版)
「チューリング次数」の記事における「ポストの問題と優先度法」の解説
エミール・ポストは r.e.チューリング次数を研究し、0 と 0′の厳密に中間であるような r.e.次数は存在するか、と問うた。このような次数を構成する問題（または、それが不可能であることの証明）はポストの問題として知られるようになった。この問題は1950年代に Friedberg と Muchnik によって独立に解決され、そのような中間の r.e.次数が実在することが示された。彼らの証明方法は、r.e.次数を構成するための同じ新技法をそれぞれが導入したもので、これは優先度法として知られるようになった。今日、優先度法は r.e.集合について何らかの結果を得る際には主役となるテクニックである。 r.e.集合 X {\displaystyle X} を構成する上で、優先度法のアイディアは、 X {\displaystyle X} が満たさねばならない可算個の「要件」の列を作るというものである。例えば、0 と 0′の中間である r.e.集合を作るには、全ての自然数 e {\displaystyle e} について要件 A e {\displaystyle A_{e}} と B e {\displaystyle B_{e}} を満たせば十分である。ここで、 A e {\displaystyle A_{e}} はインデクス e {\displaystyle e} が指す神託機械が X {\displaystyle X} から 0′ を計算できないという要件であり、 B e {\displaystyle B_{e}} はインデクス e {\displaystyle e} が指す（オラクルを持たない）チューリングマシンが X {\displaystyle X} を計算できないという要件である。これらの要件は「優先順序」（要件と自然数との間の明示的な全単射）に従って並べられる。証明は個々の自然数毎に一つずつの「段階」を踏んで帰納法的に進む。ここでいう段階とは、 X {\displaystyle X} の内容を枚挙する過程だと思えばよい。個々の段階では、何らかの数を X {\displaystyle X} に加えるか、又は X {\displaystyle X} に加えることを恒久的に禁止して、「要件」を満足させていく（つまり X {\displaystyle X} の全てが枚挙されたなら全ての要件が成り立つように強いる）。時として、ある数を X {\displaystyle X} に加えると、一つの要件が満たされる代わりにそれまで満たされていた別の要件が満たされなくなる（「傷付けられる」と言う）ことが起きる。この場合は要件の優先順序を用いてどの要件を満たすべきかを決定する。大まかなアイディアとしては、もし何らかの要件が傷付けられるなら、それより優先度が高い他の要件が何れ全て傷付けられなくなれば、最終的には傷付けられなくなるだろう、ということである。とはいえ全ての優先度論法がこのような性質を持つ訳ではない。出来上がった集合 X {\displaystyle X} が r.e.であり全ての要件を満たすことを論証する必要がある。優先度論法は r.e.集合に関する様々な証明に使える。所期の集合を生成するには、要件とその満たし方を注意深く選ばねばならない。
※この「ポストの問題と優先度法」の解説は、「チューリング次数」の解説の一部です。
「ポストの問題と優先度法」を含む「チューリング次数」の記事については、「チューリング次数」の概要を参照ください。
- ポストの問題と優先度法のページへのリンク
