Turing Machine

complexity

概要

アラン・チューリングが計算可能性の議論のために考案した抽象機械 (1936). 現代のコンピューターが行っている”計算”は全てこのチューリングマシンで表すことができる.

構成

• 左右に無限に伸びる文字が書かれたテープ
• 文字を読み取った後左右に動く事のできるヘッダ
• ヘッダを制御する制御器

からなる

定義

形式的な定義は以下のようになる. Turing Machine $‘M‘$ は

$‘M=(Q,\Sigma ,\Gamma ,q_0,A,\delta )‘$

• $‘Q‘$: 状態の集合
• $‘\Sigma ‘$: 入力アルファベット
• $‘\Gamma ‘$: テープアルファベット($‘\Sigma \subset \Gamma ‘$)
• $‘q_0‘$: 開始状態($‘q_0\in Q‘$)
• $‘A‘$: 受理状態($‘A\subset Q‘$)
• $‘\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}‘$: 遷移関数

遷移関数はある状態 $‘q_a‘$ から文字を1文字読み取って状態 $‘q_b‘$ へ遷移しヘッドを左右どちらかに動かすという動作を集めたもの.

状態遷移図

Turing Machineの動作の様子も状態遷移図に対応している. 例として $‘0,1‘$ のみからなる文字列$‘\in L‘$ が回文($‘w{w}^R,w\in \{0,1{\}}^{\ast }‘$)かどうかを判定するTMの状態遷移図は以下のようになる.

チューリング機械の万能性

TMはあらゆる「計算」をTMの動作に還元することが出来る

参考文献

• Microsoft PowerPoint - 01fa.ppt
• チューリングマシン - Wikipedia