3.14 다중 테이프 튜링 기계와 단일 테이프 환원

1. 다중 테이프 튜링 기계의 정의

다중 테이프 튜링 기계(Multi-Tape Turing Machine)는 $k \geq 2$ 개의 독립적인 테이프와 $k$ 개의 독립적인 읽기/쓰기 헤드를 가진 튜링 기계의 변형이다.

1.1 형식적 정의

$k$ -테이프 튜링 기계 $M$ 은 다음과 같이 정의된다:

$M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$

여기서 전이 함수 $\delta$ 의 정의역과 치역이 확장된다:

$\delta: (Q \setminus \{q_{\text{accept}}, q_{\text{reject}}\}) \times \Gamma^k \rightarrow Q \times \Gamma^k \times \{L, R, S\}^k$

$\delta(q, a_1, a_2, \ldots, a_k) = (q', b_1, b_2, \ldots, b_k, D_1, D_2, \ldots, D_k)$ 의 해석:

현재 상태가 $q$ 이고, 각 테이프의 헤드가 읽은 기호가 $a_1, a_2, \ldots, a_k$ 일 때,
상태를 $q'$ 로 전이하고,
각 테이프의 현재 셀에 $b_1, b_2, \ldots, b_k$ 를 쓰고,
각 헤드를 방향 $D_1, D_2, \ldots, D_k \in \{L, R, S\}$ 로 이동한다.

여기서 $S$ (Stay)는 헤드가 이동하지 않는 것을 나타낸다.

1.2 표준적 구성

가장 일반적인 구성은 다음과 같다:

테이프 1: 입력 테이프(Read-Only). 입력 $w$ 가 기록되어 있으며 변경되지 않는다.
테이프 2 ~ $k-1$ : 작업 테이프(Work Tape). 계산의 중간 결과를 저장한다.
테이프 $k$ : 출력 테이프(Write-Only, 선택적). 계산 결과를 기록한다.

2. 다중 테이프의 이점

2.1 프로그래밍의 편의성

다중 테이프는 알고리즘의 설계를 크게 단순화한다. 서로 다른 데이터를 별도의 테이프에 저장하고 독립적으로 접근할 수 있으므로, 단일 테이프에서 필요한 복잡한 기호 표시(Marking)와 위치 추적(Position Tracking)이 불필요해진다.

예를 들어, 이진 덧셈에서 피가수, 가수, 결과를 세 테이프에 분리하면, 세 헤드를 동기적으로 이동시키며 각 자릿값의 덧셈을 수행할 수 있다.

2.2 시간 효율의 향상

단일 테이프 기계에서 테이프의 한 위치에서 다른 위치로 헤드를 이동시키는 데 $O(n)$ 단계가 소요되나, 다중 테이프 기계에서 서로 다른 테이프의 헤드가 독립적으로 위치할 수 있으므로 이 오버헤드가 제거된다.

3. 단일 테이프 환원 정리

정리: $k$ -테이프 튜링 기계 $M$ 이 시간 $t(n)$ 에 입력을 처리하면, $M$ 과 동일한 언어를 인식하는 단일 테이프 튜링 기계 $S$ 가 존재하여, $S$ 는 시간 $O(t(n)^2)$ 에 입력을 처리한다.

이 정리는 다중 테이프가 단일 테이프에 비해 이차적(Quadratic) 시간 감소만을 제공하며, 계산 가능성의 관점에서 두 모델이 동등함을 보장한다.

3.1 증명의 구성

$k$ -테이프 기계 $M$ 을 시뮬레이션하는 단일 테이프 기계 $S$ 를 구성한다.

테이프 내용의 인코딩: $S$ 의 단일 테이프에 $M$ 의 $k$ 개 테이프의 내용을 인터리브(Interleave)하여 저장한다. $M$ 의 $i$ 번째 테이프의 $j$ 번째 셀의 내용은 $S$ 의 테이프의 $(k \cdot j + i)$ 번째 셀에 저장된다. 또한, 각 테이프의 현재 헤드 위치를 나타내기 위해 추가적인 표시 기호(예: 기호 위에 점을 찍은 $\dot{a}$ )를 사용한다.

테이프 알파벳의 확장: $S$ 의 테이프 알파벳은 $\Gamma' = \Gamma \cup \dot{\Gamma}$ 이며, $\dot{\Gamma} = \{\dot{a} \mid a \in \Gamma\}$ 는 헤드 위치가 표시된 기호의 집합이다.

$M$ 의 한 단계를 $S$ 가 시뮬레이션하는 과정:

$S$ 의 헤드가 테이프의 왼쪽 끝에서 시작하여 오른쪽으로 순회(Scan)하며, $k$ 개의 표시 기호(각 테이프의 헤드 위치)를 찾는다. 이 과정에서 각 표시 기호의 값을 상태에 기억한다.
$k$ 개의 기호를 모두 읽은 후, $M$ 의 전이 함수 $\delta$ 를 적용하여 다음 상태, 각 테이프에 쓸 기호, 각 헤드의 이동 방향을 결정한다.
$S$ 의 헤드가 다시 왼쪽으로 순회하며, 각 표시 기호 위치에서 기호를 쓰고 표시를 이동시킨다.

3.2 시간 복잡도 분석

$M$ 이 $t(n)$ 단계를 수행한다고 하자. $M$ 의 각 테이프에서 헤드가 방문하는 셀의 범위는 최대 $t(n)$ 이다(매 단계 최대 1셀 이동). 따라서 $S$ 의 테이프에서 $k$ 개 테이프의 인코딩이 차지하는 범위는 $O(k \cdot t(n))$ 이다.

$M$ 의 한 단계를 시뮬레이션하기 위해 $S$ 는 인코딩된 영역을 좌우로 순회해야 하며, 이 순회에 $O(k \cdot t(n))$ 단계가 소요된다. $M$ 의 $t(n)$ 단계 전체를 시뮬레이션하면:

$O(t(n)) \times O(k \cdot t(n)) = O(k \cdot t(n)^2) = O(t(n)^2)$

( $k$ 는 상수이므로 점근적 분석에서 생략)

환원의 의의

계산 가능성의 동등성

다중 테이프 환원 정리는 다중 테이프 튜링 기계가 단일 테이프 튜링 기계와 계산 가능성(Computability)에서 동등함을 증명한다. 다중 테이프 기계가 인식하는 모든 언어는 단일 테이프 기계에 의해서도 인식 가능하다.

다항적 시간 동등성

시간 복잡도의 증가가 이차적( $O(t^2)$ )이므로, 다항 시간(Polynomial Time) 계산의 클래스는 보존된다. $k$ -테이프 기계가 시간 $O(n^c)$ 에 작동하면, 단일 테이프 기계는 시간 $O(n^{2c})$ 에 작동하며, 이는 여전히 다항 시간이다. 따라서 복잡도 클래스 P는 단일 테이프와 다중 테이프에서 동일하다.

처치-튜링 논제의 강건성

다중 테이프 환원은 튜링 기계의 계산 능력이 구체적 설계(테이프 수)에 민감하지 않음을 보여주며, 이는 처치-튜링 논제의 강건성(Robustness)을 지지하는 증거이다. 계산 가능성의 개념이 기계 모델의 세부 사항에 의존하지 않는 본질적(Intrinsic) 개념임을 입증한다.

다른 변형 모델과의 관계

다중 테이프 환원과 유사한 환원 결과가 다른 튜링 기계 변형에 대해서도 성립한다:

다차원 테이프 튜링 기계: 2차원 이상의 테이프를 가진 기계. 단일 테이프로 시뮬레이션 가능하다.
다중 헤드 튜링 기계: 하나의 테이프에 여러 헤드를 가진 기계. 단일 헤드로 시뮬레이션 가능하다.
양방향 무한 테이프: 단방향 무한 테이프로 시뮬레이션 가능하다.

이 모든 변형이 표준 단일 테이프 튜링 기계와 동등한 계산 능력을 가진다는 사실은 튜링 기계에 의한 계산 가능성 정의의 강건성을 확인한다.