コース 5

計算できる、とはどういうことか

紙とえんぴつの機械が、計算の限界を教えてくれる

コンピュータにできること・できないことの境界線は、100年近く前に紙の上で引かれていました。チューリング機械を自分の手で動かして、その線まで歩きます。

01 紙とえんぴつの機械コンピュータが生まれる前に、計算の正体は紙の上で見つかっていた。チューリング機械——テープと、ヘッドと、頭の中の覚え書き。
02 表がすべてを決める機械の個性は、遷移表という1枚の表に書かれている。表を読み、そして書きかえて、自分の機械を作る。
03 こんな単純な機械が、たし算をする数の表し方を自分で決めるところから、たし算は始まる。棒の数で数を書けば、3+2は「記号の書きかえ」に化ける——たった4行の表で。
04 機械を読む機械遷移表は記号の並び——ならば、テープに書ける。1台でどんな機械のまねもできる万能機械と、「プログラムもデータである」という発見。
05 止まらない機械「このプログラムは止まるか」を必ず言い当てる機械は、作れない。1936年、コンピュータが生まれる前に紙の上で引かれた、計算の限界線まで歩きます。
06 対角線のあそび「この文は、うそである」。自分に折り返すと宙づりになる、あの形には名前がある——対角線論法。名簿の表をひとつ作って、ヘソマガリの手口の種を指でたどる。
07 それでも、庭は実る止まるかどうかは判定できない——それでも、実験室は今日も動いている。タイムアウトと燃料という工学の知恵、そして、この庭ぜんぶの種明かし。
08 計算の庭の、地図最終レッスン。もようの機械、minilangのパーサ、チューリング機械——別々の区画で出会った機械たちが、じつは一枚の地図の上に、力の順でならんでいる。