튜링 머신: 계산 가능성의 경계를 설명하는 추상 기계
튜링 머신은 유한한 제어 상태, 기호를 읽고 쓸 수 있는 테이프, 테이프 위를 이동하는 헤드로 계산을 표현하는 추상 모델이다. 물리 CPU의 설계도가 아니라 어떤 문제에 알고리즘이 존재하는지 논의하기 위한 정밀한 기준이다.
튜링 머신은 유한 제어와 확장 가능한 테이프로 알고리즘의 계산 가능성을 모델링한다.
한 단계에서 하는 일
현재 상태와 헤드가 읽은 기호에 따라 새 기호를 쓰고, 왼쪽이나 오른쪽으로 이동하며, 다음 상태로 바뀐다. 상태와 테이프 알파벳은 유한하지만 테이프는 필요한 만큼 사용할 수 있다고 가정한다. 계산의 임시 기억은 이 테이프에 저장된다.
예를 들어 양의 정수를 1의 반복인 단항 표현으로 쓰면 3은 111이다. 오른쪽으로 이동하며 마지막 1 뒤의 빈칸을 찾고 그곳에 1을 쓴 뒤 멈추는 기계는 값을 하나 증가시킨다.
Input tape: ... blank 1 1 1 blank blank ...
Head starts on the first 1.
State q_scan:
read 1 -> write 1, move Right, stay q_scan
read blank -> write 1, move Right, enter q_accept
Output tape: ... blank 1 1 1 1 blank ...
이 간단한 예에서는 현재 상태와 읽은 기호만으로 다음 행동이 정해진다. 더 복잡한 기계는 표시용 기호를 써 이미 처리한 위치를 기록하고 여러 번 왕복할 수 있다. 입력 길이에 비례해 항상 한 번만 읽는 모델은 아니다.
멈춤과 수락은 다르다
언어 판정에서는 수락 상태와 거절 상태를 구분한다. 입력이 언어에 포함되면 수락하고 포함되지 않으면 거절하며 모두 멈추는 기계가 결정기다. 포함되지 않는 입력에서 영원히 실행할 수도 있는 기계는 인식기가 될 수 있지만 항상 결정을 주지는 않는다.
기계의 상태와 규칙은 유한한 문자열로 부호화할 수 있다. 그래서 다른 튜링 머신의 설명과 입력을 받아 실행을 모사하는 보편 튜링 머신을 생각할 수 있다. 프로그램도 데이터로 다룰 수 있다는 관점이 중요한 결과를 만든다.
여러 테이프, 다른 이동 규칙 같은 변형은 계산 가능한 함수의 범위가 같을 수 있지만 실행 단계 수의 효율은 달라질 수 있다. 계산 가능성의 동등함과 복잡도의 동일함은 같은 주장이 아니다.
무한 테이프는 실제 컴퓨터가 무한 메모리를 가진다는 말이 아니다. 유한한 입력의 계산에 필요하면 얼마든지 더 사용할 수 있다는 이상화다. 실제 하드웨어의 저장 한계와 이론의 알고리즘 존재 여부는 다른 층의 질문이다.
Church–Turing 논지는 효과적으로 계산 가능한 절차를 튜링 계산으로 포착한다는 원리다. 수학적 모델끼리의 동등성 정리와는 구분해야 한다. 이 모델을 통해 일반적인 정지 판정의 불가능성이나 P·NP 같은 계산 복잡도 개념을 엄밀하게 정의할 수 있다.
복잡도를 분석할 때는 테이프의 입력 부호화와 한 단계의 연산을 정해야 한다. 같은 숫자를 단항으로 쓰면 입력 길이가 숫자 값에 비례하고, 이진으로 쓰면 로그에 비례한다. 표현 선택을 숨기면 실행 단계 수의 비교도 달라진다.