紙とえんぴつの機械
コンピュータより先に、答えがあった
このコースは、ひとつの問いを追いかけます。計算できるとは、どういうことか。コンピュータにできることと、できないことの境界線は、どこにあるのか。
意外なことに、この問いへの答えはコンピュータが生まれる前に出ています。1936年、イギリスの数学者アラン・チューリングが、紙の上だけで「計算する機械」を設計し、その限界まで突き止めました。電気も歯車も使わない、思考のための機械です。
計算する人を、観察する
チューリングが観察したのは、機械ではなく計算する人間でした。筆算をしているあなたを思い浮かべてください。やっていることを正直に数え上げると、おどろくほど少ないのです。
- 紙のマス目を見る
- マス目に書く（または消す）
- となりのマス目に移る
- 頭の中に「いま、くり上がりの最中だ」のような覚え書きを持つ
これだけです。チューリングはこの4つを部品にして、機械を組みました。マス目の並んだテープ、テープを読み書きするヘッド、そして頭の中の覚え書きにあたる状態。それがチューリング機械です。
動かしてみる
下の実験室に、いちばん素朴なチューリング機械がいます。仕事は「0と1をぜんぶ裏返す」。「再生する」を押して、ヘッド（赤いわく）の旅を見てください。
| 状態 | 読む | 書く | 動く | 次の状態 |
|---|---|---|---|---|
| すすむ | 0 | 1 | →右へ | すすむ |
| すすむ | 1 | 0 | →右へ | すすむ |
| すすむ | ＿ | ＿ | ・そのまま | おわり |
ヘッドは1マスずつ右へ進みながら、0を1に、1を0に書きかえていきます。空白（＿）に出会うと、状態が「おわり」になって止まりました。下に出ている表のことは、次のレッスンでじっくりやります——今日は、機械の体だけ覚えてください。
「状態」は、頭の中の覚え書き
部品の中でいちばんつかみにくいのが状態です。実験室の右上に出ている「すすむ」や「おわり」が、それです。
筆算のくり上がりを思い出してください。「7+5は12、1くり上がって……」の「1くり上がって」は、紙には書いていません。頭の中にあります。状態とは、その頭の中の覚え書きを、有限個の名前にしたものです。この機械は日本語の名前で覚え書きをします——あなたがコース1で使ったにわ語と、同じ思想です。
✎ 演習：機械の気持ちで予想する
実験室の「テープのはじめの中身」を 101 に打ちかえて、再生する前に予想してください。
- 止まったとき、テープには何が残っているでしょう
- 止まるまでに、機械は何歩あるくでしょう（読む→書く→動く、で1歩です）
ヒント1（考え方）
ヘッドは左端から右へ、1マスずつしか進めません。3文字を裏返したあと、止まるためにもう1歩だけ必要です——「もう文字がない」と確かめるのも、読む仕事だからです。
こたえ
テープは 010 になり、4歩で止まります。3歩で3文字を裏返し、4歩目に空白を読んで「おわり」へ移りました。「終わったと気づくにも1歩かかる」——この律儀さが、この機械のすべてです。
このレッスンで分かったこと
- 「計算できるとは何か」への答えは、1936年・紙の上で出ていた
- チューリング機械の部品は3つ：テープ（紙）、ヘッド（見る・書く・移る）、状態（頭の中の覚え書き）
- 状態は、筆算の「くり上がり中」のような覚え書きを有限個の名前にしたもの
- これは計算の本質だけを削り出した、思考のための最小の機械