【計算機理論】あらゆる計算を実行可能な計算能力！「チューリング完全」｜情報処理問題1000本ノック
基本情報技術者試験や応用情報技術者試験、高度情報処理技術者試験（ITストラテジスト・エンベデッドなど）のアルゴリズム・計算機論分野で頻出の根幹概念。「チューリング完全」の定義と、実現に必要な最小限のプログラミング条件を攻略しましょう。
1. 【 問題 】：テクノロジ系（計算機理論・プログラミング言語論）
【 問題 】 プログラミング言語や計算モデルの計算能力に関する記述です。ある言語やシステムが「万能チューリングマシン」を模倣・シミュレートできる計算能力を備えており、十分な時間とメモリが与えられれば、原理的にどんな計算可能アルゴリズムでも実行・表現できる性質を表す用語として、適切なものはどれか。
（ア）フォン・ノイマン型（Von Neumann architecture）
（イ）チューリング完全（Turing Completeness）
（ウ）NP完全（NP-Complete）
（エ）停止性問題（Halting Problem）
2. 正解：
正解：（イ）チューリング完全（Turing Completeness）
3. 解説：「『原理的になんでも計算できる』という万能の証明！」
チューリング完全は、計算機科学の父と呼ばれるアラン・チューリング（Alan Turing）が提唱した「チューリングマシン」に由来します。
プログラミング言語がチューリング完全であるためには、**「変数の保持（メモリへの書き込み）」「条件分岐（ifなど）」「無限ループや再帰（繰返し）」**の3つの要素を備えていれば十分であるとされています。
| 分類 | 代表例 | 計算能力の特徴 |
|---|---|---|
| チューリング完全な言語 | C, Python, Java, JavaScript, WebAssembly, SQL（再帰クリCTE利用時）, HTML5+CSS3 など |
万能チューリングマシンをシミュレート可能。任意の複雑な計算を実行できる。 |
| 非チューリング完全な言語 | 正規表現（基本形）, JSON, HTML（単体）, マークダウン など | データ表現や記述に特化しており、任意の繰り返し処理や汎用計算は行えない。 |
1. 理解のコツ:
・「Pythonでできる計算は、原理的にはC言語でもJavaScriptでもすべて計算できる（計算能力の限界が同じ）」ということです。
・一見ただのマークアップ言語に見える「HTML5 + CSS3」や「Minecraftのレッドストーン回路」も、工夫すれば万能チューリングマシンを作ることができるため「チューリング完全」であることが証明されています。
2. 試験対策の視点:
・問題文に「万能チューリングマシンをシミュレート」「原理的にあらゆる計算を実行可能」「任意のアルゴリズムを表現できる」と来たら、迷わずチューリング完全を選択しましょう。
・関連概念として「チューリング完全な言語では、プログラムが永久に止まらないか判定する『停止性問題』は解決不能（不可解）」という定理も超重要です！
4. まとめ
プログラミング言語が万能チューリングマシンと同等の計算能力を持ち、あらゆる計算可能問題をシミュレートできる性質。これがチューリング完全です。計算機理論の原点となる重要テーマとして確実に覚えておきましょう！