止まらない機械
永遠にゆれる、2行の表
まず、見てもらいたい機械がいます。仕事は、右へ1歩、左へ1歩——それだけです。表は2行で、「みぎ」の行が右へ送って「ひだり」に移り、「ひだり」の行が左へ送って「みぎ」に戻します。
| 状態 | 読む | 書く | 動く | 次の状態 |
|---|---|---|---|---|
| みぎ | ＿ | ＿ | →右へ | ひだり |
| ひだり | ＿ | ＿ | ←左へ | みぎ |
再生してください。機械は何も書かず、同じところをゆれ続け、60歩めで赤い文字に止められます。「この機械は、止まらないかもしれません」——この歯切れの悪い一言が、今日の主役です。
二度目の事件
あなたはこの光景を知っています。コース2のレッスン9で、あなたは while 1 < 2 { ... } という終わらないくりかえしを自分の言語に解き放ちました。あのとき評価器は10万歩で燃料が尽きて、「いつまでも とまりませんでした」と報告したのでした。
あのときの答えは、燃料で打ち切ることでした。そしてあのとき白状したとおり、打ち切りは判定ではありません。「10万歩で止まらなかった」は「永遠に止まらない」の証明にならない——本当は10万1歩めに止まる機械も、同じ文言で打ち切られるからです。
上の60歩も同じです。打ち切りが言っているのは「ここまでは止まらなかった」だけで、その先のことは、何ひとつ言っていません。
それでも、あなたは言い当てられる
ところが、この2行の機械にかぎっては、あなたは打ち切りより確かなことを言えます。表を読んでください——「みぎ」は「ひだり」へ、「ひだり」は「みぎ」へ。「おわり」に向かう行が、1行もないのです。
実行しなくても、表を読むだけで「永遠に止まらない」と言い切れました。しかも前のレッスンで、機械の表はテープに書ける——プログラムはデータだと分かり、機械を読む機械さえ実際に作れました。読むだけなら、できそうに思えます。
ならば、夢を見たくなります。どんな機械とどんな入力を渡されても、実行せずに表を読んで、「止まる」か「止まらない」かを必ず正しく言い当てる機械——それが1台あれば、燃料も打ち切りも、もう要りません。
「実行して確かめる」ではだめなことに、注意してください。止まる機械なら待てばいつか分かりますが、止まらない機械は、いくら待っても「まだ止まらない」しか分からないからです。だから「読むだけで」が、外せない条件です。
この夢の機械に、名前をつけます。ハンテイです。
坂のいちばん急なところ
ここが、このコースの坂のいちばん急なところです。結論を先に言うと、ハンテイは作れません——これからその理由を、4つの段に分けて歩きます。途中で分からなくなったら前の段に戻ってください——急がなくてよい坂です。
作戦はこうです。「作れたとする」といったん仮定して、そこからありえないことを導きます。ありえないことが出てきたら、悪いのは仮定——つまり「作れない」が言えるのです。
第1段。ハンテイが作れたと、仮にします。 機械の表と入力を渡すと、「止まる」「止まらない」のどちらかを、必ず正しく返してくれる機械です。言いかえると——けっして外さない予言者が、1台いるとします。
第2段。ハンテイを部品にして、新しい機械ヘソマガリを組みます。 ヘソマガリは機械の表を1つ受け取ると、まずハンテイにこう聞きます。「この機械に、この機械自身の表を入力として渡したら、止まりますか」。
答えを聞いたヘソマガリは、その逆をします。
- 「止まる」と言われたら——わざと止まらなくなる。冒頭の2行に入りこんで、永遠にゆれます
- 「止まらない」と言われたら——すぐ止まる
言いかえると、ヘソマガリは「予言の逆を生きる」機械です。ひねくれて見えますが、組み立てに無理はありません。ハンテイが部品として手元にあるなら、「答えを聞いて分かれ道」はただの場合分けですし、「機械に自分自身の表を渡す」のも、表がテープに書けるデータである以上（前のレッスン）、規則違反ではないのです。
第3段。ヘソマガリに、ヘソマガリ自身の表を渡します。 ここが頂上です。ヘソマガリはいつもどおりハンテイに聞きます——「ヘソマガリにヘソマガリ自身を渡したら、止まりますか」。言いかえると、予言者はいままさに起きていること、それ自体を占わされています。
ハンテイの答えは、2つにひとつしかありません。両方とも、見届けます。
- 「止まる」と答えた場合。ヘソマガリは逆をするので、永遠にゆれはじめます。つまり止まりません——予言は外れました
- 「止まらない」と答えた場合。ヘソマガリは逆をするので、すぐ止まります。つまり止まります——予言はやはり外れました
どちらに転んでも、ハンテイは間違えます。けれど第1段で、ハンテイは「必ず正しく返す」機械だと決めたはずでした。正しくて、同時に間違う——これが矛盾です。
第4段。矛盾の犯人を、さがします。 ヘソマガリの組み立てに、ずるはありませんでした。自分の表を渡す手続きも、正当でした。残る容疑者は、最初の「ハンテイが作れたとする」だけ——言いかえると、犯人は仮定しかいないのです。
よって、その仮定がまちがいでした。ハンテイという機械は、存在しません。 むずかしくてまだ誰も作れていない、のではなく——これからどれだけ技術が進んでも、どんな天才が現れても、原理として作れないのです。
「作れない」の正確なかたち
ここで言いすぎないことが、証明と同じくらい大切です。個々のプログラムについて「止まる」と証明することは、ふつうにできます。
レッスン1の「うらがえす」が必ず止まるのは、明らかです——右へ進むだけで、空白に出会えば終わるのですから。今日の冒頭でも、あなた自身が2行の表を読んで「止まらない」を言い当てました。
作れないのは、そういう個別の見極めではありません。どんな機械を渡されても、必ず正しい答えを返す、ただ1台の判定機——「どんな」と「必ず」の両方を背負った機械が、作れないのです。
コンピュータが生まれる前に
この証明をやってのけたのが、レッスン1で会ったアラン・チューリングです。1936年——コンピュータと呼べる機械は、まだ世界のどこにもありません。
つまり人類は、コンピュータを作る前に、コンピュータにできないことをひとつ知っていました。テープとヘッドと表の機械は、計算の限界線を引くために生まれたのです。
コース2のレッスン9で、あなたは「停止性問題」という名前だけをポケットに入れて帰りました。今日、その包みを開きました——中身は、ヘソマガリでした。
✎ 演習：ヘソマガリの行動を予言する
ハンテイが（仮に）あるとして、次の2台の機械をヘソマガリに渡します。それぞれの場合に、ヘソマガリは止まるでしょうか。
- 機械ア——どんな入力でも、必ず止まる機械（「うらがえす」の親戚だと思ってください）
- 機械イ——どんな入力でも、永遠にゆれ続ける機械（冒頭の機械の親戚です）
ヒント1（考え方）
ヘソマガリの手順は、渡された機械が何であれ同じ2歩です。①「その機械に、その機械自身の表を渡したら止まるか」をハンテイに聞く。②答えの逆をする。
こたえ
機械アは、自分自身の表を入力にしても止まります（どんな入力でも止まるのですから）。ハンテイは「止まる」と答え、ヘソマガリは逆をして、永遠にゆれます。
機械イは、自分自身の表を入力にしても止まりません。ハンテイは「止まらない」と答え、ヘソマガリは逆をして、すぐ止まります。
まとめると——きちんと止まる機械を渡されると止まらず、止まらない機械を渡されると止まる。このあまのじゃくな性格が、鏡にうつした自分自身を渡された瞬間、矛盾に変わるのでした。
このレッスンで分かったこと
- 燃料の打ち切りは報告であって判定ではない。「ここまで止まらなかった」は「永遠に止まらない」の証明にならない
- どんな機械にも「止まる／止まらない」を必ず正しく言い当てる判定機ハンテイは、存在しない——「作れたとする」から矛盾を導く、背理法の証明
- 証明の鍵はヘソマガリ——予言の逆をする機械に、自分自身を渡すと、どちらの予言も外れる
- 個々のプログラムが止まると示すことはできる。作れないのは「どんなプログラムにも必ず答える1台」
- これが分かったのは1936年——コンピュータが生まれる前のこと