ベイマックス10 チューリングマシン1

 チューリングマシンの原理

IMG_20150212_0003

この本は以前に紹介した「ケンブリッジ・クインテット」。ここに現在のコンピュータの基礎となる考え方、チューリングマシンの説明がのっている。

わたしはこの本を読むまではチューリングの成し遂げた業績については全くと言っていいほど知らなかった。
コンピュータといえば、ノイマンの名前を思い出す程度だった。

現在のコンピュータの基本的な考えでこれ以上のものはまだ発明・発見されていないという「チューリングマシン」について、この本の説明をもとに私が理解したことを紹介してみる。

本の中のチューリングはこんなふうに説明を初めている。

「チューリングマシンには「無限に長いテープ」が入っており、それは四角いマスに区切られていて、一つひとつには「0」か「1」が入ります。テープにそって一度に一マスごと前後に動くことのできる「走査ヘッド」が、二種類の情報を読み取ります。一つはその時のマスの中の数字で(0か1)、走査ヘッドはその数字をそのままにしておくか、そこに新しい数字を書き込みむかの仕事をします。もう一つは「状態」と呼ばれるものです。状態は文字A、B、Cなどを用いて表されます。プログラムは機械が現在どのような「状態」か、また現在走査ヘッドが読み取っているテープのマス目にはどんな「数字」(0か1)が入っているかにより、次の操作を機械に指示するのです」

IMG_20150315_0002 上の図は本の中でチューリングが書いたチューリングマシンの絵。

「このコンピュータの動きは、プログラムにより決められています。プログラムとは、この機械がどんな状況であろうと、何をすべきか命令する指示書なのです。操作のどの段階でも、走査ヘッドは二つの情報を持っています。一つは現在読み取っているテープの数字が0か1ということ、もう一つは現在の「状況」です。
典型的な指示は「もしあなたの状態がAであり、読み取った数字が0なら、左へ1マス移動し、状態をBに切り替えなさいというものです。走査ヘッドが取りうる動きは次の7種類です。
1,左へ1マス動く。
2,右へ1マス動く。
3,現在のマスに書かれている数字を1に書き換える。
4,現在のマスに書かれている数字を0に書き換える。
5,現在の「状態」をそのまま保つ。
6、現在の「状態」から他の「状態」に変わる。
7、終了する。

さてこのコンピュータの動きを1+2の計算の様子でシュミレーションしてみよう。

IMG_20150325_0003

IMG_20150325_0002

 なんとも面倒な操作だろう。 1+2の計算なんて暗算でできるじゃないか、と思うが、実はすべての計算はこのような一つひとつの操作の積み重ねで出来ていることをチューリングは明らかにしたのだ。

IMG_20150321_0005

たとえば1+2の操作は、 二つのお皿がある場面を想像する。
フォークが1本のったお皿Aと二本のったお皿Bがある。 フォークはみんなで何本あるか?という計算は、 お皿Aにのっていたフォークを新しいお皿Cにのせる。 お皿Bにのっていたフォークを新しいお皿Cにのせる。 お皿Cにのっているフォークは何本ですか?その数がお皿Aとお皿Bにのっていたホークの和になる。 これが足し算の基本なのだ。 その基本の操作と同じように動いているのが、チューリングマシンなのだ。

このマシンを動かすプログラム、アルゴリズムはどう考えれば導き出されるのだろうか。そこを切り開いたのが天才チューリングの天才たるゆえんなのだろう。

足し算(加法)はわかったが、かけ算(乗法)はどうなのだろう。
次に考えてみたい。

 

 

 

 

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です