TL;DR チューリングマシンとは抽象化した計算機である
まだ卒業してないから俺も高校生だし(震え声
チューリングマシンとは
チューリングマシンとは、wikiのinformal description(簡略化した説明)によると 「無限のテープとヘッド、状態登録機、有限の命令を書いた表」 を備えた機械のことです。
つまりその辺にあるテープと、紙+鉛筆+消しゴムがあればチューリングマシンとして使えます(紙と鉛筆、消しゴムを使って状態登録機、ヘッドの代わりとします)。
テープと紙、鉛筆、消しゴムだけで計算機械ができるとは驚きですね。
テープ
テープはマス目で区切られていてそれぞれアルファベットもしくは空文字(アルファベットと区別される特殊な文字)が書かれています。アルファベットだけでなくひらがなでも漢字でもなんでも書いてokです。
ただしアルファベット以外を使うにしろ、それらと明確に区別される特殊な空文字を設定する必要はあります。
マス目は横1列に並んでいて縦には並んでないものとします。テープの初期状態は設定可能です。空文字で埋まってる必要はありません。というか計算させるには初期状態が必要なので必ず設定しなければなりません。
ちょっと補足
プログラミングしてるみなさんはお気づきかと思いますが、テープは0と1のみ書き込み可能としても、アルファベット使用可能でも本質的になんら変わりません。アルファベットを8bitで表してしまえば0と1のみに還元できるので明らかです。以下ではアルファベット使用可能としてます。
ヘッド
ヘッドはマス目の上にあり、テープ上を1回につき右か左に1マス動かすことができます。
また、ヘッドは自身の下にあるテープのマス目の文字を読み込むこと、書き込むことができます。ただし読み込んだ文字をヘッドが保持することはできません。
状態登録機
「状態」が書き込まれたものです。紙に「状態: x」と書くスペースがあればそれでokです。この「状態」が計算するためのキモです。プログラムでいうと行番号にあたります。
命令表
命令表とは要するにプログラムです。命令表は次のような形式の命令が並んだ表です。
X、Yは「ヘッドの下のマスに書き込む」「ヘッドを右または左に1マス分動かす」「状態をyにする」のどれか1つまたは複数です。
ただし複数使うときは「書き込み→ヘッドの移動→状態変更」の順で書かなければなりません(ヘッドの移動、状態変更のみのときは「ヘッドの移動→状態変更」という具合でない部分は詰めて考えてください)。
具体的に命令をひとつ書いてみましょう。
「状態42のとき、読み込んだ文字が0ならばヘッドの下のマスにaを書き込み、ヘッドを右に一つ動かし、状態を3にする」
gotoとifを使ったプログラムと思えば簡単ですね。
チューリングマシンを使った計算
チューリングマシンを使った計算は…理論上掛けなくはないのですが、とても面倒です。掛け算の実装すら面倒です。気が向いたら書きます。
