【基礎理論】計算の限界を定義する！「決定性チューリングマシン」｜情報処理問題1000本ノック

現在のコンピュータが「何が計算できて、何が計算できないのか」を数学的に定義したモデルです。究極にシンプルな構造ながら、現代のスーパーコンピュータと同じ計算能力を持つといわれる理論上の機械を攻略しましょう。

1. 問題：計算モデルの基本概念

【 問題 】 内部状態を持つ制御部、読み書き可能な無限に長いテープ、およびテープヘッドから構成される計算モデルです。ある状態において一つの入力記号を読み取ったとき、次に行う動作（記号の書き換え、ヘッドの移動、状態遷移）が一意に決定されるモデルを何と呼ぶでしょうか？

ア、決定性有限オートマトン
イ、決定性チューリングマシン
ウ、非決定性プッシュダウンオートマトン
エ、万能チューリングマシン

2. 正解：計算理論に関する正解

正解： イ、決定性チューリングマシン（Deterministic Turing Machine）

3. 解説：「迷いがない」というアルゴリズムの原点

英国の数学者アラン・チューリングによって考案された、アルゴリズムの概念を数式化したモデルです。

【図解：チューリングマシンの3つの要素】

■ テープ：データを記録する無限のメモリ。
■ ヘッド：テープの記号を読み書きし、左右に移動する装置。
■ 制御部（状態遷移図）：現在の状態と読み取った記号から、「次に何をするか」を決めるプログラム。

★ 「決定性」とは？
・同じ状況（現在の状態と読み込んだ記号）であれば、次の動作が必ず一つに決まっていることを指します。
・多くの一般的なプログラムやアルゴリズムは、この決定性モデルに従っています。

[ 関連用語：チャーチ＝チューリングのテーゼ ]
★ 「アルゴリズムによって計算可能なものは、すべてチューリングマシンによっても計算可能である」という説です。この理論により、チューリングマシンで解けない問題（停止性問題など）は、どんなに性能が良い将来のコンピュータでも解けないことが証明されています。

1. 理解のコツ: 「1マス1文字しか入らないテープに、マニュアル通りに文字を書き込んだり消したりしながら動く機械」です。非常に原始的ですが、この単純な動きを組み合わせるだけで、現在のAIもデータベースも原理上は再現できてしまいます。
2. 試験対策の視点: 「読み書き可能な無限のテープ」という言葉が出たらチューリングマシンの合図です。「次の動作が一意に決まる」なら決定性、複数の候補から選択できるなら非決定性（P≠NP予想などで登場）と区別しましょう。

---

4. まとめ

「次に行う動作が一意に決定される計算モデル」。これが決定性チューリングマシンです。私たちが普段使っているコンピュータの論理的な本質であり、計算の世界のルールを定める最も重要な土台の一つです。