【ちゅーりんぐかんぜん】
チューリング完全 とは？
💡 「何でも計算できます」の理論的お墨付き
📌 このページのポイント
ひよこ チューリング完全って、何が「完全」なの？
ペンギン先生 「計算能力が完全に揃ってる」という意味だよ。チューリングマシンという理論上の万能計算機と同じことができるなら、その言語やシステムは「チューリング完全」と呼ばれるんだ
ひよこ チューリングマシンって何？
ペンギン先生 無限に長いテープと、テープを読み書きするヘッドと、状態を持つ制御装置でできた仮想的な機械だよ。シンプルな仕組みだけど、理論上はどんな計算でもできるんだ
ひよこ プログラミング言語は全部チューリング完全なの？
ペンギン先生 ひよこ チューリング完全だと何でも解けるの？
ペンギン先生 理論上はね。ただし「理論上解ける」と「現実的に解ける」は別物だよ。時間やメモリが足りなかったり、そもそもチューリングマシンでも解けない「停止問題」のような問題もあるんだ。チューリング完全は万能に見えて、実は限界もあるんだよ
まとめ：ざっくりこれだけ覚えればOK！
「チューリング完全」って出てきたら「理論上どんな計算でもできる能力がある」と思えればだいたいOK！
📖 おまけ：英語の意味
「Turing Complete」 ＝ チューリング完全
💬 イギリスの数学者アラン・チューリングが1936年に提案した「チューリングマシン」に由来するよ。計算できるものの限界を定義した概念なんだ