C の前に：チューリング機械*

チューリング機械とは

現在の（ノイマン型）コンピュータの抽象的なモデルとしてチューリング機械（Turing machine）と言うものがあります。

チューリング機械はテープとヘッドから成ります。

テープは十分に長く、枡目が無数に並んでいるものを考えます。それぞれの枡目に書ける記号の種類は予め決めておきます。これはメモリの抽象化であり、実際のメモリ（を容量無限大にしたもの）は記号を 0 と 1 だけに選んだテープと考える事ができます。また 1 バイト毎に区切るとすれば、記号は 0x00 ～ 0xFF を選んだ事になります。

ヘッドはテープの上を動き回って読み書きする機械です。ヘッドは内部状態を持ちます、つまり幾つかの事を憶えておく事ができます。ヘッドがどう動くかは、テープの現在位置から読んだ記号と内部状態によって決まります。これは CPU の抽象化であり、内部状態は全レジスタの値が何であるかに相当します。

足し算する

例えば、テープ上の記号に 0x00 ～ 0xFF を選び、内部状態として A、B、C を持つヘッダが

のルールで動くとします。このとき

の状態から動作を始めると、今ヘッダがいる位置の記号（値）は 0x00 でないので最初のルールが適用され

となります。内部状態が B の場合のルールは一つだけで、これを適用し

となって、未だ 0x00 でないので同じ動作が繰り返されます。

今度は 0x00 なので二つ目のルールが適用され、

となってチューリング機械は停止します。

このチューリング機械は、初めの位置の数を 1 ずつ右へ移動する事により足し算を行うものとなっています（0x02 + 0x03 = 0x05）。より複雑な内部状態とルールを定める事で、実際のコンピュータと同じ計算能力を持つもの（万能チューリング機械）をも構成できます。

計算モデル

チューリング機械はコンピュータをそのままモデル化したものですが、それは「入力を一定のルールに従って処理する」という計算モデルの一例に過ぎません。

現在ではλ計算、コンウェイのライフゲーム、マジック：ザ・ギャザリング等多くのシステムが計算モデルとして万能チューリング機械をシミュレートできる、つまりコンピュータと同等の計算能力を持つ事が知られています。