3.4 무한 테이프, 읽기/쓰기 헤드, 상태 레지스터의 구조

1. 무한 테이프의 구조와 역할

1.1 테이프의 물리적 추상화

튜링 기계의 무한 테이프(Infinite Tape)는 계산 과정에서 데이터를 저장하고 조작하기 위한 무한한 기억 공간(Memory)의 추상화이다. 테이프는 셀(Cell)이라 불리는 이산적 저장 단위의 선형 배열(Linear Array)로 구성되며, 각 셀은 테이프 알파벳 $\Gamma$ 의 기호 중 정확히 하나를 저장한다.

테이프의 구조적 특성은 다음과 같다:

1차원 선형 구조: 셀들이 일직선으로 배열된다. 각 셀은 좌우 인접한 셀과의 순서 관계에 의해 위치가 결정된다.
이산적 셀: 셀의 수는 가산 무한(Countably Infinite)이며, 각 셀은 자연수로 색인(Index)될 수 있다.
단일 기호 저장: 각 셀은 한 시점에 정확히 하나의 기호를 저장한다.
읽기/쓰기 가능: 각 셀의 내용은 읽혀지거나 새로운 기호로 덮어쓰여질 수 있다.

1.2 단방향 무한 대 양방향 무한

테이프의 무한성에 관해 두 가지 변형이 존재한다:

단방향 무한 테이프(One-Way Infinite Tape): 테이프의 왼쪽 끝이 존재하고 오른쪽으로만 무한히 확장된다. 셀은 $c_0, c_1, c_2, \ldots$ 로 색인된다. 헤드가 가장 왼쪽 셀에서 왼쪽으로 이동하려는 시도는 정의되지 않거나, 헤드가 제자리에 머무는 것으로 처리된다.

양방향 무한 테이프(Two-Way Infinite Tape): 테이프가 양방향으로 무한히 확장된다. 셀은 $\ldots, c_{-2}, c_{-1}, c_0, c_1, c_2, \ldots$ 로 색인된다.

두 변형은 계산적으로 동치(Computationally Equivalent)이다. 양방향 무한 테이프를 단방향 무한 테이프로 시뮬레이션하려면, 양방향 테이프의 양의 부분과 음의 부분을 단방향 테이프의 짝수 셀과 홀수 셀에 번갈아 배치하면 된다.

1.3 테이프의 초기 상태

계산 시작 시, 입력 문자열 $w = w_1 w_2 \cdots w_n \in \Sigma^*$ 이 테이프의 처음 $n$ 개 셀(셀 $c_0$ 부터 $c_{n-1}$ 까지)에 기록된다. 나머지 모든 셀은 공백 기호 $\sqcup$ (Blank Symbol)로 초기화된다.

$\text{테이프 초기 상태}: [w_1][w_2]\cdots[w_n][\sqcup][\sqcup][\sqcup]\cdots$

테이프의 기능

테이프는 세 가지 기능을 동시에 수행한다:

입력 매체(Input Medium): 기계에 제공되는 입력 데이터의 저장소이다.
작업 공간(Working Space): 계산 과정의 중간 결과가 기록되는 임시 저장소이다. 헤드가 이동하며 기호를 읽고 쓰는 과정에서 테이프의 내용이 동적으로 변화한다.
출력 매체(Output Medium): 계산이 완료된 후 테이프에 남아 있는 내용이 출력 결과가 된다.

현대 컴퓨터에서 입력 장치, 메모리(RAM), 출력 장치가 별도의 하드웨어로 분리되어 있는 것과 달리, 튜링 기계에서는 단일 테이프가 이 모든 기능을 통합적으로 수행한다.

읽기/쓰기 헤드의 구조와 동작

헤드의 위치

헤드는 매 시점에서 테이프의 정확히 하나의 셀 위에 위치한다. 헤드의 위치를 $h \in \mathbb{Z}$ (또는 $h \in \mathbb{N}_0$ , 단방향 테이프의 경우)로 나타낼 때, $h$ 는 헤드가 위치한 셀의 색인이다.

계산 시작 시, 헤드는 입력의 첫 번째 기호가 기록된 셀( $c_0$ ) 위에 위치한다: $h_0 = 0$ .

헤드의 동작

헤드는 매 계산 단계에서 다음의 세 가지 동작을 순차적으로 수행한다:

읽기(Read): 현재 위치 $h$ 의 셀에 저장된 기호 $a = \text{tape}[h]$ 를 읽는다. 이 기호가 전이 함수의 입력으로 사용된다.
쓰기(Write): 전이 함수에 의해 결정된 새로운 기호 $b$ 를 현재 셀에 기록한다: $\text{tape}[h] \leftarrow b$ . 기존 기호 $a$ 는 $b$ 로 덮어쓰여진다. $a = b$ 인 경우 실질적 변화가 없다.
이동(Move): 전이 함수에 의해 결정된 방향 $D \in \{L, R\}$ 으로 한 셀 이동한다:
- $D = L$ (왼쪽): $h \leftarrow h - 1$
- $D = R$ (오른쪽): $h \leftarrow h + 1$

일부 튜링 기계 정의에서는 헤드가 제자리에 머무는 동작 $S$ (Stay)를 추가하여 $D \in \{L, R, S\}$ 로 확장하나, 이 확장은 계산 능력을 변화시키지 않는다.

헤드 동작의 국부성

헤드의 이동은 매 단계에서 최대 한 셀로 제한된다. 이 국부성(Locality) 제약은 튜링 기계의 핵심적 설계 원리이다. 임의의 셀에 직접 접근(Random Access)하는 것이 아니라, 인접 셀로의 순차적 이동만이 허용된다. 이 제약에도 불구하고 튜링 기계의 계산 능력은 랜덤 접근 기계(Random Access Machine, RAM)와 동등하며, 다만 특정 계산에 필요한 단계 수가 증가할 수 있다.

상태 레지스터(유한 상태 제어 장치)의 구조

상태 레지스터의 기능

상태 레지스터(State Register)는 유한 상태 제어 장치(Finite State Control)의 핵심 구성 요소로서, 기계의 현재 내부 상태를 저장한다. 상태 레지스터는 유한한 상태 집합 $Q = \{q_0, q_1, q_2, \ldots, q_k\}$ 중 정확히 하나의 상태를 유지한다.

상태의 역할

상태는 기계의 “기억“의 유한한 부분을 담당한다. 현재 상태는 기계가 지금까지 수행한 계산의 이력(History)을 유한하게 요약한 것이며, 이 요약에 기반하여 다음 동작이 결정된다.

상태의 유한성은 중요한 제약이다. 기계가 무한한 테이프의 전체 내용을 상태만으로 기억할 수는 없다. 그러나 테이프가 추가적 기억 공간을 제공하므로, 기계 전체의 기억 용량은 무한하다. 상태 레지스터의 유한성과 테이프의 무한성의 결합이 튜링 기계의 계산 능력을 결정한다.

상태 전이의 결정론적 성격

결정론적 튜링 기계에서, 현재 상태 $q$ 와 헤드가 읽은 기호 $a$ 의 쌍 $(q, a)$ 가 주어지면, 다음 상태, 쓸 기호, 이동 방향이 유일하게 결정된다. 이 결정론적 성격은 동일한 입력에 대해 기계가 항상 동일한 계산 과정을 수행함을 보장한다.

세 구성 요소의 상호작용

테이프, 헤드, 상태 레지스터는 매 계산 단계에서 다음과 같이 상호작용한다:

상태 레지스터가 현재 상태 $q$ 를 제공한다.
헤드가 현재 위치의 셀에서 기호 $a$ 를 읽는다.
전이 함수 $\delta(q, a) = (q', b, D)$ 가 적용된다.
상태 레지스터가 $q'$ 로 갱신된다.
헤드가 현재 셀에 $b$ 를 쓴다.
헤드가 방향 $D$ 로 이동한다.

이 과정이 기계가 수락 상태 또는 거부 상태에 도달할 때까지 반복된다.

튜링 기계 구성 요소와 현대 컴퓨터의 대응

튜링 기계 구성 요소	기능	현대 컴퓨터 대응
무한 테이프	데이터 저장 및 작업 공간	메모리(RAM) + 보조 저장 장치
읽기/쓰기 헤드	데이터 접근 및 수정	메모리 버스 + CPU 레지스터
유한 상태 제어 장치	명령어 해독 및 실행 제어	CPU의 제어 장치(Control Unit)
전이 함수 $\delta$	동작 규칙의 명세	프로그램(명령어 집합)

이 대응은 튜링 기계가 현대 컴퓨터의 이론적 원형(Theoretical Prototype)임을 보여준다. 현대 컴퓨터는 튜링 기계의 추상적 구성 요소를 물리적 하드웨어로 구현한 것이며, 튜링 기계의 계산 능력에 대한 이론적 결과는 현대 컴퓨터의 계산 능력에 대한 원리적 보장과 한계를 동시에 제공한다.