チューリング完全（Turing Completeness）とは何か

「チューリング完全」とは、ある計算システム（プログラミング言語やハードウェアなど）が、 「アラン・チューリングが考案した理論上のコンピュータ（チューリングマシン）と同じ計算能力を持っている」 ことを指す言葉です。

簡単に言うと、 「十分な時間とメモリがあれば、どんなに複雑な計算問題でも解くことができる能力」 のことです。

1. アラン・チューリングとの関係

この言葉は、イギリスの数学者 アラン・チューリング（1912-1954） に由来します。

彼は1936年に、現在のコンピュータの動作原理のモデルとなる「チューリングマシン」という理論上の機械を提唱しました。これは「テープに書かれた記号を読み書きし、状態を変化させる」という極めて単純な仕組みですが、彼はこのマシンで「計算可能なあらゆる問題が解ける」ことを証明しました。

現代のコンピュータやプログラミング言語が「チューリング完全である」と言うとき、それはアラン・チューリングが定義したその万能な計算能力を備えていることを意味します。

あるシステムがチューリング完全であるためには、一般的に以下の要素が必要とされます。

データの保存（メモリ）: 情報を記録し、後で取り出せること。

条件分岐（If文）: 「もしAならBをする」という判断ができること。

繰り返し（ループ・再帰）: ある処理を何度も繰り返せること（または無限に続けられること）。

この3つが揃っていれば、どんなにシンプルな言語であっても、スーパーコンピュータと同じ論理的な計算が可能です。

プログラミング言語: C言語、Python、Java、JavaScriptなどはすべてチューリング完全です。

意外なもの:

Excelの数式: 最新のExcel（LAMBDA関数など）はチューリング完全です。

ライフゲーム: 先ほどのドキュメントにあった通り、単純なルールですが複雑な計算が可能です。

マインクラフトのレッドストーン: ゲーム内でコンピュータを自作できるのは、この仕組みがチューリング完全だからです。

マジック・ザ・ギャザリング: カードゲームのルールの組み合わせによって、理論上は計算機を構築できることが証明されています。

「チューリング完全」という基準があるおかげで、私たちは 「この新しい言語でどんなプログラムが作れるか？」 と悩む必要がなくなりました。

もしその言語がチューリング完全であれば、C言語で作れるものはPythonでも作れるし、JavaScriptでも作れるという 「計算能力の等価性」 が保証されるからです。あとは、書きやすさや実行速度といった「使い勝手」の差があるだけになります。