停止問題（ハルティング問題）とは？定義とチューリングの証明をわかりやすく

停止問題（ハルティング問題）の定義とチューリングの不可能性証明を図解と例でやさしく解説。直感と論理を結びつけて初心者にもわかりやすく整理。

ハルティング問題（停止問題）は、コンピュータサイエンスの問題の基本的な未解決（不可判定）性を示す問題です。簡単に言えば、「任意のプログラムとその入力を与えたとき、そのプログラムが有限時間で停止するか（終了するか）を確実に判定する汎用プログラムが存在するか？」という問いです。

定義（直感的）

より正確には、ハルティング問題は次の決定問題です。入力としてプログラム（またはチューリングマシン）Fと入力Iが与えられたとき、FをIで実行した場合に有限のステップで停止するかを判定する関数（アルゴリズム）が存在するかを問います。もしそのような判定器（デシダー）H(F,I)が存在すれば、任意の（符号化された）プログラムと入力について「停止する／しない」を正しく返すことになります。

チューリングの証明（本質）

アラン・チューリングは1936年に、一般的な停止判定器は存在しない（ハルティング問題は決定不能である）ことを示しました。証明は典型的には反例を作る「自己言及」と「矛盾」に基づく方法です。以下はその分かりやすい説明です。

まず、矛盾を導くために、仮に停止判定器 H(F, I) が存在すると仮定します。ここで H は以下のように振る舞うとします：

 function H(F, I):     // F: プログラム、I: 入力     // F(I) が有限時間で停止するなら True を返す     // 停止しない（無限ループする）なら False を返す 

次に H を使って、新しいプログラム D を次のように定義します（擬似コード）：

 function D(X):     if H(X, X) then         loop forever   // 無限ループする     else         return        // 停止する 

この D は「与えられたプログラム X が自分自身を入力として実行したときに停止するかどうか」を H に問い合わせ、その答えに反対の振る舞い（停止するならループ、ループなら停止）をします。ここが自己言及のポイントです。

では、D に自分自身を与えて実行するとどうなるでしょうか（すなわち D(D) を考える）？起こりうるのは次の二通りだけです：

• もし H(D, D) が True（＝D(D)は停止する）と判定したなら、D の定義により D(D) は無限ループする。だがこれは H の判定と矛盾する。
• もし H(D, D) が False（＝D(D)は停止しない）と判定したなら、D の定義により D(D) は即座に停止する。これも H の判定と矛盾する。

どちらの場合でも矛盾が生じるため、最初の仮定（任意の F, I に対して正しく答える停止判定器 H が存在する）は間違っています。したがって、汎用的な停止判定器は存在しません。これがチューリングの証明の要旨です。

補足：半決定可能性（再帰的列挙性）について

重要な点として、ハルティング問題が「判定不能（Decidable でない）」であっても、完全に何もわからないわけではありません。ハルティング集合（停止する〈プログラム, 入力〉の集合）は再帰的列挙可能（半決定可能）です。つまり、ある手続きは次のように振る舞います：

• 与えられた (F,I) を並列（あるいは逐次的に時間スライスして）シミュレートして、実際に F(I) が停止したことが確認できれば「停止する」と報告して停止する。
• しかし F(I) が停止しない場合、その手続きも永遠に動き続け、答えを出さない（拒否も肯定もしない）。

つまり「停止する」ケースを認める有効な検査手続きはありますが、「停止しない」ことを必ず正しく判定して有限時間で報告する一般的アルゴリズムは存在しません。

なぜ重要か・応用

• 停止問題の不可判定性は、プログラムの一般的な自己検査や完全な静的解析の限界を示します。任意のプログラムに対して「バグがあるか」「必ず終了するか」を完全に自動判定することは不可能です。
• また、停止問題の証明手法は、計算可能性理論の基本技法（自己言及、対角法、還元）として多くの他の不可判定性証明（ライスの定理など）にも使われます。

まとめ

ハルティング問題とは「任意のプログラムと入力について、そのプログラムが停止するかを判定できるか？」という問題です。アラン・チューリングは1936年に、この種の汎用判定器は存在しない（ハルティング問題は決定不能である）ことを示しました。これは計算理論の基礎的かつ重要な結果であり、現代の計算機科学やプログラム解析に深い示唆を与えています。詳しく学ぶと、半決定可能性や不可判定性の概念、さらにそれらが持つ理論的・実用的影響が理解できます。

この証明の元になった歴史的発見は、1936年にアラン・チューリングによって発表されました。

質問と回答

Q:ハルティング問題とは何ですか?

Q:プログラムがハルティング問題を解決しているかどうかは、どのようにしてわかるのですか?

Q:そのようなプログラムが存在しないことを証明する方法はあるのでしょうか?

Q:Pは何をするのですか?

Q: Q は何をするのですか?

Q:Rは何をするのですか?

Q:Rに自分自身を見させるとどうなるのですか?

文字で検索