こんにちは，学生エンジニアの迫佑樹(@yuki_99_s)です．
昔々(とはいえ100年前くらい)あるところに，チューリングさんと呼ばれるおじさんがいました．
彼はイギリスの数学者で，チューリングマシンや，チューリングテストと呼ばれるものを考案しました．
また，戦争時に敵国の暗号化された文書を解読してしまうなど，すごい逸話が残っているおじさんです．
この人が作ったチューリングマシンと呼ばれるものがあるのですが，今回はそれについて解説してみようと思います．
例えで理解するチューリングマシン
チューリングマシンとは，コンピュータのモデルとなる仮想的な機械のことです．
少し例を出しながら解説をしていきます．
映画のフィルムを想像してみてください．
このようなものです．
このフィルムの一枚一枚には，なんらかのデータが入っています．
そして，これを映画のスクリーンに映したいときはどうするでしょうか？
映画のスクリーンに，このフィルムにかかれているデータを読み込んで，投影してあげますね．
映画は，複数の絵を連続で移すことによって動きを表現しているので，はじめの0.1秒は1枚目で，はじめの0.2秒は2枚目を移す… といったことを決めておく必要があります．
つまり，この矢印は，今どのデータを読み込んでいるのかを確認するためのものといえます．
この単純なシステムだと，必要なデータの分だけフィルムの枚数を用意して上げる必要があります．
100枚の絵からなる映画があれば，100枚のフィルムを用意する必要があります．
では，このフィルムがとても短かったらどうしましょう？
これでも，先ほどと同じ映画を上映することが出来ます．
その方法を紹介します．
0.1秒目は，フィルムが全く同じです．
そして，投影し終わったら，先ほどと同じく矢印の場所を移動させて，別のデータを読み込みます．しかし，動く前に，データを消して，別のデータを入れてあげます．
すると，0.2秒目は以下のようになります．
そして，次は，矢印を左に動かして，先程入れた別のデータをスクリーンへ映してあげます．
スクリーンへ移すのが完了すると，0.3秒目に行く前に，同じくデータを書き換えます．
すると，0.3秒目は以下のように，しっかりスクリーンへ正しいデータを映し出すことが出来ます．
これを繰り返していくと，長いフィルムを使って映画を上映するのと全く同じことを実現することが出来ます．
つまり，まとめると
-
単純に右へ右へと参照するデータの位置を動かすのではなく，フィルムの状態によって参照位置を右にずらすか左へずらすかを変える
-
データを読み込むだけでなく，書き換える機能を矢印に付ける
この２つが可能になれば，限られた場所で様々なことが出来るようになるということです．
実は，これこそがチューリングマシンの仕組みそのままだったりします．
チューリングマシンで具体的に計算してみる
先程，フィルムに例えてチューリングマシンの仕組みを紹介しました．
はじめに，チューリングマシンはコンピュータのモデルと言いました．
コンピュータが出来ることは，計算や記憶など様々ですが，今回は実際に計算を扱ってみましょう．
それでは，具体的に2+1を計算してみようと思います．
このように，フィルムにデータが入ってるとします．
今回，2+1を計算して見るので，2本の棒と1本の棒を+マークの左右においてあげました．
チューリングマシンでは，どこのデータを読み取るかを示しているこの矢印のことを，ヘッドと呼びます．
この時，このフィルムの他にもう一つ必要なものが，あります．
それが，機能表と呼ばれるものです．
先程，映画のフィルムの例で出したとおり，ヘッド(矢印)は左右に動いたり，データを書き換えたりします．
そのため，どんな状態でどのようなデータが書いてある時，ヘッドをどっちにうごかしてどんなデータを書き込めばいいのかを指定してあげる必要があります．
先程の例だと，以下のような感じでヘッドの動作を指定します．
これをいちいち文章で指定すると大変なことになるので，機能表と呼ばれる表にしようって考えたわけですね．
機能表は，したい処理によって決められています．
今回のように，足し算をしたかった場合，以下のような機能表になります．
いきなり暗号みたいになりましたが，1つずつ説明していきます．
まずは，読み込みについてです．
画像で言う以下の部分ですね．
ここは，読み込んだ文字を表しています．
つまり，ヘッドがIを指していると，機能表のIのところを読めば良いわけです．
また，ヘッドが，空っぽのところを指している場合，機能表のΛのところを読みます．
Λは，機能表では空っぽっていう意味が使うので覚えておいてください．
そして，さっきの状態の時に，もしの状態であれば，
のところを読んであげるわけです．
では，その場所に書いてある，ってなんでしょうか？
は，「どんな文字を書き込んで，どの方向にヘッドを動かして，どんな状態に変化させるか」を表しています．
つまり，というのは，「空っぽのデータを書き込んで，右側に動き，状態を
にする」という意味になります．
これで必要な知識はすべて揃いました．
あとは実際に計算してみるのみです！
今回は，初期状態を，始まりを一つ目のIとします．
機能表より，「空っぽのデータを書き込んで，右側に動き，状態をにする」となります．
これに従って，動作させると，以下のようになります．
状態がになって，元の場所に書いてあったIが空っぽになっていますね．
では次の機能表を見ていきましょう．
今回は，状態がとなったので，「状態が
で，データはIが書き込まれている時」に行う動作をします．
機能表より，Iを書き込んで，状態をに変えて，右へ動きます．
同様にして，動かしていくと，次のようになっていきます．
細かい動きは省略しますが，全く同じなので，少し長くなってしまいますが，トレースしてみてください．
実際に自分でやってみると，かなり理解が深まります．
そして，最後の動作を機能表に基づいて行ってあげると，状態が「!」となります．
状態が「!」となったら，動作は終わりです．
この通り，Iが3つ並んだ状態で終了しており，2+1を計算することが出来たと思います．
これをよく見てみると，「+の左側にあるものを全部，+の右側に持っていってあげてる」だけということになりますね．
ということで，このチューリングマシンの機能表は，「+の左側にあるものを全部+の右側に持っていってあげることによって，足し算を計算している」ということになります．
少し手順が長くなってしまいましたが，少しだけチューリングマシンの動作に対するイメージがついたのではないでしょうか？
チューリングマシンとチューリング完全
先程の過程を見ていて，この機能表というものが，「動作の司令を与えている」ということがわかると思います．
動作の手順を与えるものは，プログラミングの世界でアルゴリズムと呼ばれます．
機能表もアルゴリズムも動作の司令を出すもの…
つまり，機能表=アルゴリズムとなるわけです．
よって，このチューリングマシンがしっかり最後に停止状態となり，なにかしらの結果が得られれば，アルゴリズムが存在するため，現在，コンピュータでその問題を解くことが可能ということになります．
こんなよくわからない記号から出来ていたものが，「コンピュータである問題を解くことが出来るか」という判定に使われているなんておもしろくないですか？
最後に
今回はかなり図が多くなってしまいました．
実際に処理を追う必要があり，サラッと読むだけでは理解しにく買ったかと思います．
申し訳ありません．
ですが，確実にトレースするととても良くわかるので，是非一度，機能表を使いながら足し算の処理を行ってみることをおすすめします！
▼期間限定で無料配布中▼
- 経済的自立を果たす10のステップ
- 時給10円から年商10億円に至る道のり
- 最短で0→1を立ち上げる起業術
- お金持ちになる5つのルール
- すぐに実行できる即金マニュアル
無料特典を受け取るか迷っている方は、こちらの記事「真面目」でも「頭がいい人」でもお金持ちになれないたった1つの理由」をお読みください。
