TL;DR
ある計算の仕組みが、万能チューリングマシンと同じ計算能力を持つこと。計算完備ともいう。
チューリング完全（チューリングかんぜん、英語: Turing-complete）とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全あるいは計算完備であるという。
仕組み
万能チューリングマシンとは、ほかのどんなチューリングマシンでも模倣できるチューリングマシンのことである。
万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。（エミュレータの原理）
あるシステムがチューリング完全であれば、チューリングマシンで解ける問題は、理論上そのシステムでも解ける。
例
Python、JavaScript、C などのプログラミング言語や、セル・オートマトンのような計算モデルはチューリング完全である。
自分の理解
個人的には、難解プログラミング言語の界隈でよく聞く単語である。データサイエンスでも聞く気がする。
万能チューリングマシンが何なのか、最初はよく分からなかった。ChatGPT に「サルでも分かるチューリング完全」と聞いてみたが、あまりにもざっくりした説明だった。Qiita のまとめ記事のほうが分かりやすい。ストレンジコードを読みたい。
関連
- チューリングマシン
- 難解プログラミング言語