튜링 기계

튜링 기계의 작동 방식을 묘사하는 그림

튜링 기계 (Turing machine)란 컴퓨터의 실행과 저장에 관한 추상적인 모델로서 1936년에 앨런 튜링이 알고리즘에 대한 엄밀한 수학적 정의를 위해 도입한 개념이다. 이 개념은 컴퓨터 과학 이론에서 널리 사용되고 있는데, 특히 계산 복잡도 이론과 계산이론에서 아직도 널리 사용되고 있다. 튜링 기계가 논리나 수학에서 사용될 수 있는 체계의 뭉뚱그려진 개념까지도 모두 온전히 묘사할 수 있다는 명제는 처치-튜링 명제로 알려져 있다. 또한 임의의 튜링 기계를 모방할 수 있는 기계를 범용 튜링 기계라 하며 이는 현대 컴퓨터의 모델이 되었다.

도입

튜링 기계라는 개념이 처음 등장한 것은 1936년 튜링이 발표한 논문 “계산가능수와 결정문제에 대한 응용에 관하여(On Computable Numbers, with an Application to the Entscheidungsproblem)”이다. 튜링은 계산가능수를 “유한한 방법으로 십진수 표현을 얻어낼 수 있는 실수”라고 정의하고, 튜링 기계를 통해 계산가능수를 계산하는 방법을 논문에 제시했다.

정의

튜링 기계의 개념은 '한정된 숫자의 기호 가운데 하나를 가질 수 있는 칸이 무한히 늘어서 있는 종이의 내용을, 엄밀하게 정의된 절차에 따라 규칙적으로 바꿈으로써 계산을 행하는 사람'에 관한 발상을 바탕으로 한다. 거기서 ‘계산을 수행하는 사람’은 튜링 기계의 ‘유한한 조건만 다룰 수 있는 기계’와 대응되는데, 기계가 가질 수 있는 조건들은 m-배형(m-configuration)이라 한다.

튜링 기계에 테이프를 넣으면 한 번에 한 칸씩만 읽을 수 있다. 이 때 이 칸에 기록되어 있는 기호는 읽힌 기호이다. ‘읽힌 기호’는 그 순간 튜링 기계가 직접 의식한 기호이지만, ‘읽힌 기호’에 따라 자기 자신의 m-배형을 변경함으로써 이미 읽었던 기호들도 기억할 수 있다. 따라서 튜링 기계의 동작은 m-배형과 작동 시작부터 읽었던 기호들에 의해 결정된다. 튜링은 이를 기계의 배형이라고 정의했다.

기계의 배형에 따라 기계는 여러 가지 동작을 취하는데, 이 동작은 행동표(table of behavior)로 결정되며, 기계는 행동표가 나타내는 알고리즘에 따라 작동한다. 그리고 ‘어떤 단계에서의 기계의 움직임, 읽은 칸의 개수, 테이프에 적힌 모든 기호의 배열 그리고 m-배형’은 그 단계에서의 총배형(complete configuration)을 나타내고, 총배형에 따른 기계와 테이프의 변화는 동작(move)이라고 부른다.

행동표에는 가능한 모든 m-배형과 읽힌 기호에 대해 ‘현재 칸에 기록할 기호’, ‘기계의 이동 방향과 거리’, 그리고 ‘기계의 m-배형 변화’가 제시되어 있다. 그리고 행동표에서 기계의 작동을 중지한다는 명시를 할 때까지 작동해 계산가능수를 계산하거나, 작동을 중지하지 않고 무한히 계산가능수열(정수들의 무한수열)을 계산한다.

계산가능수를 계산하는 튜링 기계의 예

m-배형	기호	행동	변경할 m-배형
A	빈칸	오른쪽으로 한 칸 이동	A
A	1	오른쪽으로 한 칸 이동	B
B	1	오른쪽으로 한 칸 이동	B
B	빈칸	1 기록 후 오른쪽으로 한 칸 이동	C
C	1	오른쪽으로 한 칸 이동	D
C	빈칸	왼쪽으로 한 칸 이동	D
D	빈칸	이동하지 않고 작동 중지	D
D	1	1 삭제 후 작동 중지	D

이 행동표에 따라 작동할 때 튜링 기계는 1진수(1의 연속)로 표현된 두 자연수의 합을 1진수로 표현한다.

계산가능수열을 계산하는 튜링 기계의 예

m-배형	기호	행동	변경할 m-배형
A	빈칸	0 기록 후 오른쪽으로 한 칸 이동	B
B	빈칸	오른쪽으로 한 칸 이동	C
C	빈칸	1 기록 후 오른쪽으로 한 칸 이동	D
D	빈칸	오른쪽으로 한 칸 이동	A

이 행동표에 따라 작동할 때 튜링 기계는 0과 1을 번갈아 가며 무한히 출력한다.

성질

계산가능수나 계산가능수열을 계산하는 알고리즘이 존재하면 그에 상응하는 튜링 기계가 존재한다. 하지만 계산가능수나 계산가능수열을 계산할 수 없는 튜링 머신도 존재한다. 아래 행동표는 마틴 데이비스가 예로 든 튜링 기계의 행동표이다.

m-배형	기호	행동	변경된 m-배형
A	0	오른쪽으로 한 칸 이동 후 1 기록	B
B	1	왼쪽으로 한 칸 이동 후 0을 1로 수정	C
C	1	오른쪽으로 한 칸 이동 후 1을 0으로 수정	B

튜링 기계가 이 행동표에 따라 작동할 경우 0과 1 사이를 무한히 왕복하는데, 이런 기계를 순환적(circular)이라고 부르며, 계산가능수열을 출력하는 튜링 기계는 비순환기계(circle-free machine)라고 부른다.

정지 문제는 ‘임의의 튜링기계가 순환적인지 비순환적인지 판단’하는 문제이다. 그리고 1936년 튜링은 정지 문제는 튜링 머신에서 판정 불가능함을 증명했다.

범용 튜링 기계

범용 튜링 기계(universal Turing machine)는 임의의 튜링 기계에 대해 그 기계의 행동을 모방할 수 있는 기계를 뜻하며, 튜링이 정지 문제를 해결하기 위해 도입했다.

범용 튜링 기계는 내장된 튜링 기계에 따라 수행하는 계산이 달라지는데, 이는 현대 컴퓨터의 특징을 잘 드러낸다. 범용 튜링 기계를 하드웨어에 비유하면 범용 튜링 기계에 내장된 기계는 소프트웨어에 비유할 수 있다.

튜링은 1947년에 이 기계를 다음과 같이 묘사했다.

이런 종류의 기계는 단 하나만 있어도 모든 일을 수행할 수 있다는 점이 확인된다. 이것은 사실 얼마든지 다른 모든 기계의 모델이 될 수도 있다. 이 특수한 기계는 범용 기계라고 불리어야 할 것이다.

참고

• 정지 문제
• 처치-튜링 명제

참고자료

너무 많이 알았던 사람. 데이비드 리비트 저. 고중숙 역.