チューリングマシン

チューリングマシンの概要

チューリングマシン（Turing machine）は、アラン・チューリングによって1936年に提案された計算モデルの一つです。この機械は、計算可能性という数学的概念を理解するための基本要素となっています。チューリングマシンは、形式的な定義と直感に基づくアイデアを組み合わせて説明されることが多く、理論計算機科学において非常に重要な役割を果たします。

歴史的背景

チューリングの論文「計算可能数について──決定問題への応用」でこの機械のアイデアが示されました。同時期にエミール・ポストも独自に類似の概念を提案しましたが、チューリングの論文が機械の詳細について最も精緻に記述されています。チューリング＝チャーチのテーゼによって、その後の計算モデルが同等であることが示され、計算可能性の理論が発展しました。

機械の構成

チューリングマシンは以下の三つの主要な要素から成ります：
1. テープ - 無限に長いテープは、記号の列を格納するための場所です。テープ上の各位置には記号が書き込まれ、読み取られます。
2. ヘッド - テープ上を左右に移動し、記号の読み書きを行う部品です。
3. 有限オートマトン - 現在の状態に基づいてヘッドの動作を決定する機能を持つものです。

さらに、以下のソフトウェア要素も必要です：

• - テープに書かれる記号の種類（有限個）
• - 初期状態におけるテープの記号列
• - 状態遷移規則群

動作の原理

チューリングマシンの動作は、現在の状態とヘッドが位置しているテープの記号に基づいて決定されます。具体的には、次のような操作が行われます：

• - 現在位置に新しい記号を書き込む、またはそのままとする。
• - ヘッドを左右に一つ動かすか、動かさない。
• - 次の状態に遷移する。

このように、チューリングマシンは計算過程を通じて「受理状態」に至ることを目的としています。この受理状態は、特定の決定問題の解答を示すものであり、計算可能性の理論に基づいています。

現実の計算との関連性

実際のコンピュータはチューリングマシンの原則に従った動作をします。実用的な電子計算機は、チューリングマシンに比べて遥かに複雑であり、限られた記憶領域を持ちますが、理論的には解くことができる問題の範囲は同じです。このため、計算理論ではアルゴリズムがチューリングマシン上の手続きと同じものとして扱われます。

形式的定義

チューリングマシンは次の七つの要素によって定義されます：

• - 状態の有限集合 Q
• - 記号の有限集合 Γ
• - 空白記号 b
• - 入力字母の有限集合 Σ
• - 遷移関数 δ
• - 初期状態 q_init
• - 受理状態 q_acc

このように定義されたチューリングマシンは、与えられた入力に対して特定の出力を生成することができます。

変種と計算クラス

チューリングマシンにはいくつかの変種があります。例えば、決定性と非決定性の区分、さらに万能チューリングマシンは任意の他のチューリングマシンを模倣できる能力を持っています。

これまでの研究により、チューリングマシンの理解は計算理論全体に大きな影響を与えており、コンピュータ科学の基礎教育には欠かせないテーマとなっています。

もう一度検索