3.9 단항 산술 연산의 튜링 기계 구현

1. 단항 표현(Unary Representation)

단항 표��(Unary Representation)은 자연수 $n$ 을 기호 $1$ 의 $n$ 번 반복으로 표현하는 수 체계이다. 자연수 $n$ 은 문자열 $1^n$ 으로 표현된다:

$0 \rightarrow \epsilon$ (빈 문자열) 또는 $0 \rightarrow$ (기호 없음)
$1 \rightarrow 1$
$2 \rightarrow 11$
$3 \rightarrow 111$
$n \rightarrow \underbrace{11\cdots1}_{n}$

단항 표현은 위치적 기수법(Positional Numeral System)에 비해 표현 효율이 낮으나(자연수 $n$ 의 표현에 $n$ 개의 기호가 필요), 산술 연산의 튜링 기계 구현이 구조적으로 단순하다는 이점이 있다. 이 때문에 단항 표현은 계산 이론의 교육적 예시에서 표준적으로 사용된다.

본 절에서는 두 자연수 사이의 구분자(Separator)로 기호 $0$ 을 사용한다. 예를 들어, $3 + 2$ 의 입력은 $111\,0\,11$ 로 표현된다.

2. 단항 덧셈(Unary Addition)

2.1 문제 정의

입력: $1^m 0 1^n$ (단항으로 표현된 $m$ 과 $n$ , 구분자 $0$ 으로 분리)
출력: $1^{m+n}$ (단항으로 표현된 $m + n$ )

2.2 기계 설계

전략: 구분자 $0$ 을 $1$ 로 바꾸면 $1^m 1 1^n = 1^{m+1+n}$ 이 되므로, 결과에서 $1$ 을 하나 제거하여 $1^{m+n}$ 을 얻는다. 구체적으로, 구분자 $0$ 을 $1$ 로 바꾸고 오른쪽 끝의 $1$ 을 공백으로 바꾸는 방식을 사용한다.

상태: $Q = \{q_0, q_1, q_2, q_{\text{accept}}\}$

$q_0$ : 구분자 $0$ 을 찾아 오른쪽으로 이동
$q_1$ : $0$ 을 $1$ 로 바꾼 후 오른쪽 끝으로 이동
$q_2$ : 오른쪽 끝의 $1$ 을 공백으로 바꾸고 정지

전이 함수:

상태	$1$	$0$	$\sqcup$
$q_0$	$(q_0, 1, R)$	$(q_1, 1, R)$	—
$q_1$	$(q_1, 1, R)$	—	$(q_2, \sqcup, L)$
$q_2$	$(q_{\text{accept}}, \sqcup, R)$	—	—

2.3 실행 ��적: $2 + 3 = 5$

입력: $11\,0\,111$

단계	테이프	헤드 위치	상태
0	$\mathbf{1}1\,0\,111$	0	$q_0$
1	$1\mathbf{1}\,0\,111$	1	$q_0$
2	$11\,\mathbf{0}\,111$	2	$q_0$
3	$11\,\mathbf{1}\,111$	2→3	$q_1$ (0을 1로 변경)
4–6	$111\,\mathbf{1}11$ → …	3–5	$q_1$ (오른쪽 이동)
7	$111111\,\mathbf{\sqcup}$	6	$q_1$ → $q_2$ (왼쪽 이동)
8	$11111\,\mathbf{\sqcup}$	5	$q_2$ → $q_{\text{accept}}$ (마지막 1을 지움)

결과: $11111 = 1^5$ . $2 + 3 = 5$ 이므로 올바르다.

3. 단항 뺄셈(Unary Subtraction)

3.1 문제 정의

입력: $1^m 0 1^n$ ( $m \geq n$ )
출력: $1^{m-n}$

3.2 기계 설계

전략: 왼쪽 블록의 $1$ 과 오른쪽 블록의 $1$ 을 하나씩 짝��어 제거한다. 구체적으로, 오른쪽 블록의 가장 오른쪽 $1$ 을 공백으로 바꾸고, 왼쪽 블록의 가장 오른쪽 $1$ 도 공백으로 바꾸는 과정을 반복한다.

상태: $Q = \{q_0, q_1, q_2, q_3, q_4, q_{\text{accept}}\}$

$q_0$ : 오른쪽 끝으로 이동하여 오른쪽 블록의 마지막 $1$ 을 찾음
$q_1$ : 오른쪽 끝에서 $1$ 을 공백으로 바꿈
$q_2$ : 왼쪽으로 이동하�� 구분자 $0$ 을 통과
$q_3$ : 왼쪽 블록의 마지막 $1$ 을 $0$ 으로 바꿈
$q_4$ : 정리 단계(구분자와 공백 정리)

이 기계의 상세한 전이 함수는 상태 수가 증가하여 복잡해지나, 핵심 원리는 두 블록의 원소를 하나씩 소거하는 반복적 짝 맞추기이다.

4. 단항 곱셈(Unary Multiplication)

4.1 문제 정의

입력: $1^m 0 1^n$
출력: $1^{m \times n}$

4.2 기계 설계

전략: $m \times n$ 은 $n$ 을 $m$ 번 더하는 것으로 환원된다. 왼쪽 블록의 $1$ 을 하나씩 소비하면서, 매번 오른쪽 블록 $1^n$ 을 결과 영역에 복사한다.

구체적 절차:

왼쪽 블록의 첫 $1$ 을 표시(예: $X$ 로 변환)한다.
오른쪽 블록 $1^n$ 을 결�� 영역(테이프의 별도 위치)에 복사한다.
단계 1-2를 왼쪽 블록의 모든 $1$ 에 대해 반복한다.
결과 영역에 $1^{m \times n}$ 이 기록된다.

이 구현에는 다수의 상태가 필요하며(원본과 복사본을 구분하기 위한 표시 기호, 복사 위치 추적 등), 튜링 기계의 ��태 수가 문제의 복잡도에 따라 증가하는 전형적 사례이다.

4.3 시간 복잡도

단항 곱셈의 시간 복잡도는 $O(m \times n \times (m + n))$ 이다. 외부 루프가 $m$ 번, 내부 복사 루프가 $n$ 번 반복되며, 각 복사에서 테이프를 $O(m + n)$ 만큼 순회한다. 이는 단항 표현의 비효율성과 테이프의 순차적 접근 특성이 결합된 결과이다.

5. 단항 산술의 이론적 의의

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

첫째, 산술의 기계적 수행 가능성을 실증한다. 기본 산술 연산(덧셈, 뺄셈, 곱셈)이 유한한 수의 상태와 간단한 전이 규칙으로 구현 가능하다는 것은, 산술이 기계적으로 계산 가능(Mechanically Computable)함을 구체적으로 보여준다.

둘째, 연산 복잡도의 구체적 분석이 가능하다. 각 연산에 필요한 단계 수와 테이프 공간을 정밀하게 분석할 수 있으며, 이를 통�� 데이터 표현 방식(단항 대 이진)과 기계 구조가 연산 효율에 미치는 영향을 정량적으로 평가할 수 있다.

셋째, **수학적 구성(Mathematical Construction)**의 기계화를 예시한다. 자연수의 산술을 기호 조작의 규칙 체계로 환원하는 것은 힐베르트의 형식주의 프로그램이 지향한 목표의 구체적 실현이다.

단항 산술 연산의 튜링 기계 구현은 “계산이란 기호의 기계적 조작이다“라는 튜링의 핵심 통찰을 가장 직접적이고 구체적인 형태로 보여주는 교육적·이론적 사례이다.