計算完備
最小定義
以下が揃うとチューリング完全：
1.条件分岐
2.無限に伸びる記憶
3.自己参照的な制御
メモ
チューリング完全
プログラミング言語と呼ばれるためにはチューリング完全である必要がある
正規表現やSQLなどは積極的にチューリング完全にならないことを目指している これによって無限ループが原理的に発生しなくなりどんなに時間がかかろうといつかは必ず終わることを確信できる
メモリ容量に制限がない
メモリアクセスに制限がない
whileループできる
css
チューリング陥穽
機能的にはチューリング完全で任意の計算可能な機能を記述できるが、一方で実用性を失うほど記述が難しいような、プログラミング言語。計算モデル
チューリング完全を保てるギリギリまで機能を省いている