Turing Completeness

발생

Turing Completeness(튜링 완전성) 정리

정의

튜링 완전하다는 것은 어떠한 계산 시스템으로 튜링 머신과 동일한 계산 능력을 가질 수 있다는 것이다.

진정으로 튜링 완전하려면 튜링이 처음 튜링 머신(a-machine)에 대해 정의 했을 때와 같이 무한한 테이프 즉 무한한 저장 공간을 필요로 한다. 하지만 무한한 저장 공간을 가진다고 가정 후 튜링 머신과 동일한 계산 능력을 가질 경우에는 느슨한 의미에서 튜링 완전(Loose Turing Complete) 하다고 한다.

위에서 말하는 계산 시스템이란 어떤 규칙에 따라 입력을 받아 출력을 만들어내는 장치를 의미한다. 이는 계산을 수행 할 수 있는 모든 이론, 실용적 구조 모두 계산 시스템 인 것이다.

조건

튜링 완전한 최소 조건이 공식적으로 정해진 사항은 아니지만 통용되고 있는 사항들은 아래와 같다.

  1. 조건적 분기
    1. e.g., if, while, goto 등
    2. 어떤 입력된 상태에 따라 동작을 달리 할 수 있어야한다.
  2. 무한 저장 공간
    1. e.g., 테이프가 무한한 튜링 머신, 스택 제한이 없는 시스템, 동적 메모리 할당에 제한이 없는 언어 등
    2. 이론적으로 저장 공간을 무한하게 확장 시킬 수만 있다면 해당 조건을 충족한다.

결론

정의와 조건에 부합한다면 해당 시스템은 튜링 완전하다 할 수 있고 튜링 완전한 예시는 아래와 같다.

  • 프로그래밍 언어 (Python, C/C++, Java, Haskell 등)
  • 계산 이론 (Lambda Calculus, Recursive Functions, Markov Algorithms 등)
  • 기타 (Typescript의 타입 시스템, C++ Template, Java Generic, 마인크래프트 레드스톤, CSS 등)

Day-61

tech