停止性問題のソースを表示
←
停止性問題
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''停止性問題'''(ていしせいもんだい)あるいは'''Halt'''(ホルト)は、(直接的には)[[計算可能性理論]]の問題で、[[チューリング機械]](≒[[プログラム (コンピュータ)|プログラム]]、[[アルゴリズム]])''A''に入力''x''を入れたら有限時間で停止するか、という問題。[[アラン・チューリング]]は[[1936年]]、停止性問題を解くチューリング機械が存在しない事を[[カントールの対角線論法|対角線論法]]で示した。すなわちそのようなチューリング機械の存在を仮定すると、自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止するような別のチューリング機械が構成できるという矛盾が導かれる。 == 概要 == プログラム''A''にデータ''x''を入力して実行する事を''A''(''x'')と書き、''A''(''x'')が''y''を出力するとき''y''=''A''(''x'')と書く。コンピュータではいかなるデータも0と1の数字で表し、したがってプログラム自身も0と1の数字で表せる。 コンピュータ用語ではこの数値化を「[[エンコード|符号化]]」と呼び、[[理論計算機科学]]では「[[ゲーデル数]]化」という。以下記号を簡単にする為、プログラムAを数字で表したものも、Aと書く。 よって例えばプログラムA、Bに対し、「A(B)」は、「プログラムBを表す数字をBとし、AにBを入力して実行する」の意である。停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が有限時間で停止するかどうかを決定せよ」という問題である。 また「停止性問題の決定不能性定理」とは、停止性問題を常に正しく解くプログラムは存在しない、という定理である。 すなわち以下の性質を満たすプログラム''H''は存在しない、という定理である。 全てのプログラム''A''と全てのデータ''x''に対し、 * ''A''(''x'')が有限時間で停止する ⇒ ''H''(''A'',''x'')は有限時間でYESを出力して停止する。 * ''A''(''x'')は有限時間では停止しない ⇒ ''H''(''A'',''x'')は有限時間でNOを出力して停止する。 ''H''の定義より、''H''は入力(''A'',''x'')によらず'''必ず停止する'''事に注意されたい。''A''(''x'')が停止するかどうかを、<b>必ず停止する</b>''H''を使って決定する事はできない、というのが定理の趣旨である。 == 証明 == 背理法で示す。証明は、[[自己言及のパラドックス#嘘つきのパラドックス|嘘つきのパラドックス]]に類似した論法を使う。 停止性問題を常に正しく解くプログラム''H''が存在したとする。 ''M''(''A'')を、''H''(''A'',''A'')=YESなら停止せず、''H''(''A'',''A'')=NOなら0を出力して停止するプログラムとする。(''H''(''A'',''A'')と[[無限ループ]]を組み合わせる事で''M''(''A'')を作る事ができる。) ''M''(''M'')は停止するだろうか? * ''M''(''M'')が停止したとすると、''M''の定義より''H''(''M'',''M'')=NO。''H''の定義より ''H''(''M'',''M'')=NOとなるのは''M''(''M'')が停止しないときのみなので、矛盾。 * ''M''(''M'')が停止しないとすると、''M''の定義より''H''(''M'',''M'')=YES。''H''の定義より、''H''(''M'',''M'')=YESとなるのは''M''(''M'')が停止するときのみなので、矛盾。 よって停止性問題を常に正しく解くプログラム''H''は存在しない。 なお、[[ゲーデルの不完全性定理|ゲーデルの第一不完全性定理]]の証明は停止性問題の決定不能性の証明の別表現である。 == カントールの対角線論法との関係 == [[対角線論法]]は、集合Sからその冪集合P(S)への全単射が存在しない(カントールの定理)事を示す為に[[ゲオルグ・カントール]]が使った論法である。 実は上述の証明は対角線論法も利用している。以下簡単の為、プログラムの入力は全て自然数とする。前述したようにプログラムは0と1からなる数字で書き表せるので、プログラム全体の集合と自然数全体の集合<math>\mathbb{N}</math>と自然に同一視できる。本当は<math>\mathbb{N}</math>の中にはプログラムに対応していないものもあるが、簡単の為その辺の事情は略する。 <math>\phi:\mathbb{N} \times \mathbb{N} \mapsto \{0,1\}</math>を次のように定義する: :''A''(''x'')が停止すればφ(''A'',''x'')=1、そうでなければφ(''A'',''x'')=0。 以下φ(''A'',''x'')の事をφ<sub>''A''</sub>(''x'')と定義する。<math>g:\mathbb{N} \mapsto \{0,1\}</math>を、g(''A'')=¬φ<sub>''A''</sub>(''A'')により定義する。ただしここで「¬」は0と1を反転する写像。すなわち¬0=1、¬1=0。 すると対角線論法により、''g''=φ<sub>''M''</sub>となる''M''は存在しない。 さて、仮に停止性問題を常に正しく解くプログラム''H''が存在するとする。''M''(''A'')を、''H''(''A'',''A'')=YESなら停止せず、''H''(''A'',''A'')=NOなら0を出力して停止するプログラムとすると、''M''と''H''の定義より''g''=φ<sub>''M''</sub>が成立し、矛盾。したがって停止性問題を常に正しく解くプログラムは存在しない。 == 関連項目 == * [[ゲーデルの不完全性定理]] * [[ライスの定理]] * [[チャイティンの定数]] * [[時間階層定理]]:停止性問題の決定不能性は「有限時間」と「無限時間」という2つの時間階層の間の[[時間階層定理]]だと解釈できる。 * [[無限ループ]] {{DEFAULTSORT:ていしせいもんたい}} [[Category:数理論理学]] [[Category:計算理論]] [[Category:思考実験]] [[Category:数学の問題]] [[Category:数学に関する記事]]
停止性問題
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報