それでも、庭は実る
崖を見たあとで
前のふたつのレッスンで、あなたは崖を見ました。「このプログラムは止まるか」を実行せずに言い当てるプログラムは、書けない——むずかしいのではなく、原理的に書けないのでした。
それなら、ひとつ不思議なことがあります。この庭の実験室は、止まらないかもしれないプログラムを、あなたに何度も走らせてきました。なのにこのページは、一度も凍りついていません。
判定できないものを、どうやって走らせてきたのか。じつはあなたは、その答えをこの庭で、もう何度も見ています。
この庭の、種明かし
思い出してください。コース2で while を覚えたあなたの言語に終わらないくりかえしを書かせたとき、「プログラムがいつまでも とまりませんでした。」という返事が出ました。あのとき種明かしされたのが燃料（フューエル）——評価の1歩ごとに燃料を1払わせて、尽きたら打ち切る仕掛けです。
今日の種明かしは、その先です。あの燃料は、あの実験室だけの特注品ではありません。この庭の実験室は、ぜんぶ燃料計を積んでいます。
コース1のにわ語は、10万歩で燃料が尽きます。コース2のminilangも、10万歩です。そしてこのコースのチューリング機械が出してきた「◯歩で打ち切りました。この機械は、止まらないかもしれません。」——あれも、同じ燃料計の声でした。
つまりこの庭の作者は、停止性問題を解いていません。解けないと知ったうえで、あきらめ方を決めたのです。
あきらめ方を、設計する
前のレッスンで確かめたとおり、打ち切りは判定ではありません。「10万歩で止まらなかった」は「永遠に止まらない」の証明ではなく、本当は10万1歩めで止まるプログラムを、冤罪で打ち切ることもありえます。
でも、ここからが今日の前進です。判定はできなくても、「10万歩で打ち切って、止まらなかったとみなす」と決めることはできます。 原理が「できない」と言ったのは前者だけで、後者はただの運用——人間が線を引くだけのことだからです。
「みなす」には間違いが混ざります。間違いをゼロにする道は、原理が閉ざしました。それでも、どんな間違い方をどれだけ許すかは、こちらで選べます——線を10万歩に引くか、1000歩に引くか、それを決めるのは定理ではなくあなたです。
この庭の10万歩は、「教材の小さなプログラムなら、まじめに働いていて10万歩かかることはまずない」という見積もりで引いた線です。完璧な答えがないと知ったうえで、間違い方を自分で選ぶ——これが工学という営みです。
暮らしの中の、同じ知恵
この知恵は、計算機の発明ではありません。あなたの暮らしが、先に使っています。
通信のタイムアウト。 メッセージを送って返事がないとき、相手が「答える気がない」のか「まだ考えている」のか、待つ側には原理的に区別がつきません。だからアプリは何秒かで見切りをつけて、「接続できませんでした」と報告します——あれは判定ではなく、あきらめ方の設計です。
フリーズしたアプリの強制終了。 「応答なし」と出たアプリは、本当はあと1秒で復帰するのかもしれません。それでもあなたは終了ボタンを押します。間違うかもしれないと知りながら、待ち続けない方を選んでいるのです。
料理の「弱火で20分」。 鍋の中がどうなっているかは見えないので、時間で区切ります。ただし、このたとえにはひとつ限界があります——鍋はふたを開ければ中が見えますが、計算は「途中」を開けて見ても、終わりが近いのかどうか分からないことがあるのです。
⟡ よりみち：燃料に、本物のお金を払う世界
ブロックチェーンの一種・イーサリアムでは、世界中の参加者が他人の書いたプログラムを実行します。止まらないプログラムを実行させられたら、たまりません。そこで採用されたのが燃料方式——計算の1歩ごとに「ガス」と呼ばれる手数料を本物のお金で払わせて、ガスが尽きたら打ち切るのです。あなたの言語の10万歩と、設計はまったく同じです。停止性問題への工学の答えが、お金の流れる仕組みの土台になっています。
もうひとつの「実は」——暴走できないように、作る
種明かしを、もうひとつ。コース3で正規表現の機械を見たとき、「この庭の機械は後戻りをしないので、原理的に暴走しません」という一文がありました。あれも、あきらめ方の設計です。
ただし流儀がちがいます。燃料は、強い言語に走らせてからブレーキをかける方式でした。正規表現は、そもそも暴走という芸当ができないくらい、言語を小さく作る方式です。
小ささには、代金がありました。コース3の終わりに見たとおり、正規表現は「数えられない」——かっこの対応のような仕事には、原理的に届きません。なんでも計算できる力を差し出して、かならず止まる安全を受け取った。能力と安全の交換です。
✎ 演習：止まらない機械を、止める
下にいるのは、左右にゆれ続けるだけで、永遠に「おわり」へたどり着かない機械です。再生すると、100歩で打ち切られます。
この実験室は表が書きかえられます。表を直して（行を書きかえるか、書き足して）、「止まりました」の返事を出してください。前のレッスンまでのあなたは打ち切られる側でしたが、今日は止める側です。
| 状態 | 読む | 書く | 動く | 次の状態 | この行を消す |
|---|---|---|---|---|---|
ヒント1（考え方）
この機械が止まらないのは、表のどの行をたどっても「おわり」に行き着かないからです。では、どこか1か所を「おわり」につなぎかえたら？
こたえ
いちばん短い直し方は、「みぎ」の行の次の状態を「ひだり」から「おわり」に書きかえることです。1歩で「止まりました」が出ます。「ひだり」の行を直せば2歩——どちらでも、止まれば正解です。
書き足す流儀もあります。「みぎ」の行の書くを「1」に変えて、「みぎ・1を読む→おわり」という行をたしてみてください。機械は1歩めに足あとを残し、一周まわって自分の足あとを踏んだ3歩めに止まります。
どの直し方も、やったことは同じです——止まらないと分かっている機械なら、止まるように直せばいい。判定できないのは「あらゆるプログラム」を相手にしたときの話で、目の前の1台を読んで直すことは、いつでもあなたにできます。
このレッスンで分かったこと
- この庭の実験室は、ぜんぶ燃料計を積んでいる——にわ語もminilangも10万歩で打ち切り、チューリング機械の「◯歩で打ち切りました」も同じ仕掛け
- 停止性は判定できない（原理）。でも「ここで打ち切って、止まらなかったとみなす」線は引ける（運用）——間違い方を自分で選ぶのが工学
- 通信のタイムアウトも、アプリの強制終了も、同じ知恵。暮らしが先に使っていた
- もうひとつの流儀は、暴走できないくらい言語を小さく作ること——正規表現は数えられない代わりに、かならず止まる。能力と安全の交換