>>「真面目」でも「頭がいい人」でもお金持ちになれないたった1つの理由とは

チューリングマシンを宇宙一わかりやすく解説してみる

こんにちは,学生エンジニアの迫佑樹(@yuki_99_s)です.

昔々(とはいえ100年前くらい)あるところに,チューリングさんと呼ばれるおじさんがいました.

http://www.fbs.osaka-u.ac.jp/labs/skondo/saibokogaku/Turingphotos/photo.jpg

彼はイギリスの数学者で,チューリングマシンや,チューリングテストと呼ばれるものを考案しました.

また,戦争時に敵国の暗号化された文書を解読してしまうなど,すごい逸話が残っているおじさんです.

この人が作ったチューリングマシンと呼ばれるものがあるのですが,今回はそれについて解説してみようと思います.

例えで理解するチューリングマシン

チューリングマシンとは,コンピュータのモデルとなる仮想的な機械のことです.

少し例を出しながら解説をしていきます.

映画のフィルムを想像してみてください.

f:id:McG:20161028171116p:plain

このようなものです.

このフィルムの一枚一枚には,なんらかのデータが入っています.

f:id:McG:20161028171709p:plain

そして,これを映画のスクリーンに映したいときはどうするでしょうか?

映画のスクリーンに,このフィルムにかかれているデータを読み込んで,投影してあげますね.

映画は,複数の絵を連続で移すことによって動きを表現しているので,はじめの0.1秒は1枚目で,はじめの0.2秒は2枚目を移す… といったことを決めておく必要があります.

f:id:McG:20161028172753p:plain

つまり,この矢印は,今どのデータを読み込んでいるのかを確認するためのものといえます.

この単純なシステムだと,必要なデータの分だけフィルムの枚数を用意して上げる必要があります.

100枚の絵からなる映画があれば,100枚のフィルムを用意する必要があります.

では,このフィルムがとても短かったらどうしましょう?

f:id:McG:20161028174059p:plain

これでも,先ほどと同じ映画を上映することが出来ます.

その方法を紹介します.

0.1秒目は,フィルムが全く同じです.

f:id:McG:20161028174252p:plain

そして,投影し終わったら,先ほどと同じく矢印の場所を移動させて,別のデータを読み込みます.しかし,動く前に,データを消して,別のデータを入れてあげます.

f:id:McG:20161028204221p:plain

すると,0.2秒目は以下のようになります.

f:id:McG:20161028204237p:plain

そして,次は,矢印を左に動かして,先程入れた別のデータをスクリーンへ映してあげます.

スクリーンへ移すのが完了すると,0.3秒目に行く前に,同じくデータを書き換えます.

f:id:McG:20161028204347p:plain

すると,0.3秒目は以下のように,しっかりスクリーンへ正しいデータを映し出すことが出来ます.

f:id:McG:20161028204654p:plain

これを繰り返していくと,長いフィルムを使って映画を上映するのと全く同じことを実現することが出来ます.

つまり,まとめると

  • 単純に右へ右へと参照するデータの位置を動かすのではなく,フィルムの状態によって参照位置を右にずらすか左へずらすかを変える

  • データを読み込むだけでなく,書き換える機能を矢印に付ける

この2つが可能になれば,限られた場所で様々なことが出来るようになるということです.

実は,これこそがチューリングマシンの仕組みそのままだったりします.

チューリングマシンで具体的に計算してみる

先程,フィルムに例えてチューリングマシンの仕組みを紹介しました.

はじめに,チューリングマシンはコンピュータのモデルと言いました.

コンピュータが出来ることは,計算や記憶など様々ですが,今回は実際に計算を扱ってみましょう.

それでは,具体的に2+1を計算してみようと思います.

このように,フィルムにデータが入ってるとします.

今回,2+1を計算して見るので,2本の棒と1本の棒を+マークの左右においてあげました.

f:id:McG:20161028210502p:plain

チューリングマシンでは,どこのデータを読み取るかを示しているこの矢印のことを,ヘッドと呼びます.

この時,このフィルムの他にもう一つ必要なものが,あります.

それが,機能表と呼ばれるものです.

先程,映画のフィルムの例で出したとおり,ヘッド(矢印)は左右に動いたり,データを書き換えたりします.

そのため,どんな状態でどのようなデータが書いてある時,ヘッドをどっちにうごかしてどんなデータを書き込めばいいのかを指定してあげる必要があります.

先程の例だと,以下のような感じでヘッドの動作を指定します.

f:id:McG:20161028211257p:plain

これをいちいち文章で指定すると大変なことになるので,機能表と呼ばれる表にしようって考えたわけですね.

機能表は,したい処理によって決められています.

今回のように,足し算をしたかった場合,以下のような機能表になります.

f:id:McG:20161028212324p:plain

いきなり暗号みたいになりましたが,1つずつ説明していきます.

まずは,読み込みについてです.

画像で言う以下の部分ですね.

f:id:McG:20161028212416p:plain

ここは,読み込んだ文字を表しています.

つまり,ヘッドがIを指していると,機能表のIのところを読めば良いわけです.

f:id:McG:20161028213038p:plain

また,ヘッドが,空っぽのところを指している場合,機能表のΛのところを読みます.

Λは,機能表では空っぽっていう意味が使うので覚えておいてください.

f:id:McG:20161028213241p:plain

そして,さっきの状態の時に,もしq_1の状態であれば,q_1のところを読んであげるわけです.

f:id:McG:20161028213746p:plain

では,その場所に書いてある, \Lambda Rq_0ってなんでしょうか?

f:id:McG:20161028213842p:plain

 \Lambda Rq_0は,「どんな文字を書き込んで,どの方向にヘッドを動かして,どんな状態に変化させるか」を表しています.

f:id:McG:20161028214641p:plain

つまり, \Lambda Rq_0というのは,「空っぽのデータを書き込んで,右側に動き,状態を q_0にする」という意味になります.

f:id:McG:20161028215520p:plain

これで必要な知識はすべて揃いました.

あとは実際に計算してみるのみです!

今回は,初期状態を q_0,始まりを一つ目のIとします.

f:id:McG:20161028220018p:plain

機能表より,「空っぽのデータを書き込んで,右側に動き,状態を q_2にする」となります.

これに従って,動作させると,以下のようになります.

f:id:McG:20161028220238p:plain

状態が q_2になって,元の場所に書いてあったIが空っぽになっていますね.

では次の機能表を見ていきましょう.

f:id:McG:20161028220436p:plain

今回は,状態が q_2となったので,「状態が q_2で,データはIが書き込まれている時」に行う動作をします.

f:id:McG:20161028220612p:plain

機能表より,Iを書き込んで,状態を q_2に変えて,右へ動きます.

f:id:McG:20161028220824p:plain

同様にして,動かしていくと,次のようになっていきます.

細かい動きは省略しますが,全く同じなので,少し長くなってしまいますが,トレースしてみてください.

実際に自分でやってみると,かなり理解が深まります.

f:id:McG:20161028234212p:plain

f:id:McG:20161028234219p:plain

f:id:McG:20161028234224p:plain

f:id:McG:20161028234231p:plain

f:id:McG:20161028234237p:plain

f:id:McG:20161028234243p:plain

f:id:McG:20161028234249p:plain

f:id:McG:20161028234255p:plain

f:id:McG:20161028234301p:plain

f:id:McG:20161028234308p:plain

f:id:McG:20161028234314p:plain

f:id:McG:20161028234323p:plain

f:id:McG:20161028234329p:plain

f:id:McG:20161028234335p:plain

f:id:McG:20161028234341p:plain

f:id:McG:20161028234347p:plain

f:id:McG:20161028234354p:plain

f:id:McG:20161028234359p:plain

そして,最後の動作を機能表に基づいて行ってあげると,状態が「!」となります.

状態が「!」となったら,動作は終わりです.

f:id:McG:20161028234404p:plain

この通り,Iが3つ並んだ状態で終了しており,2+1を計算することが出来たと思います.

これをよく見てみると,「+の左側にあるものを全部,+の右側に持っていってあげてる」だけということになりますね.

ということで,このチューリングマシンの機能表は,「+の左側にあるものを全部+の右側に持っていってあげることによって,足し算を計算している」ということになります.

少し手順が長くなってしまいましたが,少しだけチューリングマシンの動作に対するイメージがついたのではないでしょうか?

チューリングマシンとチューリング完全

先程の過程を見ていて,この機能表というものが,「動作の司令を与えている」ということがわかると思います.

動作の手順を与えるものは,プログラミングの世界でアルゴリズムと呼ばれます.

機能表もアルゴリズムも動作の司令を出すもの…

つまり,機能表=アルゴリズムとなるわけです.

よって,このチューリングマシンがしっかり最後に停止状態となり,なにかしらの結果が得られれば,アルゴリズムが存在するため,現在,コンピュータでその問題を解くことが可能ということになります.

こんなよくわからない記号から出来ていたものが,「コンピュータである問題を解くことが出来るか」という判定に使われているなんておもしろくないですか?

最後に

今回はかなり図が多くなってしまいました.

実際に処理を追う必要があり,サラッと読むだけでは理解しにく買ったかと思います.

申し訳ありません.

ですが,確実にトレースするととても良くわかるので,是非一度,機能表を使いながら足し算の処理を行ってみることをおすすめします!