決定可能性の問題

ウィキペディア小見出し辞書

決定可能性の問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/08 15:15 UTC 版)

「μ再帰関数」の記事における「決定可能性の問題」の解説

ここである疑問が生じる。ここで説明されている計算のアルゴリズムは停止しないのか、である。ここでは「計算不能」な関数を扱っているのだろうか。計算可能かどうかはどうやって決定されるのか。クリーネは以下のように記している。 まず、以下のような「効率的に決定可能な述語」について考える。 εyR(x,y) = IF (Ey)R(x,y) THEN ε ="least y such that R(x,y)" ELSE 0. クリーネは次のように提案している。「命題 R(x,0), R(x,1), R(x,2), ... を順に調べていき、真であるものを探す。我々が満足するまで… 「しかし、もし NOT_(Ey)R(x,y) であるような x であれば、探索は際限なく続き何も得られないだろう。アレフ0 の全命題の評価を完了することは人間計算機には不可能である。 「 だがそれにもかかわらず、R(x,y) をうまく選択すれば、εyR(x,y) を効率的に計算可能かもしれない…何らかの効率的な手続きをとれば。 「したがって、述語 (Ey)R(x,y) を効率的に決定可能である場合のみ、関数 εyR(x,y) を効率的に計算可能である」（Kleene pp. 317-318） そこで、我々の採用しているアルゴリズムが「決定可能」かどうかをどうやって判断すればよいだろうか。「停止判定」アルゴリズムを使って停止するかどうかを調べられるだろうか。そのような判定が不可能であるという証明は非常に複雑である。重要な点は、クリーネが全ての全域再帰関数をゲーデル数によって数え上げ、カントールの対角線論法を使って、それ以上の再帰関数が定義可能であることを示したことである。 結論から言えば、μ再帰関数の停止判定はμ再帰関数の体系では不可能であり、これはチャーチ＝チューリングのテーゼを受け入れた場合、チューリングマシンの停止問題と同じであることが判っている。