튜링 머신 101: 덧셈 기계 만들기

책상에 앉은 튜링의 눈앞에는 오직 노트와 펜, 그리고 그가 방금 창조해낸 ‘a-machine’의 개념뿐이었다. 이제 증명할 시간이었다. 이 순전히 기계적인 장치가, 인간의 지적 활동이라 여겨졌던 ‘계산’을 수행할 수 있는지를.

그는 가장 기초적인 문제부터 시작하기로 했다.
‘숫자 3에 1을 더해 4를 만드는 기계.’

이 문제를 기계의 언어로 바꿔야 했다. 튜링은 숫자를 표현하는 방식으로 ‘1의 개수’를 사용하기로 했다. 즉, 숫자 3은 ‘111’로 표현된다. 따라서 문제는 ‘111이 적힌 테이프를 1111로 바꾸는 것’이 된다.

초기 상태:
테이프는 양쪽이 비어있고, 중앙에 ‘111’이 적혀 있다. 헤드는 가장 왼쪽에 있는 ‘1’에서 시작한다.

[... B | 1 | 1 | 1 | B ...]
▲

목표:
기계가 작동을 멈췄을 때, 테이프는 ‘1111’이 되어 있어야 한다.

[... B | 1 | 1 | 1 | 1 | B ...]

튜링은 기계의 입장에서 생각하기 시작했다.
‘내가 헤드라면, 무엇을 해야 하는가?’

1. 일단 ‘1’들의 가장 오른쪽 끝을 찾아야 한다. 그러려면 계속 오른쪽으로 이동해야 한다.
2. 이동하다가 처음으로 빈칸(B)을 만나면, 그곳이 바로 1을 추가할 자리다.
3. 그 빈칸에 ‘1’을 쓴다.
4. 임무가 끝났으니, 작동을 멈춘다.

이 논리적 절차를 이제 기계가 알아들을 수 있는 ‘행동표’로 번역해야 했다. 튜링은 두 개의 상태를 정의했다.

• q_find_end : ‘1’의 끝을 찾아 오른쪽으로 이동하는 상태.
• q_halt : 모든 작업을 마치고 정지하는 상태.

그는 표를 그리기 시작했다.

규칙 1:

• 만약 현재 상태가 q_find_end이고, 헤드가 1을 읽는다면?
• 아직 끝이 아니라는 뜻이다. 1은 그대로 두고, 계속 오른쪽으로 가야 한다.
• 행동: 1을 쓰고(즉, 바꾸지 않고), 오른쪽(R)으로 한 칸 이동하고, 상태는 그대로 q_find_end를 유지한다.

규칙 2:

• 만약 현재 상태가 q_find_end이고, 헤드가 빈칸 B를 읽는다면?
• 드디어 ‘1’들의 끝, 목표 지점을 찾았다!
• 행동: 이 빈칸에 1을 쓰고, 임무가 완수되었으니, 상태를 q_halt로 변경한다.

이 두 가지 규칙이면 충분했다. 튜링은 완성된 행동표를 만족스럽게 바라보았다.

이제, 시뮬레이션을 해볼 차례였다. 튜링은 펜 끝으로 헤드의 움직임을 따라가며 기계의 작동을 머릿속으로 그렸다.

시작:
상태: q_find_end
테이프: [... B | 1 | 1 | 1 | B ...] (헤드는 굵은 글씨 위에)

1단계:

• 헤드가 ‘1’을 읽는다. 상태는 q_find_end. (규칙 1 적용)
• 헤드는 ‘1’을 쓰고 오른쪽으로 이동. 상태는 그대로 q_find_end.
• 상태: q_find_end
• 테이프: [... B | 1 | 1 | 1 | B ...]

2단계:

• 헤드가 ‘1’을 읽는다. 상태는 q_find_end. (규칙 1 적용)
• 헤드는 ‘1’을 쓰고 오른쪽으로 이동. 상태는 그대로 q_find_end.
• 상태: q_find_end
• 테이프: [... B | 1 | 1 | 1 | B ...]

3단계:

• 헤드가 ‘1’을 읽는다. 상태는 q_find_end. (규칙 1 적용)
• 헤드는 ‘1’을 쓰고 오른쪽으로 이동. 상태는 그대로 q_find_end.
• 상태: q_find_end
• 테이프: [... B | 1 | 1 | 1 | B ...]

4단계:

• 헤드가 빈칸 ‘B’를 읽는다. 상태는 q_find_end. (규칙 2 적용)
• 헤드는 그 자리에 ‘1’을 쓰고, 상태를 q_halt로 변경한다.
• 상태: q_halt
• 테이프: [... B | 1 | 1 | 1 | 1 ...]

종료:
기계는 q_halt 상태에 도달했으므로 더 이상 작동하지 않는다. 최종 테이프에는 ‘1111’이 선명하게 남아있었다.

성공이었다.
튜링은 의자 깊숙이 등을 기댔다. 방금 그가 한 것은 단순한 덧셈 시뮬레이션이 아니었다. 그는 ‘생각’ 없이, 오직 정해진 기계적 규칙만으로 지적인 결과물을 만들어낼 수 있음을 스스로에게 증명했다.

이 작고 단순한 기계가 덧셈을 할 수 있다면, 규칙을 조금 더 복잡하게 만들어 뺄셈, 곱셈, 그 어떤 산술 연산도 수행하게 할 수 있을 터였다.

그의 상상 속 기계는 더 이상 막연한 스케치가 아니었다. 그것은 이제 작동하는 논리였다. 결정 문제를 향한 그의 여정에, 첫 번째 교두보가 확보되는 순간이었다.