ゆめさくエンジニア研究所女性向けエンジニアスクール女性向けエンジニアスクール
ログイン

チューリングマシンと停止問題

回 1-8　道 1 数と論理と計算量

チューリングマシンは、1936 年に Alan Turing が考えた計算の模型で、マス目の並んだ長いテープと、1 マスずつ読み書きするヘッドと、今の状態と、規則の表だけでできています。今のコンピュータで計算できることは、この単純な機械でも計算できると考えられています。一方で、どんなプログラムでも止まるかどうかを必ず正しく答える機械は作れません。これを停止問題が解けないと言い、元になる論法を Turing が同じ論文で示しました。

目安 55 分1-8 (1-1〜1-8 の中)

読み終えたらどんなプログラムでも止まるかを判定する道具が作れない理由を、例で話せる

この頁の流れ

  1. 1止まるかどうかを、前もって判定できるか
  2. 2チューリングマシンはどう計算するのか
  3. 3動かして確かめる
  4. 4止まるかを判定する機械は、なぜ作れないのか
  5. 5仕事でどう確かめるか
  6. 6関わる実例
  7. 7よくある問い
  8. 8確認クイズ
  9. 9説明課題
  10. 10一次資料
  11. 11次へ

「まだ作られていない」道具と、「原理として作れない」道具を切り分けられるようになります。

文 ゆめさくコード編集部公開 2026年10月26日更新 2026年10月26日出典を確かめた日 2026年10月26日

止まるかどうかを、前もって判定できるか

どんなプログラムでも、動かす前に「いつか止まるか、永遠に回り続けるか」を必ず正しく答える道具は、原理として作れません。これを停止問題が解けない、と言います。

プログラムが固まって返事をしなくなる原因の多くは、終わらないループです。それなら、プログラムを読み込んで「このコードは止まります」「ここで永遠に回ります」と教えてくれる検査の道具があれば、とても便利です。なぜ、そんな道具は無いのでしょうか。技術が足りないからでしょうか。

ループは条件が偽になった周で止まり、変数を変えないと条件は真のままで終わらない図

答えは、技術ではなく論理の問題です。1936 年に Alan Turing は、計算そのものを単純な機械の模型で表し、その模型の上で、機械の振る舞いを前もって判定する機械が作れない問題があることを示しました。今の形の停止問題は、その論法を整えた物です。この回では、その模型のチューリングマシンを Python で動かし、判定の道具が必ず間違える相手を作ってみます。

チューリングマシンはどう計算するのか

チューリングマシンは、テープの 1 マスを読み、規則の表に従って書き換えて 1 マス動く、を繰り返すだけの機械です。この単純な繰り返しで、今のコンピュータにできる計算を表せると考えられています。

4 つの部品

チューリングマシンは、Turing が 1936 年から 1937 年にかけて発表した論文「On Computable Numbers, with an Application to the Entscheidungsproblem」で考えた模型で、Turing machine の名前は、その論文の書評で Alonzo Church が付けました。部品は次の 4 つです。

部品役目
テープマス目が限り無く続く帳面
ヘッド1 マスを読み書きする
状態今どの段階かの印
規則の表次に何をするかの表

規則の表の 1 行は、「今の状態がこれで、読んだ記号がこれなら、この記号を書き、左か右へ 1 マス動くかその場に留まり、次の状態をこれにする」という 5 つ組です。教科書は、これに記号の集まりや始めと終わりの状態を合わせて、機械を数の組として定義します。

テープは限り無く続くので、メモリの量に上限の無いコンピュータに当たります。止まる状態に入ったら、機械は止まります。

万能チューリングマシンと、今のコンピュータ

Turing は、ほかのチューリングマシンの規則の表をテープから読み、その機械の動きを真似る 1 台の機械、万能チューリングマシンも作ってみせました。プログラムをデータとしてテープに置き、それを読んで実行する作りで、プログラムをメモリに置いて実行する今のコンピュータと同じ考えです。

このため、チューリングマシンと同じだけの計算ができることを、チューリング完全と呼びます。Python のような普段の言語も、メモリが足りる限り、チューリングマシンにできる計算はすべて書けます。

チャーチ=チューリングの提唱

計算できる問題とは、ある手順で機械的に答えを出せる問題のことで、チャーチ=チューリングの提唱は、それがちょうどチューリングマシンで計算できる問題だと考えます。Church と Post も同じころ別の方法で計算を定め、どれも同じ範囲だと分かりました。

これは数学の定理ではなく提唱です。「機械的な手順」という言葉が数学の言葉で書けないので、証明はできません。それでも、Turing と Church と Post が別々に考えた計算の模型が、どれも同じ範囲になったことが、この提唱を支えています。

動かして確かめる

2 進数に 1 を足すチューリングマシンを、Python で動かします。ヘッドは右端の桁から始め、規則は 3 行です。

状態は、足している途中の A と、止まった H の 2 つです。

状態読む書く動く次
A10左A
A01留まるH
A空白1留まるH

1 を読んだら 0 にして、繰り上がりを左の桁へ運びます。0 か空白を読んだら 1 にして止まります。

動かす 2 進数に 1 を足す機械

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1 A 1010
2 A 1000
3 H 1100

1011 (10 進数の 11) が、3 歩で 1100 (12) になりました。1 歩目と 2 歩目で右の 2 桁の 1 を 0 にして繰り上がりを運び、3 歩目で 0 を 1 にして止まりました。機械は足し算を知りません。表の 3 行に従っているだけです。

規則の表を書き換えると、別の計算をする機械になります。今度は、状態 B のまま右へ進みながら 1 を書き続ける機械です。止まる状態 H に入る行がありません。

動かす 止まらない機械を上限で打ち切る

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1000 B 1000

1000 歩で打ち切っても、状態は B のままで、テープには 1 が 1000 個並びました。この機械は永遠に止まりません。ただ、1000 歩で打ち切った時点では「あと 1 歩で止まる機械」と見分けがつきません。動かして待つだけでは、止まらないことは確かめられないのです。

止まるかどうかが、動かしてみるまで分からない例もあります。偶数なら 2 で割り、奇数なら 3 倍して 1 を足す、を 1 になるまで繰り返します。

動かす 1 に着くまでの歩数

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

1 0
2 1
3 7
6 8
7 16
27 111

27 から始めると、1 に着くまでに 111 歩かかりました。この繰り返しがどの数から始めても 1 に着くか (このループがいつも止まるか) は、コラッツの問題と呼ばれ、まだ誰も証明できていません。2025 年の論文で、2 の 71 乗までのすべての数で 1 に着くことが計算で確かめられています。

止まるかを判定する機械は、なぜ作れないのか

止まるかを必ず正しく答える判定の機械があると仮定すると、その答えの逆をする機械を作れてしまい、判定は自分を相手にした所で必ず間違えます。これが停止問題が解けない理由です。

判定の逆をする機械

判定の機械を judge とし、プログラムを渡すと、止まるなら True、止まらないなら False を返すとします。この judge を使って、次の機械 trouble を作ります。

  • judge(trouble) が True (止まる) と答えたら、永遠に回る
  • False (止まらない) と答えたら、すぐ止まる

trouble は止まるでしょうか。止まると判定されたら回り続け、止まらないと判定されたら止まります。どちらの答えも外れです。だから、どんなプログラムにも正しく答える judge は無いことになります。

実際に、いつも「止まる」と答える判定 A と、いつも「止まらない」と答える判定 B を用意して確かめます。永遠に回る所は、ここでは回らずに「ループへ」と返すだけにして、どちらへ進むかを見ます。

動かす 判定の逆をする機械

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

判定 A 止まる ループへ
判定 B 止まらない すぐ止まる

判定 A に対しては、trouble はループへ進みました。判定 B に対しては、すぐ止まりました。どちらの判定も、自分を使って作った trouble には外れます。判定の中身をどれだけ賢くしても、その判定から同じ形の trouble を作れるので、逃げ道がありません。

動かして確かめる判定は、終わらない

それなら、判定の中で相手を実際に動かして、止まったら True を返せばよいでしょうか。

動かす 動かして確かめる判定

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

RecursionError

judge は trouble を動かし、trouble はすぐに judge(trouble) を呼び、それがまた trouble を動かします。呼び出しが限り無く深くなり、Python は呼び出しの深さの上限で RecursionError を出して止めました。動かして確かめる判定は、止まらない相手には答えを返せません。

再帰は自分の中で小さい自分を呼び、止まる条件に着くと戻る図。Python は既定で 1000 段が上限

崩れる前提をまとめると、次の通りです。

  • 時間をかければ、どんなプログラムも止まるか分かる、という前提。止まらない相手は、いくら待っても「止まらない」と言い切れない
  • 判定の道具を賢くすれば、いつか全部に答えられる、という前提。どんな判定からも、それが外れる相手を作れる
  • 判定できないのは難しいプログラムだけ、という前提。コラッツの問題のような 10 行ほどのループでも、止まるかはまだ誰にも分からない

仕事でどう確かめるか

停止問題が解けないので、仕事では「必ず止まる形で書く」と「上限で打ち切る」の 2 つで守ります。

1 つ目は、ループに止まる理由を書くことです。回るたびに必ず減り、0 より小さくならない数 (残りの件数、残りの回数) があれば、そのループは止まります。条件を n != 0 ではなく n > 0 と書くだけでも、飛び越して止まらない事故を防げます。

動かす 飛び越すと止まらない

python実行可能
出力

▶ 実行ボタンを押すと結果がここに表示されます

実行すると、次の通りに出ます

止まった
打ち切り

10 から 2 ずつ減らすと 0 で止まりますが、7 から減らすと 5、3、1、−1 と 0 を飛び越し、100 歩の上限で打ち切られました。

2 つ目は、上限で打ち切ることです。外の通信、利用者の入れた正規表現、受講生のコードの実行のように、止まるか分からない処理には、時間か歩数の上限を付けます。上限に届いたら「止まらなかった」ではなく「上限に届いた」と記録します。

3 つ目は、検査の道具の答えを読み分けることです。終わらないループを探す道具は、停止問題が解けないので、見逃しか、誤った警告か、「分からない」のどれかを必ず含みます。警告が無いことは、止まる証明ではありません。

関わる実例

止まるかの判定は、小さな機械でさえ、人と計算機の大きな協力が要ります。

5 状態のビジービーバーの値 BB(5) の確定 (2024 年 7 月 2 日)

ビジービーバーの値は、状態の数を決め、記号を 0 と 1 の 2 つにしたチューリングマシンのうち、空のテープから始めて止まる機械が、止まるまでに動ける歩数の最大です。研究者の共同の取り組み bbchallenge は、2024 年 7 月 2 日に、5 状態の値 BB(5) が 47,176,870 歩だと証明したと発表しました。証明は定理の証明を機械で確かめる道具 Coq で書かれています。

崩れた前提は「状態が 5 つしかない機械なら、止まるかはすぐ分かる」です。2025 年に出た論文によると、証明では 5 状態の機械を 181,385,789 台並べ、1 台ずつ止まるか止まらないかを決めました。止まらない機械は動かして待っても決められないので、機械の形ごとに止まらない理由を示す判定の方法を作って当てました。ここでも、全部の機械に効く 1 つの判定は無く、形ごとに別の判定が要りました。

よくある問い

今のコンピュータはチューリングマシンの実物ですか

作りは違いますが、計算できることの範囲は同じだと考えられています。今のコンピュータは、テープではなく番地の付いたメモリを持ち、1 マスずつではなく好きな番地を読みます。ただ、テープが限り無いチューリングマシンと違い、実物のメモリには上限があります。

有限オートマトンとの違いは何ですか

有限オートマトンは、状態と規則の表は持ちますが、書き込めるテープを持たない機械です。覚えておけるのは今の状態だけなので、たとえば開きかっこと閉じかっこの数が合っているかを、どれだけ長い文でも確かめることはできません。チューリングマシンはテープに書いて覚えておけるので、それもできます。

チューリングテストとの違いは何ですか

チューリングテストは、Turing が 1950 年に、機械が考えると言えるかを問うために出した、会話の相手が人か機械かを当てる試しです。チューリングマシンは計算の範囲を調べるための模型で、知能を測る物ではありません。名前に同じ Turing が付いているだけで、別の話です。

停止問題が解けないなら、バグを探す道具は役に立たないのですか

役に立ちます。解けないのは「どんなプログラムにも必ず正しく答える」ことで、多くのプログラムに正しく答えることはできます。道具は、分からない所では警告を出すか黙るので、警告が無いことを止まる証明と取り違えないことが大事です。

確認クイズ

答えだと思う選択肢を押すと、その場で正誤と理由が開きます。4 問すべてに正しく答えると、この回は修了で、石が緑に変わります (この端末のブラウザに残ります)。間違えた問いは、あとから解き直せます。

1 問目

チューリングマシンの部品に入らない物はどれですか。

2 問目

このコードを動かすと何が出ますか。上の 2 進数に 1 を足す機械の規則で、テープを 111、ヘッドを右端から始めます。

111 に 1 を足す

tape = dict(enumerate("111"))
pos, state = 2, "A"
while state != "H":
    sym = tape.get(pos, "_")
    w, mv, state = rules[
        (state, sym)]
    tape[pos] = w
    pos += mv
row = [tape[i] for i in
       sorted(tape)]
print("".join(row))

3 問目

停止問題について正しいのはどれですか。

4 問目

止まるか分からない処理を、仕事で安全に動かす方法はどれですか。

説明課題

次のことを、自分の言葉で 3 行にまとめてください。書いたら、下の模範解答を開いて比べてください。

  • どんなプログラムでも止まるかを判定する道具が作れない理由を、trouble の例で
  • それでも仕事で止まらない処理から身を守る方法

模範解答

自分の説明を書いてから開いて、比べてください。

この回の先の一歩

どんな入力でも必ず判定できる道具は作れないと知っていると、検査の道具の結果を過信せず、試験と人の目を組み合わせる設計ができます。いまの自分が転職までの道のどの段にいるかは、転職診断で確かめられます。

一次資料

どれも 2026年10月26日に開いて、題と中身を確かめました。

次へ

前の回 1-7情報量とハフマン符号化ビット、確からしさ、圧縮

道 1 数と論理と計算量の回

  1. 1-12 進数と 16 進数桁の重み、変換、表せる範囲頁で読む
  2. 1-2文字コードと文字化けUnicode、UTF-8、Shift_JIS、BOM頁で読む
  3. 1-3計算量を数えるBig-O、ループの回数頁で読む
  4. 1-4論理と真理値表AND、OR、NOT、ド・モルガン準備中
  5. 1-5リトルエンディアンとビッグエンディアンバイトの並び順、ネットワーク、ファイル頁で読む
  6. 1-6Base64 の仕組み64 字の表、= の詰め物、長さ 4/3頁で読む
  7. 1-7情報量とハフマン符号化ビット、確からしさ、圧縮頁で読む
  8. 1-8チューリングマシンと停止問題テープ、状態、計算できない問題この回

道 1 の頁へ戻るほかの道を見る