計算の庭の、地図
出会った機械を、数えてみる
最終レッスンは、新しい機械を作りません。かわりに、あなたがこの庭で出会ってきた機械たちを、一枚の紙の上に置きなおします。
数えてみましょう。
コース3のもようの機械——状態と矢印でできていて、持ち物は有限の覚え書きだけでした。コース2であなたが作ったminilang——そのパーサは、かっこの入れ子を何段でも正しく数えました。そしてこのコースのチューリング機械——たし算をし、機械を読み、崖のふちまで歩きました。
別々の区画の、別々の住人に見えます。ところがこの3つは、力の順に、きれいに一列にならぶのです。
一枚の地図
地図は、内側から外側へ広がる3つの輪でできています。外の輪は、内の輪をまるごと含みます——外の機械は、内の機械の仕事をぜんぶ肩代わりできるからです。
- いちばん内側：もようの言語（正規言語と呼ばれます）。持ち物は有限の覚え書きだけで、読みながら増やせません。だから速く、暴走せず、そのかわり数えられません
- まんなか：かっこを数えられる言語（文脈自由言語と呼ばれます）。minilangの文法が、ここの住人です。あなたが作ったパーサは「式を読む関数」がかっこの中でもう一度自分を呼ぶ作りでした——あの呼び出しの積み重なりが、深さを数える「紙」の役をしていたのです
- いちばん外側：チューリング機械の言語。計算できることなら、なんでも書けます。そのかわり、止まらないことがあります（レッスン5の崖）
コース3のレッスン7の終わりに、こんな種がまいてありました——「『数えられる機械』とは、どんな機械でしょう。じつは、あなたがコース2で作ったものがそれです」。まんなかの輪が、その答えです。あなたは地図を知る前に、2つめの輪の機械をすでに自分の手で作っていました。
いちばん内側の住人に、あいさつする
懐かしい顔を、ひとつ呼び戻しましょう。いちばん内側の住人、もようの機械です。
あいあい
丸が状態、矢印が遷移。状態の数は、もようを書いた時点で決まっていて、本文がどれだけ長くても増えません。この「読みながら増やせない」ことが内側の輪の壁でした——入れ子のかっこに敗れた、コース3のあの壁です。
輪ごとの、言える・言えない
それぞれの輪に、言えることばと、言えないことばがあります。1行ずつ並べると、地図の等高線が見えてきます。
| 輪 | 言えること（例） | 言えないこと（例） |
|---|---|---|
| いちばん内側（もよう） | 「あ」が3つ以上つづく——あああ+ | 「（」と「）」の対応 |
| まんなか（かっこを数えられる） | 「（」と「）」の対応 | a・b・cを同じ数ずつ並べた列 |
| いちばん外側（チューリング機械） | 計算できることなら、なんでも | ——そのかわり、止まらないことがある |
まんなかの輪にも壁があることだけ、ひとこと添えておきます。aabbcc のように三種類の文字を同じ数ずつ並べた列は、かっこを数えられる機械にも言えません——証明はこの庭の外の話なので、今日は「どの輪にも壁がある」とだけ覚えてください。そして壁の外には、いつも次の輪が待っています。
言語の力は、ただではない
ここで、前のレッスンの勘定書きを地図に重ねます。外の輪ほど強いのなら、なぜ世界はぜんぶ、いちばん外側のことばで書かないのでしょう。
内側の輪は、数えられないかわりに、本文を一度なぞるだけで読み終わり、原理的に暴走しません。外側の輪は、なんでも計算できるかわりに、止まる保証を手放しました。輪をひとつ外に出るたびに、速さか、止まる保証か——何かをひとつ、レジに置いていくのです。
だから、検索窓の裏には内側の輪が、プログラミング言語の文法にはまんなかの輪が住んでいます。手抜きではなく、勘定の結果です。仕事に足りるいちばん内側の輪を選ぶ——それが、この地図の使いかたです。
⟡ よりみち：この地図は、人間のことばを測る物差しだった
この3つの輪には、考えた人の名前がついています——チョムスキー階層。1956年、言語学者のノーム・チョムスキーが提案しました。コンピュータ科学の道具に見えますが、生まれは言語学です。チョムスキーが測ろうとしたのは、人間のことばの文法がどれほどの複雑さを持つか、でした。人間のことばを測るために作られた物差しが、そのままプログラミング言語の地図になった——ことばと計算は、根のところでつながっていたのです。この庭が「言語の庭」と名のっているのは、そういうわけです。
✎ 最終演習：注文を、地図に置く
4つの注文があります。それぞれ、地図のどの輪があれば足りるでしょうか。いちばん内側の輪から考えてください。
- 「この行が『数字3つ・棒・数字4つ』の形か、確かめてほしい」
- 「この式の、かっこの対応が取れているか、確かめてほしい」
- 「このminilangのプログラムを実行して、答えを教えてほしい」
- 「このプログラムが必ず止まるかどうか、実行せずに教えてほしい」
ヒント1（考え方）
聞くことは2つです。「この仕事は、数える必要があるか」「この仕事は、実行そのものを求めているか」。そして4つめは、このコースのレッスン5と6を思い出してください。
こたえ
1は、いちばん内側で足ります——数えなくてよい、かたちの仕事です（コース3の郵便番号と同じ）。2は、まんなか——入れ子を数える仕事です。3は、いちばん外側——実行はチューリング機械の仕事そのものです。そして4は、地図のどの輪にも置けません。レッスン5と6で確かめたとおり、いちばん外側の機械にもできない注文です。この地図には「外」がある——それを証明つきで知っていることも、あなたの持ち物です。
歩いてきた道（コース5の総括）
- 機械——テープ・ヘッド・状態。計算する人間から削り出した、思考のための最小の機械（レッスン1）
- 表——機械の個性は遷移表だけ。表がプログラム（レッスン2）
- たし算——計算とは、意味の分からない記号を決まりどおりに書きかえる作業（レッスン3）
- 万能——機械を読む機械。表もまた、テープに書けるデータだった（レッスン4）
- 崖——「止まるかどうか」は、実行せずには見抜けない（レッスン5）
- 対角線——その不可能は、自分自身を読ませる一撃で証明できる（レッスン6）
- 燃料——言語の力は、ただではない。能力と安全の交換（レッスン7）
- 地図——機械たちは一枚の地図にならび、地図には「外」もある（このレッスン）
庭の、次の区画へ
この地図は、明日からの道具です。目の前の仕事に「これは数える仕事か」「実行まで要る仕事か」と問えば、輪がひとつ指させます——道具選びとは、地図の上で住所を決めることでした。
そして、扉がひとつ残っています。停止性は実行前に判定できませんでした——けれど、実行前に確実に分かることもあります。たとえば「この式は、数と真偽を足そうとしている」という間違いは、動かさなくても捕まえられます。
崖のこちら側で、もうひとつの知恵が待っています。コース2で作ったminilangに「型」という目を足す、コース6「型のはなし」です。
修了、おめでとうございます！ あなたはもう、「計算できる」ということばの意味を、機械を自分の手で動かして知っている人です。