停止問題

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

停止問題

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

「計算可能性理論」の記事における「停止問題」の解説

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