4月4日「チューリングマシン」
シリーズ「ぼんやりコンピュータ」コンピュータについて、なんとなく文章にしてみます。一応コンピュータの歴史にそって書いていき、最終的に現在のコンプーターの話にもっていく予定です。
今日は「チューリング・マシン」の話です。
数学者アラン・チューリングさんは、まだ存在しない未来の計算機について考えていました。
「理論計算機科学」理論上の計算機の性能について、数学モデルで計算機を構築することができれば、
たとえ今現在は存在しない未来のコンピューターであっても、その能力の上限が計算できるはず……!
そのために作成された仮想計算機モデル、それが「チューリング・マシン」です。
チューリングマシンは「無限の長さのテープ」と「そのテープのどこでも読み書きできるヘッド」から構成されているマシーンです。
最近の人は「磁気テープ」になじみがないのでこの説明ではピンとこないかもしれません。「無限にページがあるノート」のどこでも読み書きできる「鉛筆と消しゴムを持った人」の組み合わせを想像してもらえればいいと思います。
この組み合わせで、まあだいたいの問題は解けそう、というのは直感的にわかるんじゃないかなと思います。
無限ページのノートなので大量の数字をこの人に渡すことができますし、無限ページのノートなので大量の数字を書くこともできます。記憶力がおいつかなければメモをとることもできます。
「一生計算しても計算が終わらない命題」とか、解けない問題もあるにはありますが、現在のコンピューターにできるようなことはこのチューリングマシンが全部できる、とみなしていいそうです。
なんでもできるということは、チューリングマシン上で「チューリングマシンを動かす」ということもできるということ……?
これができるんですね。あらかじめノートに命令をならべておくわけです。命令には「現在のページを読みなさい」とか、「現在のページに数字を書きなさい」とか「何ページ前に進みなさい」とかそういうのをあらかじめて決めて、チューリングマシンの中の人に教えておく必要があります。
「命令のページ」と「命令を実行するページ」が同じだと、命令がどんどん書き換わってヘンなことになってしまうので、「1000ページ進めてから命令を実行し、そのあと1000ページ戻って次の命令を読む」とかルールを決めておけばなんとかなります。
これを万能チューリングマシンと言ったりします。
チューリングさんが考えたのは理論上の、いわば仮想マシンでしたが、
のちになって実際に万能チューリングマシンにあたる、
プログラムを内蔵したノイマン型コンピュータが誕生しました。
つぎはこのコンピュータ・アーキテクチャについて書けたらいいな、と思っています。
ここまで読んでいただいてありがとうございました!