停止性問題
![]() | この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。(2018年1月) |
計算可能性理論において停止性問題(ていしせいもんだい、英: halting problem)または停止問題は、「どんなチューリングマシン[注 1]、あるいは同様な計算機構についても、それが有限時間で停止するかを判定できるアルゴリズム」は可能か、という問題。
アラン・チューリングは1936年、停止性問題を解くアルゴリズムは存在しないことをある種の対角線論法のようにして証明した。 すなわち、そのようなアルゴリズムを実行できるチューリングマシンの存在を仮定すると「自身が停止するならば無限ループに陥って停止せず、停止しないならば停止する」ような別の構成が可能ということになり、矛盾となる。
概要
プログラムAにデータxを入力して実行する、ということをA(x)と書き、A(x)がyを出力するときy=A(x)と書くことにする。
現代のコンピュータの使い方であれば、中身がプログラムであるバイナリの実行ファイルを、単なるデータファイルとして扱うこともできる、ということから、プログラムを、他のプログラムへの入力データにできる、ということは感覚的にわかる。また具体的には、エミュレータに実行ファイルを渡す、というのが一例である。チューリングは、「いかなるチューリングマシンをも模倣できるチューリングマシン」である「万能チューリングマシン」が可能であることを示し、模倣されるチューリングマシンはそのテープの初期状態に記述される、というようにして議論を進めた。
以下記号を簡単にする為、「データとしてのプログラムA」も、Aと書く。 よって例えばプログラムA、Bがあったとして、「A(B)」は、「プログラムAに、データとしてのプログラムBを入力として渡す」の意である。停止性問題とは、「プログラムAとデータxが与えられたとき、A(x)が停止するかどうかを決定せよ」という問題である。
また「停止性問題の決定不能性」とは、停止性問題を常に正しく解くプログラムは存在しない、ということである。 すなわち以下の性質を満たすプログラムHは存在しない。
全てのプログラムAと全てのデータxに対し、
- A(x)の実行は停止する ⇒ H(A,x)はYESを出力する。
- A(x)の実行は停止しない ⇒ H(A,x)はNOを出力する。
証明
停止性問題を解くプログラムHが存在すると仮定して矛盾を導く。証明は嘘つきのパラドックスに類似している。
M(A)を、H(A,A)=YESならM(A)自身は停止せず、H(A,A)=NOなら0を出力してM(A)を停止するプログラムとする。(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からなる数字で書き表せるので、プログラム全体の集合は自然数全体の集合
停止問題
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/10/17 08:19 UTC 版)
詳細は「チューリングマシンの停止問題」を参照 停止問題は計算機科学の重要な問題の1つであり、計算可能性理論だけでなく日々のコンピュータの利用にも深い意味を持っている。停止問題を簡単に述べると次のようになる: チューリングマシンと入力が与えられたとき、その入力を与えられたプログラム(チューリングマシン)は停止(完了)するかどうかを求めよ。停止しない場合、永遠に動作し続ける。 ここでチューリングマシンが判定しようとするのは素数や回文といった単純な問題ではなく、チューリングマシンで他のチューリングマシンに関する質問への答えを得ようとしているのである。詳しくは主項目(チューリングマシンの停止問題)を参照してもらうとして、結論としてこの問いに(あらゆる場合に)答えられるチューリングマシンは構築できない。 すなわち、あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラムを実行してみるしかないということになる。そして、停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せずに永遠に動作するのかは判らない。あらゆるチューリングマシンに関する記述とあらゆる入力の停止する全組合せからなる言語は帰納言語ではない。従って、停止問題は計算不能または判定不能と呼ばれる。 停止問題を拡張したライスの定理では、言語が特定の自明な特性を持つかどうかは(一般に)判定不能であるとされる。
※この「停止問題」の解説は、「計算可能性理論」の解説の一部です。
「停止問題」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。
- 停止問題のページへのリンク