튜링 완전(turing completeness)이란 어떤 프로그래밍 언어나 추상 기계가 튜링 기계와 동일한 계산 능력을 가진다는 의미이다. 이것은 튜링 기계로 풀 수 있는 문제, 즉 계산적인 문제를 그 프로그래밍 언어나 추상 기계로 풀 수 있다는 의미이다.
제한 없는 크기의 기억 장치를 갖는 기계를 만드는 것이 불가능하므로, 진정한 의미의 튜링 완전 기계는 아마도 물리적으로 불가능할 것이다. 그러나, 제한 없이 기억 장치의 크기를 늘려갈 수 있다고 가정할 수 있는 물리적인 기계 혹은 프로그래밍 언어에 대해서는, 느슨하게 튜링 완전하다고 간주한다. 이런 맥락에서, 요즘 나온 컴퓨터들은 튜링 완전하다고 여겨지고 있다.
역사
찰스 배비지의 해석기관(1830년대)이 최초의 튜링 완전 머신으로 간주된다.
19세기 말 레오폴트 크로네커는 계산 가능성의 개념을 공식화하면서 원시 귀납적 함수를 정의하였다.
계산성의 실질적 개념은 괴델의 불완전성 정리와 함께 시작하면서 곧 떨어져 나왔다.
예시
의도되지 않은 튜링 완전성
몇몇 소프트웨어는 의도치 않게 튜링 완전성을 갖추기도 한다.
같이 보기
외부 링크
