튜링 완전

튜링 완전(turing completeness)이란 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 의미이다. 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다.

제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다.