イギリスの数学者、アラン・マティソン・チューリングが1936(昭和11)年に発表した論文「計算可能数についての決定問題への応用」に書かれている仮想機械(計算機模型)のこと。

目次 概要 特徴 電子計算機 チャーチの定立 チューリングコンプリート

概要

チューリングマシンはすなわち、計算機を数学的に検証、議論する上で必要となる、理想化、単純化された仮想的な計算機である。

この理論では、無限に長いテープと、そのテープに情報を読み書きするヘッドとを持った、いくつかの簡単な基本操作によって動く機械が想定されており、その機械の有限回の操作で数学の形式体系と等価な働きをすることを導いた。

特徴

つまりチューリングマシンは、少なくとも次のような装置を持つ。

1. 無限に長いテープ
2. そのテープに情報を読み書きするヘッド
3. 計算機内の状態を保持するメモリー

そして、計算機内の状態と、ヘッドで読み取った情報の組み合わせに応じて、次のいずれかの動作を行なう。

• ヘッドの位置の情報を読み取る
• ヘッドの位置に情報を書き込む
• 計算機内の状態を変更する
• ヘッドを左右のいずれかに一つ分移動する

以上の動作を、計算機内の状態が停止になるまで繰り返して実行する。

電子計算機

チャーチの定立

現在使われている電子計算機(コンピューター)、つまりノイマン型電子計算機は、理論的にはチューリングマシンの原理に準じていると言える。

チューリングマシンが持つ記憶媒体の容量は無限なのに対して現実の計算機のそれは有限ではあるが、理論上はチューリングマシンが解ける問題と、計算機が解ける問題はほぼ同等である、とされている。これはチャーチの定立(Charch's thesis、チャーチのテーゼ)という考えによる。

チューリングコンプリート

人間がチューリングマシンに問題を解かせる場合、テープに問題を記号として記述して与え、チューリングマシンはその問題を読み取りながらテープを書き換えつつ、結果を出力する。

この「記号」は、電子計算機ではプログラミング言語に対応するが、チューリングマシンの動作の全てを記述できるものを「チューリングコンプリート」なプログラミング言語である、という。

基本的に、現在使われているプログラミング言語はチューリングコンプリートである。

リンク

用語の所属
オートマトン
用語の所属
アラン・マティソン・チューリング
チューリングコンプリート
ノイマン型

[再検索] [戻る]