3.10 이항 덧셈과 뺄셈의 튜링 기계 설계

1. 이진 표현과 산술 연산

이진 표현(Binary Representation)에서 자연수 $n$ 은 비트열 $b_k b_{k-1} \cdots b_1 b_0$ 으로 표현되며, $n = \sum_{i=0}^{k} b_i \cdot 2^i$ 이다. 이진 표현에서의 산술 연산은 단항 표현에 비해 지수적으로 효율적인 공간을 사용하지만(자연수 $n$ 의 표현에 $\lceil \log_2(n+1) \rceil$ 비트), 튜링 기계의 구현이 더 복잡해진다.

본 절에서는 이진수의 최하위 비트(Least Significant Bit, LSB)가 테이프의 왼쪽에, 최상위 비트(Most Significant Bit, MSB)가 오른쪽에 위치하는 역순(Reversed) 표기를 채택한다. 이 관례는 올림(Carry)의 전파 방향과 헤드의 이동 방향을 일치시켜 기계 설계를 단순화한다. 두 피연산자는 구분자 기호 $\#$ 로 분리된다.

2. 이진 덧셈의 튜링 기계

2.1 문제 정의

입력: $a_{n-1} \cdots a_1 a_0 \# b_{m-1} \cdots b_1 b_0$ (이진수 $A$ 와 $B$ 의 역순 표현)
출력: $A + B$ 의 이진 표현

2.2 알고리즘 전략

이진 덧셈은 최하위 비트부터 최상위 비트까지 순차적으로 처리하며, 각 자릿값에서 올림(Carry)을 관리한다. 핵심 규칙:

$0 + 0 + 0 = 0$ , 올림 $0$
$0 + 1 + 0 = 1$ , 올림 $0$ (또는 $1 + 0 + 0$ )
$1 + 1 + 0 = 0$ , 올림 $1$
$1 + 0 + 1 = 0$ , 올림 $1$ (또는 $0 + 1 + 1$ )
$1 + 1 + 1 = 1$ , 올림 $1$

여기서 세 번째 항은 이전 자릿값의 올림이다.

2.3 기계 설계

올림의 유무를 상태로 인코딩한다:

$q_0$ : 올림 없음(Carry = 0) 상태에서 $A$ 의 현재 비트를 읽음
$q_1$ : 올림 있음(Carry = 1) 상태에서 $A$ 의 현재 비트를 읽음
$q_2$ : $A$ 의 비트를 기억하고 $B$ 의 대응 비트를 찾아 이동
$q_3$ : 결과 비트를 기록하고 다음 자릿값으로 진행

실제 구현은 $A$ 의 비트, $B$ 의 비트, 올림의 세 값의 조합에 따라 결과 비트와 다음 올림을 결정해야 하므로, 다수의 상태가 필요하다. 주요 상태 전이의 논리:

올림 = 0인 경우 ( $q_0$ 계열):

$A$ 의 비트	$B$ 의 비트	결과 비트	다음 올림
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

올림 = 1인 경우 ( $q_1$ 계열):

$A$ 의 비트	$B$ 의 비트	결과 비트	다음 올림
0	0	1	0
0	1	0	1
1	0	0	1
1	1	1	1

2.4 다중 테이프 설계의 단순성

이진 덧셈은 다중 테이프 튜링 기계(Multi-Tape Turing Machine)에서 보다 간결하게 구현된다. 세 개의 테이프를 사용하여:

테이프 1: 피가수 $A$
테이프 2: 가수 $B$
테이프 3: 결과 $A + B$

세 테이프의 헤드를 동기적으로 오른쪽으로 이동시키며, 각 위치에서 테이프 1과 테이프 2의 비트를 읽고, 올림을 고려하여 결과를 테이프 3에 기록한다. 이 설계는 이진 전가산기(Full Adder)의 직접적 소프트웨어 구현이다.

3. 이진 뺄셈의 튜링 기계

3.1 문제 정의

입력: $A \# B$ ( $A \geq B$ 인 이진수)
출력: $A - B$ 의 이진 표현

3.2 알고리즘 전략

이진 뺄셈은 빌림(Borrow)을 관리하며 최하위 비트부터 순차적으로 처리한다. 핵심 규칙:

$0 - 0 - 0 = 0$ , 빌림 $0$
$1 - 0 - 0 = 1$ , 빌림 $0$
$1 - 1 - 0 = 0$ , 빌림 $0$
$0 - 1 - 0 = 1$ , 빌림 $1$ (상위 자릿값에서 빌림 발생)
$0 - 0 - 1 = 1$ , 빌림 $1$
$1 - 0 - 1 = 0$ , 빌림 $0$
$1 - 1 - 1 = 1$ , 빌림 $1$
$0 - 1 - 1 = 0$ , 빌림 $1$

여기서 세 번째 항은 이전 자릿값의 빌림이다.

3.3 기계 설계

빌림의 유무를 상태로 인코딩한다:

$q_0$ : 빌림 없음(Borrow = 0)
$q_1$ : 빌림 있음(Borrow = 1)

뺄셈 기계의 구조는 덧셈 기계와 유사하되, 올림 대신 빌림을 관리하고, 결과에서 선행 영(Leading Zero)을 제거하는 후처리가 필요하다.

빌림 = 0인 경우:

$A$ 의 비트	$B$ 의 비트	결과 비트	다음 빌림
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

빌림 = 1인 경우:

$A$ 의 비트	$B$ 의 비트	결과 비트	다음 빌림
0	0	1	1
0	1	0	1
1	0	0	0
1	1	1	1

4. 이진 산술의 복잡도 분석

4.1 시간 복잡도

단일 테이프 튜링 기계에서 $n$ -비트 이진 덧셈의 시간 복잡도는 $O(n^2)$ 이다. 이는 각 비트 처리 시 $A$ 와 $B$ 사이를 왕복해야 하며, 왕복 거리가 $O(n)$ 이기 때문이다. 다중 테이프 튜링 기계에서는 $O(n)$ 으로 개선된다.

4.2 단항 표현과의 비교

$n$ -비트 이진수 두 개의 덧셈에서, 피연산자의 크기는 최대 $2^n - 1$ 이다. 동일한 피연산자를 단항으로 표현하면 입력 길이가 $O(2^n)$ 이 되며, 단항 덧셈의 시간은 $O(2^n)$ 이다. 따라서 이진 표현은 산술 연산에서 지수적 효율 이점을 제공한다.

5. 이진 산술 튜링 기계의 이론적 의의

이진 산술의 튜링 기계 구현은 다음의 이론적 의의를 갖는다.

첫째, 데이터 표현(Representation)의 선택이 계산 효율에 근본적 영향을 미침을 실증한다. 동일한 연산이 단항 표현에서는 지수적 시간이, 이진 표현에서는 다항적 시간이 소요된다.

둘째, 올림/빌림의 관리가 상태에 의한 유한 기억과 테이프에 의한 무한 기억의 상호작용으로 구현됨을 보여준다. 올림 비트(0 또는 1)는 상태에 인코딩되고, 비트열 자체는 테이프에 저장된다.

셋째, 현대 컴퓨터의 산술 논리 장치(ALU)가 수행하는 이진 산술 연산의 논리적 구조가 튜링 기계의 전이 함수로 완전히 포착됨을 보여주며, 이는 하드웨어 설계와 계산 이론 사이의 형식적 대응을 예시한다.