スマートフォン用の表示で見る

Turing Machine

コンピュータ

Turing Machine

ちゅーりんぐましん

概要

英国数学者アラン・チューリングが仮想機械として考案した。

チューリングマシンは1本のテープと、このテープ上の記号を読み書きするためのヘッドを一つ持つだけの仮想機械である。チューリング・マシンには有限個の「状態」があって、各時刻でそのうち何れか一つの状態をとることができる。

数学的に書けば以下の様になる。

  • TM =(Q,¥Sigma,¥Gamma,¥delta,q_0,H)
Q
状態の集合
¥Sigma
初期状態のテープに書かれているアルファベット
¥Gamma
テープに書かれるアルファベット,¥Sigma ¥subseteq ¥Gamma
¥delta
遷移関数(Q¥times ¥Gamma ¥rightarrow Q¥times ¥Gamma ¥times D)
D=¥{L,S,R¥}
ヘッドの移動方向
q_0
開始状態,q_0 ¥in Q
H
受理状態,H ¥subseteq Q

計算可能という点ではnテープTuring Machine,確率的Turing Machine,非決定性Turing Machine,量子版Turing Machineと同様の能力を持つ(入力に対する計算時間及び使用するテープの長さ等には違いがある)。

現実のコンピュータチューリングマシンのサブセットといえる。コンピュータのメモリが有限であるのにたいしてチューリングマシンのテープ長には制限がない。概念的にはほぼ等価といえる。