停止問題とは? わかりやすく解説

停止性問題

(停止問題 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/03/17 21:19 UTC 版)

計算可能性理論において停止性問題(ていしせいもんだい、: 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つであり、計算可能性理論だけでなく日々コンピュータの利用にも深い意味を持っている。停止問題を簡単に述べると次のうになる: チューリングマシン入力与えられたとき、その入力与えられプログラムチューリングマシン)は停止完了)するかどうか求めよ停止しない場合永遠に動作し続ける。 ここでチューリングマシン判定しようとするのは素数回文といった単純な問題ではなくチューリングマシンで他のチューリングマシンに関する質問への答え得ようとしているのである詳しくは主項目(チューリングマシンの停止問題)を参照してもらうとして、結論としてこの問いに(あらゆる場合に)答えられるチューリングマシン構築できない。 すなわち、あるプログラムとその入力があったとき、それが停止するかどうかは単にそのプログラム実行してみるしかないということになる。そして、停止すれば停止することがわかる。停止しない場合は、それがいつか停止するのか、それとも停止せず永遠に動作するのかは判らないあらゆるチューリングマシンに関する記述あらゆる入力停止する組合せからなる言語帰納言語ではない。従って、停止問題は計算不能または判定不能呼ばれる。 停止問題を拡張したライスの定理では、言語特定の自明な特性を持つかどうかは(一般に判定不能であるとされる

※この「停止問題」の解説は、「計算可能性理論」の解説の一部です。
「停止問題」を含む「計算可能性理論」の記事については、「計算可能性理論」の概要を参照ください。

ウィキペディア小見出し辞書の「停止問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「停止問題」の関連用語










10
18% |||||

停止問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



停止問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの停止性問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算可能性理論 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS