チューリング完全性とは何ですか？

コンピュータサイエンスでは、 チューリング完全性は、データを操作する規則のシステムの分類です。それは、チューリング機械の発明者であるコンピュータ科学者アランチューリングにちなんで名付けられました。

たとえば、プログラミング言語やCPU命令セットは、データにアクセスしてデータを変更する正式なルールシステムの例です。その規則がチューリングの仮想計算機をシミュレートするために使用できる場合、その規則は「チューリング完了」であると言われる。チューリング完全システムは、あらゆる可能な計算またはコンピュータプログラムを実行できることが数学的に証明され得る。

チューリングの完全なシステムの例は、アランチューリング教授のアロンゾ教会によって開発されたラムダ計算です。