位置と内容

ウィキペディア

チューリングマシン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/01/06 13:28 UTC 版)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "チューリングマシン" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2011年12月)

チューリングマシン

チューリングマシン (英: Turing machine) は、アラン・チューリングが「計算可能性」に関する議論のために提示した抽象機械である^[1]。

歴史

チューリングの「計算可能数について──決定問題への応用」（1936年）において提示された^[2]。同様なものを同年にエミール・ポスト (Emil Post) も独立に発表している^[3]。構想の理由、動機についてはポストの論文が明確だが、機械自体に関する記述はチューリングの論文が詳細である。次いで、同時代に提示された他の計算モデルも計算可能性の理論からは同等であることが確認され、チューリング＝チャーチのテーゼはそれらを「計算可能」の定義とすることを提唱した。

概要

ここでは非形式的（直感的）に述べる。理論的には形式的に述べる必要がある。

チューリングマシンには、いわゆるハードウェアに相当するものとして、

1. その表面に記号を読み書きできるテープ。長さは無制限（必要になれば順番にいくらでも先にシークできる^{[注 1]}）とする
2. テープに記号を読み書きするヘッド
3. ヘッドによる読み書きと、テープの左右へのシークを制御する機能を持つ、有限オートマトン

がある。

また、ソフトウェアに相当するものとして、以下がある。

1. テープに読み書きされる有限個の種類の記号
2. 最初から（初期状態において）テープにあらかじめ書かれている記号列
3. 有限オートマトンの状態遷移規則群。詳細は次で述べる

この有限オートマトンの状態遷移規則は、その有限オートマトンの「現在の状態」（内部状態）と、ヘッドがテープの「現在の場所」から読み出した記号の組み合わせに応じて、次のような動作を実行する。

• テープの「現在の場所」に新しい記号を書き込む（あるいは、現在の記号をそのままにしてもよい）
• ヘッドを右か左に一つシークする（あるいは、移動しなくてもよい）
• 有限オートマトンを次の状態に状態遷移させる（同じ状態に遷移してもよい）

さらに、この有限オートマトンには（一般的な有限オートマトンの「受理状態」と同様な）「受理状態」がある。計算可能性理論的には、決定問題の2種類の答えに対応する、2種類の受理状態が必要である^{[注 2]}。

現実の計算との関係

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

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

形式的な定義

この節では、チューリングマシンを形式的（formal）に記述する。

チューリングマシン

チューリングマシン M は次の7つ組で定義される：

$${\displaystyle M=\langle Q,{\mathit {\Gamma }},b,{\mathit {\Sigma }},\delta ,q_{\mathrm {init} },q_{\mathrm {acc} }\rangle \,.}$$

ウィキメディア・コモンズには、チューリングマシンに関連するメディアがあります。