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