튜링 완전

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

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

• 튜링 기계 (정의에 따라)
• 타입 없는 람다 대수 및 적절한 타입시스템을 가진 대부분의 람다 대수 변종 (처치튜링명제에 따라)
• 제한 없는 재작성체계
• 우리가 일반적으로 사용하는 사실상 모든 일반목적 프로그래밍 언어는 튜링 완전하다. 좀 더 정확하게는:
  • 제한 없는 조건부 GOTO 문과 (필요에 따라 그 크기를 임의로 키울 수 있는) 메모리를 읽고 쓸 수 있는 모델은 튜링 완전하다.
  • GOTO 문을 제한 없는 while 문으로 바꿔도 튜링 완전하다. ("제한이 없다"는 말은 루프가 시작되기 전에 루프가 도는 횟수가 결정되거나 하면 안 된단 소리다.)
  • 많은 함수형프로그래밍언어는 람다 대수와 동형이다.
• 많은 난해한 프로그래밍 언어는 위의 조건을 충족하지 않는데도 튜링 완전하게 설계되곤 한다. (이를테면 Muriel 같은 것) 따라서 이 동네에서는 튜링 완전하면서도 굉장히 예측 불허인 언어를 설계하는 것이 일반적이다.

그 밖에 보통 튜링 완전하다고 예상하기 쉽지 않은 것들:

• Rule 110과 라이프 게임을 포함한 각종 셀룰러 오토마타
• 마인크래프트 레드스톤 회로 (…)