チューリング完全
(個人的に)Esolang 界隈でよく聞く単語。あとデータサイエンス? チューリング完全(チューリングかんぜん、英語: Turing-complete)とは、計算理論において、ある計算のメカニズムが万能チューリングマシンと同じ計算能力をもつとき、その計算モデルはチューリング完全あるいは計算完備であるという。
遷移規則をうまく構成することで、「いかなるチューリングマシンであろうとも、それを模倣することが可能なチューリングマシン(万能チューリングマシン)」が可能である。
万能チューリングマシンは、与えられた、別のチューリングマシンを記述した記号列と、そのチューリングマシンへの入力記号列を読みこみ、それに従って動く。(エミュレータの原理)
ChatGPT に聞いてみる。
Q: サルでも分かるチューリング完全
基礎
まず、計算とは何かを考えます。計算は、数学的な問題やその他の種類の問題を解決する過程です。
例えば、2つの数の足し算や、ある条件を満たす数字を見つけることなどが計算に含まれます。
チューリングマシン
チューリングマシンは、英国の数学者アラン・チューリングによって1936年に提案された理論上の計算モデルです。 これは無限に長いテープ、テープ上を移動する読み書きヘッド、一連の状態、そしてその状態に基づいてテープに何を書き込むか、ヘッドをどのように動かすかを決定するルールで構成されています。
チューリングマシンは、非常に単純なルールを使って任意の計算可能な問題を解く能力を持っています。
チューリング完全性
ある計算システムがチューリング完全であるとは、そのシステムがチューリングマシンと同じ計算能力を持つことを意味します。
つまり、理論上、そのシステムを使用して解くことができるすべての問題は、チューリングマシンでも解くことができます。
これにはプログラミング言語(例えばPython、JavaScript、Cなど)や、特定の計算モデル(例えばセル・オートマトン)が含まれます。
あまりにもざっくりとした説明だな…radish_miyazaki.icon
Qiita に良さそうなまとめがあった。