튜링 머신(Turing Machine)이란?

튜링 머신은 1936년 영국의 수학자 앨런 튜링(Alan Turing)이 고안한 가상의 수학적 계산 모델이다. 물리적으로 존재하는 기계가 아니라, "계산이란 무엇인가?"를 증명하기 위해 만든 논리적인 개념이다. 이 기계는 오직 정해진 규칙에 따라 테이프 위를 이동하며 기호를 조작하는 방식으로 작동한다.

 

 중요한 점은 이 가상의 기계가 현대 컴퓨터의 논리적 구조와 작동 원리의 완벽한 근간이 되었다는 것이다. "어떤 문제든 해결할 수 있는 명확한 알고리즘(규칙)이 있다면, 튜링 머신으로 계산할 수 있다"는 것이 핵심 원리이다.

 

튜링 머신의 4대 구조 (Structure)

튜링 머신은 물리적인 복잡성 없이, 연산을 수행하기 위한 최소한의 논리적 장치들로 구성되어 있다.

• 테이프 (Tape)
  • 형태: 일정한 크기의 칸(Cell)들로 나뉘어진 1차원 형태의 띠이다.무수히 많은 정사각형 칸(Cell)들이 일렬로 길게 이어져 있는 격자무늬 띠로 이뤄져 있으며, 이론상 양쪽 방향으로 무한히 늘어날 수 있다.
  • 특징: 각 칸에는 기호(예: 0, 1, A, B 등)가 적혀 있으며, 기호가 적혀 있지 않은 빈 칸은 공백(Blank, 보통 B 또는 _로 표시) 상태로 둔다. 이는 튜링 머신의 유일한 저장 매체(메모리)개념이다.
• 헤드 (Head)
  • 형태: 테이프 위의 특정 단일 칸을 가리키는 장치이다.
  • 특징: 현재 가리키고 있는 칸의 기호를 읽고(Read), 그 자리에 새로운 기호를 기록(Write)할 수 있다. 또한 테이프 위를 한 번에 왼쪽(L)이나 오른쪽(R)으로 한 칸씩 이동(Move)할 수 있다.
  • 단계: 
    1. 읽기(Read): 현재 가리키고 있는 칸에 어떤 기호가 쓰여 있는지 읽어 들인다.
    2. 쓰기(Write): 그 칸에 있던 기존 기호를 지우고 새로운 기호를 덮어쓴다.
    3. 이동(Move): 규칙에 따라 왼쪽(L) 또는 오른쪽(R)으로 정확히 한 칸씩 움직인다. 건너뛰거나 멀리 점프하여 이동할 수 없다.
• 상태 레지스터 (State Register)
  • 형태: 머신이 현재 어떤 단계에 처해 있는지를 나타내는 유한한 개수의 내부 상태들 중 하나를 기억하는 장치.
  • 특징: 머신은 항상 특정한 상태(예: $q_0, q_1, q_2 \dots$)에 머물러 있으며, 이 상태는 조건에 따라 계속 변한다. 연산의 시작을 알리는 시작 상태와 연산의 끝을 알리는 정지 상태(Halt State)가 존재한다.
  • 머신은 동시에 여러 생각을 하지 못하기에, 오직 하나의 현재 상태(예: q0, q1, q2)에 머무른다.
    • 시작 상태(Start State): 기계가 처음 켜졌을 때 갖는 최초의 상태이다.
    • 정지 상태(Halt State): 연산이 성공적으로 완수되어 기계가 멈추는 최종 상태이다.
• 전이 함수 / 행동표 / 동작 규칙표 (Transition Function / Action Table)
  • 형태: 기계가 어떤 조건에서 어떻게 행동해야 하는지 정의해 둔 규칙들의 집합이다.
  • 특징: 규칙은 항상 (현재 상태, 헤드가 읽은 기호)라는 두 가지 입력 조건을 기준으로 구성된다. 이 조건이 충족되면 (쓸 기호, 헤드의 이동 방향, 변경될 다음 상태)라는 세 가지 지시사항을 출력한다.
  • 세부 지시사항
    
    • [지시사항 1] 그 칸에 새로 쓸 기호가 무엇인가?
    • [지시사항 2] 헤드를 왼쪽(L)으로 갈 것인가, 오른쪽(R)으로 갈 것인가?
    • [지시사항 3] 기계의 내부 상태를 어떤 상태로 바꿀 것인가?

 

튜링 머신의 동작 과정 (Process)

튜링 머신의 동작은 매우 단순한 단위 작업의 무한한 반복으로 이루어진다. 본질적인 동작 사이클은 다음과 같다.

1단계: 스캔 및 조회 (Scan)

머신은 현재 부여된 내부 상태 정보와 헤드가 가리키는 테이프 칸 위의 기호를 결합한다. 그 후 이 결합 값에 해당하는 행동 지침을 동작 규칙표에서 찾는다.

• 상황 예시: "현재 내부 상태는 q0이고, 헤드가 비춘 테이프 위의 문자는 1이다." ➔ 규칙표에서 (q0, 1)에 해당하는 행을 검색한다.

2단계: 명령 수행 (Execution)

매칭된 규칙표의 명령에 따라 다음과 같이 테이프와 헤드를 실시간으로 물리 조작한다.

1. 헤드가 위치한 칸의 기호를 규칙에 적힌 새 기호로 바꾼다.
2. 헤드를 지정된 방향(왼쪽 혹은 오른쪽)으로 한 칸 미세하게 이동시킨다.

3단계: 상태 변경 및 판단 (Transition & Halt Decision)

1. 머신의 내부 상태를 규칙에 적혀 있던 다음 상태로 업데이트한다.
2. 새로 업데이트된 상태가 미리 지정된 정지 상태(Halt)인지 판별한다.
   • 정지 상태가 아니라면: 다시 새로운 위치에서 1단계(스캔 및 조회)로 되돌아가서 위의 과정을 동일하게 실행.
   • 정지 상태에 도달했다면: 기계는 모든 연동 장치를 멈추고 정지한다. 연산이 완료되었으며, 이때 테이프 전체에 남겨진 문자들의 열이 계산의 최종 결괏값(출력값)이 된다.

 

플로우 차트 시각화

 

동작 과정 시뮬레이션 예시

이해를 돕기 위해 "이진수 맨 끝자리에 1을 더하는 연산(+1)"을 수행하는 튜링 머신의 작동 시연을 예시로 들어보자.

• 초기 상태: 테이프에 1, 0이 적혀 있고 헤드는 맨 오른쪽 숫자 0을 가리키고 있다. (현재 내부 상태는 시작 상태인 q_start)
• 규칙 1: (q_start, 0) 일 때 ➔ 1을 쓰고, 헤드를 R(오른쪽)로 가고, 상태를 q_halt로 변경한다.

시뮬레이션 흐름:

1. [1단계] 기계가 현재 상태(q_start)와 헤드의 문자(0)를 읽는다.
2. [2단계] 규칙 1을 발견하고 지시대로 작동합니다. 헤드 위치의 0을 지우고 1로 바꿔 씁니다. 헤드를 오른쪽(R)으로 한 칸 움직인다.
3. [3단계] 상태를 q_halt로 전환한다.
4. [판단] 새로 바뀐 상태가 정지 상태(q_halt)이므로 동작을 완전히 멈춘다.

• 최종 테이프 모습: 1, 1 (기존 10에서 1이 늘어난 11이 완성).