튜링 완전

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

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

 역사 
찰스 배비지의 해석기관(1830년대)이 최초의 튜링 완전 머신으로 간주된다.

19세기 말 레오폴트 크로네커는 계산 가능성의 개념을 공식화하면서 원시 귀납적 함수를 정의하였다.

계산성의 실질적 개념은 괴델의 불완전성 정리와 함께 시작하면서 곧 떨어져 나왔다.

 예시 
 파스칼
 C++
 XSLT
 의도되지 않은 튜링 완전성 
몇몇 소프트웨어는 의도치 않게 튜링 완전성을 갖추기도 한다.
 C++의 템플릿
 자바의 제네릭
 Typescript의 타입 시스템
 x86의 MOV 명령어
 마인크래프트
 시티즈: 스카이라인
 CSS

 같이 보기 
 알고리즘 정보 이론
 촘스키 위계
 처치-튜링 논제
 계산 가능성 이론
 가상화

 외부 링크 
 c2.com

분류:계산 이론
분류:프로그래밍 언어 이론
분류:튜링 기계