튜링 기계

앨런 튜링이 1936년에 처음 제안한 계산 모형인 튜링 기계에 대해 알아보자. 가장 간단한 계산 모형인 유한 상태 기계와 유사하지만 그와 달리 제한 없는 메모리를 가진 튜링 기계는 범용 컴퓨터를 훨씬 더 정확하게 모사한다. 튜링 기계는 실제 컴퓨터가 할 수 있는 모든 작업을 수행할 수 있다. 그럼에도 불구하고 튜링 기계도 특정 문제를 해결할 수는 없다. 실제로 이러한 문제는 계산의 이론적 한계를 넘어서는 문제이다.

튜링 기계 모형은 무한 테이프를 무한 메모리로 사용한다. 그 테이프에 적힌 기호를 읽고 쓸 수 있고 테이프 위를 움직이며 다닐 수 있는 테이프 헤드가 있다. 처음에 테이프에는 입력 문자열만 들어 있고 다른 부분은 비어 있다. 기계가 정보를 저장해야 하는 경우 이 정보를 테이프에 기록할 수 있다. 기계가 쓴 정보를 읽기 위해 기계는 헤드를 그 정보 위로 되돌아 갈 수 있다. 기계는 출력을 생성하기로 결정할 때까지 계산을 계속한다. 인식 및 거부 출력은 지정된 인식 및 거부 상태에 진입하여 얻을 수 있다. 인식 또는 거부 상태에 들어가지 않으면 영원히 멈추지 않고 계속 진행된다. ¹

유한 상태 기계와 튜링 기계 사이의 차이점은 다음과 같다.

1. 튜링 기계는 테이프에 쓰기와 읽기가 모두 가능하다.
2. 읽기-쓰기 헤드를 왼쪽과 오른쪽으로 모두 움직일 수 있다.
3. 테이프가 무한하다.
4. 거부 및 수락에 대한 특수 상태가 즉시 적용된다.

언어 의 원소가 될 자격을 검사하기 위해 튜링 기계 을 도입하자. 입력이 에 속하면 이 인식하고, 그렇지 않으면 거부하도록 만드려고 한다. 을 더 잘 이해하기 위해 당신이 수백만 개의 글자가 적힌 엄청 긴 입력 문자열 한가운데에 서 있다고 생각해보자. 당신의 목표는 입력 문자열이 에 속하는 지를 알아내야 한다. 즉, #로 구분된 두 문자열이 동일한지를 알아내야 한다. 문자열을 모두 외우기에는 입력이 너무 길지만, 당신은 입력 위를 앞뒤로 움직이며 그 위에 표식을 남기는 것은 허용된다. 뻔한 전략으로는 #로 나눠진 두 부분을 번갈아 오가며 그들이 일치하는 지를 확인하는 것이다. 각 문자가 반대편의 어디에 대응되는 지는 표식을 남기며 확인하면 된다.

이런식으로 을 설계하면 된다. 은 읽기-쓰기 헤드로 입력 문자열을 여러 번 오고 간다. 오고 갈 때마다 # 기호의 양쪽에 있는 문자 중 하나와 비교한다. 이미 검사된 문자를 파악하기 위해 검사한 기호를 지운다. 모든 기호를 지우면 모든 기호가 성공적으로 일치한다는 의미이며 은 인식 상태가 된다. 불일치가 발견되면 거부 상태가 된다. 요약하면 의 알고리즘은 다음과 같다.

“입력 문자열 에 대해

1. 테이프 위를 오고 가면서 # 기호 양쪽의 대응하는 위치로 이동하여 동일한 기호가 포함되어 있는지 확인한다. 그렇지 않거나 #이 발견되지 않으면 거부한다. 확인한 기호를 지우면서 다음에는 어떤 기호가 대응하는지 추적한다.
2. 왼쪽에 있는 기호를 모두 지웠으면 # 오른쪽에 남은 기호가 있는지 확인한다. 기호가 남아 있으면 거부하고, 그렇지 않으면 수락한다.”

다음 그림은 입력 011000#011000에서 시작한 의 테이프의 변화 과정 중 일부다.

주

1. 멈추지 않고 계속 진행된다는 것은 튜링의 정지 문제에서 비중있게 다루어진다. ↩