4月4日「チューリングマシン」

シリーズ「ぼんやりコンピュータ」コンピュータについて、なんとなく文章にしてみます。一応コンピュータの歴史にそって書いていき、最終的に現在のコンプーターの話にもっていく予定です。

今日は「チューリング・マシン」の話です。

数学者アラン・チューリングさんは、まだ存在しない未来の計算機について考えていました。

「理論計算機科学」理論上の計算機の性能について、数学モデルで計算機を構築することができれば、

たとえ今現在は存在しない未来のコンピューターであっても、その能力の上限が計算できるはず……！

そのために作成された仮想計算機モデル、それが「チューリング・マシン」です。

チューリングマシンは「無限の長さのテープ」と「そのテープのどこでも読み書きできるヘッド」から構成されているマシーンです。

最近の人は「磁気テープ」になじみがないのでこの説明ではピンとこないかもしれません。「無限にページがあるノート」のどこでも読み書きできる「鉛筆と消しゴムを持った人」の組み合わせを想像してもらえればいいと思います。

この組み合わせで、まあだいたいの問題は解けそう、というのは直感的にわかるんじゃないかなと思います。

無限ページのノートなので大量の数字をこの人に渡すことができますし、無限ページのノートなので大量の数字を書くこともできます。記憶力がおいつかなければメモをとることもできます。

「一生計算しても計算が終わらない命題」とか、解けない問題もあるにはありますが、現在のコンピューターにできるようなことはこのチューリングマシンが全部できる、とみなしていいそうです。

なんでもできるということは、チューリングマシン上で「チューリングマシンを動かす」ということもできるということ……？

これができるんですね。あらかじめノートに命令をならべておくわけです。命令には「現在のページを読みなさい」とか、「現在のページに数字を書きなさい」とか「何ページ前に進みなさい」とかそういうのをあらかじめて決めて、チューリングマシンの中の人に教えておく必要があります。

「命令のページ」と「命令を実行するページ」が同じだと、命令がどんどん書き換わってヘンなことになってしまうので、「1000ページ進めてから命令を実行し、そのあと1000ページ戻って次の命令を読む」とかルールを決めておけばなんとかなります。

これを万能チューリングマシンと言ったりします。

チューリングさんが考えたのは理論上の、いわば仮想マシンでしたが、

のちになって実際に万能チューリングマシンにあたる、

プログラムを内蔵したノイマン型コンピュータが誕生しました。

つぎはこのコンピュータ・アーキテクチャについて書けたらいいな、と思っています。

ここまで読んでいただいてありがとうございました！