チューリングマシン

Difference Engineは機械式の加算機であったが、より一般的に、機械的な計算手順でどのような問題が解きうるのかという研究がなされ、1936年に、Alan Turing氏は、計算する機械のモデルとして次のような概念的な機構を考えた。

無限に長いテープがあり、それに書かれたデータを読んだり、新しい値を書き込んだりするヘッドがある。そして、ヘッドから読まれた"1/0"に応じて状態遷移を行う有限のステートマシン(現在の状態とヘッドからの入力の"1/0"に応じて次の状態が定義されており、状態の数が有限の回路)があり、その状態に応じて、ヘッドを1ビット分、右や左に動かし、データを読んだり書いたりする。そして、最終状態と定義した状態に辿り着いたら、問題に対する答えがテープ上に書かれているという機械である。

Stanford Encyclopedia of Philosophyに書かれている足し算を行うTuring Machineの例を次に紹介する。

まず、数値の表現であるが、整数NをN+1個の"1"の連続で表わし、終わりに"0"を1個付ける。そして初期状態では、ヘッドは第一オペランドの左端の"1"の位置にあるとする。これを3＋4の場合について示したのが、次の図である。そして、足し算の結果であるが、答えは7であるので、8個の"1"の連続したブロックの右に"0"があり、ヘッドは左端の"1"の位置にあるようになれば良い。

この処理を実行するためのTuring Machineの状態遷移図は、つぎのようになる。

丸で描かれたS0からS4が状態であり、矢印がそれぞれの状態での入力に応じた状態の遷移を表わしている。矢印に付けられた( )は入力と動作を表わし、左側の0、1は、ヘッドからの入力であり、右側はヘッドがどのような動作を行うのかを示している。ここでヘッドの動作の→、←は矢印の方向へのヘッドの移動を示し、0や1は、ヘッドは移動せずそのシンボルへの書き換えを示す。

Turing Machineは、最初はS0状態にあり、上側の矢印の(1、→)は"1"がヘッドから読まれると、ヘッドは→方向に1ポジション移動し、次の状態はS0状態に戻る。一方、S0状態でヘッドから"0"が読まれると(0、1)の矢印を辿り、その位置のシンボルを"1"に書き換え、次の状態はS1状態となる。

上記の遷移図での3＋4の動きを説明すると、まず、S0状態で"1"を読みヘッドを右へ動かす動作が4回続き、第一オペランドの終わりの"0"を読むと、それを"1"に書き換えてS1状態に遷移する。そして、S1状態では"1"を見ると左にヘッド動かし、初期ヘッド位置の左の"0"を検出すると、ヘッドを右に動かしS2状態に遷移する。S2状態では、まず、初期ヘッド位置にあった"1"を読むので、これを"0"に書き換え、次にこの"0"を読んでヘッドを右に動かしてS3状態に遷移する。そしてS3状態では、その右隣の"1"を"0"に書き換え、次にヘッドを右に移動して、最終状態のS4状態に遷移する。

簡単に言うと、第一オペランドの終わりの"0"を"1"に書き換えて、第一オペランド(N)と第二オペランド(M)を連結することにより足し算を行うが、数値の表現がN+1個とM+1個の"1"の連続であるので、これではN+M+3個の"1"の連続になってしまう。これをS2とS3状態を使って左端の二つの"1"を"0"に変換することにより、N+M+1個の"1"の連続に変換している。

二つの"1"のブロックを繋いだだけで、読者は、これが足し算かと思われるかも知れないが、この計算の前に、2進数を－1しながら0になるまで"1"を書き、N+1個の"1"のブロックを作る処理を加え、足し算の後に"1"の並びを1つづつ消しながら＋1して個数を数える処理を付け加えれば2進数の加算も実現できる。

但し、このような計算方法が効率が良い訳は無く、チューリングマシンはコンピュータとしては実用にされていないが、計算可能な問題は、状態遷移テーブルとテープの長さに制約が無ければ、チューリングマシンで解くことが出来ることが証明されている。

これは、処理時間を別とすれば、チューリングマシンでは解けないような問題をとくことができるコンピュータは作れないということで、コンピュータの研究は、問題を速く解くという性能と、プログラムの作りやすさ、それを少ないハードウェアで経済的に実現するという方向に向かうことになる。

なお、チューリングマシンでできることと同等のことができることをTuring Completeと呼び、現代の汎用コンピュータはTuring Completeであるが、黎明期のコンピュータや専用コンピュータではそうでないものも存在する。