튜링 완전

Turing completeness. 계산 모델의 한 분류. 어떤 계산 모델이 튜링 기계로 나타낼 수 있는 프로그램을 모두 나타낼 수 있고 그 역도 성립한다면 그 모델은 튜링 완전, 즉 튜링 기계와 동일한 능력을 가진다.

기본적으로 우리가 사용하는 사실상 모든 계산은 튜링 완전한 모델로 표현 가능하다고 볼 수 있다. 이보다 더 넓은 범위의 개념은 초계산(hypercomputation)이며 실제로 구현할 수 있으리라는 추측도 있긴 하지만 아직 현실적인 얘기는 아니다.