【ちゅーりんぐかんぜん】
チューリング完全 とは？
最終更新:
💡 計算できる範囲が同じ。何でも解けるとは違う
チューリングマシンの計算を模擬できる計算能力を持つこと。時間と記憶容量の上限を置かない理論上の性質で、すべての問題を解けることや、実用的な速さを保証するものではありません。
📌 このページのポイント
ひよこ チューリング完全の「完全」って何？
ペンギン先生 チューリングマシンという計算モデルが行える計算を模擬できる、という意味だよ。どんな問題でも解けるというお墨付きではなく、計算できる範囲を比べる言葉なんだ。
ひよこ チューリングマシンはどんな機械？
ペンギン先生 記号を記録するテープ、読み書きするヘッド、有限個の状態と規則で表す理論上の機械だよ。規則に従って記号を書き換え、ヘッドを動かし、状態を変える。万能チューリングマシンはほかの機械の規則を読み、それを模擬できるんだ。
ペンギン先生 一般的なプログラミング言語の計算能力を説明するときに使うよ。ただし理論上は必要な記憶容量や時間を使えると仮定する。実際のパソコンは有限だから、大きな計算を必ず最後まで実行できるわけではないんだ。
ひよこ 停止するかどうかも計算できる？
ペンギン先生 ひよこ チューリング完全なら性能も高い？
ペンギン先生 表現力の話だから、速さや安全性の評価とは別だよ。同じ計算ができても所要時間や書きやすさは違う。目的に合う言語を選ぶには、実装・資源・利用する機能も確かめよう。
もっと詳しく知りたい人へ
Excelもチューリング完全なの？
Microsoft Researchは、再帰などを表現できるLAMBDAの導入でExcelの数式言語がチューリング完全になったと説明しています。すべての古い数式やバージョンが同じという意味ではなく、実際の実行には再帰やメモリなどの制限もあります。
まとめ：ざっくりこれだけ覚えればOK！
「チューリング完全」って出てきたら「理論上、チューリングマシンの計算を模擬できる性質」と思えばだいたいOK！資源の上限を置かない理論上の比較だよ。
📖 おまけ：英語の意味
「Turing Complete」 ＝ チューリング完全
💬 アラン・チューリングが1936年の論文で示した計算モデルに由来します。単にテープ・ヘッド・状態があるだけで、すべての機械が万能になるわけではありません。