チューリングマシン

バーチャルマシンです。

僕が考えたバーチャルマシンは？

エバリュエーションマシン、カウンティングマシン、ドラゴンマシン、空転金融原子炉・第二の月


チューリングマシン (英: Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。

1936年にイギリスの数学者アラン・チューリングの論文「計算可能数について──決定問題への応用」で発表された。同様の考え方は同年にエミール・ポスト (Emil Post) も独自に発表している。構想の理由、動機についてはポストの論文が明確だが、仮想機械自体に関する記述はチューリングの論文が詳細である。

チューリングの仮想機械は、

1. 無限に長いテープ
2. その中に格納された情報を読み書きするヘッド
3. 機械の内部状態を記憶するメモリ

で構成され、内部状態とヘッドから読み出した情報の組み合わせに応じて、次の動作を実行する。

• ヘッド位置のテープに情報を書き込む
• 機械の内部状態を変える
• ヘッドを右か左に一つ移動する

上の動作を、機械は内部状態が停止状態になるまで反復して実行し続ける。

実際の計算機の基本的動作も、突き詰めて考えれば、このチューリング機械の原理に従っているといえる。実用上の電子計算機はチューリング機械よりも遥かに複雑であり、また有限の記憶領域しか持たないが、「計算機で原理上解ける問題」は「チューリング機械で解ける問題」と同じであるといわれている。このため計算理論では、算法あるいは算譜をチューリング機械と同一視する（チャーチ＝チューリングのテーゼ）。

数学の形式体系はすべてこの仮想機械の動作に還元できるといわれている。この機械で決定できない命題も存在する。例えば与えられたチューリング機械が停止するかどうかをチューリング機械で決定することはできない（停止性問題）。これはゲーデルの不完全性定理の別表現とみなすことができる。