튜링 기계

00. TL;DR

• 튜링 기계는 테이프, 헤드, 상태, 명령표로 구성된 가상의 계산 모델입니다.
• 매우 단순한 규칙만으로도 모든 계산이 가능하다는 점에서, 현대 컴퓨터의 이론적 기초가 됩니다.
• 헤드는 테이프의 기호를 읽고, 쓰고, 이동하면서 상태 전이에 따라 작업을 반복 수행합니다.

---

01. 튜링 기계란?

튜링 기계는 1936년 앨런 튜링이 제안한 개념으로,

어떤 계산 문제든 단순한 명령 집합으로 처리할 수 있다는 것을 증명하기 위한 모델입니다.

 

실제 물리적인 기계는 아니며, 이론상 컴퓨터의 모델이라 할 수 있습니다.

---

01.01. 구성 요소

구성 요소	설명
테이프	무한히 긴 칸들의 줄. 각 칸에 하나의 기호(예: 0, 1, 공백 등)를 기록할 수 있음.
헤드	테이프 위를 왼쪽 또는 오른쪽으로 이동하면서 기호를 읽거나 씀.
상태	현재 기계의 내부 상태를 나타냄. S1, S2 등으로 표현.
명령표	현재 상태와 읽은 기호에 따라 ‘기호 변경’, ‘이동 방향’, ‘다음 상태’를 결정하는 규칙 모음.

 

---

01.02. 기본 동작 원리

튜링 기계는 다음 과정을 반복합니다:

1. 현재 상태와 테이프에서 읽은 기호를 확인합니다.
2. 명령표를 참조해 다음 작업을 결정합니다.
3. 기호를 쓰거나 유지합니다.
4. 왼쪽 또는 오른쪽으로 이동합니다.
5. 상태를 변경합니다.
6. 위 작업을 반복하거나 정지 상태(Halt)에 도달하면 종료합니다.

---

02. 동작 방식 예제

02.01. 예제 1 – 1 → 1 1 (복제)

목표

테이프에 1 하나가 있으면, 1 1이 되도록 합니다.

초기 상태

테이프:   □ □ 1 □ □
            ↑
           (헤드)
상태: S1

명령표

상태	읽은 기호	쓸 기호	이동	다음 상태
S1	1	1	→	S2
S2	□	1	정지	Halt

실행 결과

테이프:   □ □ 1 1 □

02.02. 예제 2 – 1 → 1 1 1 (세 번 복제)

목표

테이프에 1이 있으면, 1 1 1이 되도록 합니다.

초기 상태

테이프:   □ □ 1 □ □ □ □
            ↑
          (헤드)
상태: S1

명령표

상태	읽은 기호	쓸 기호	이동	다음 상태
S1	1	1	→	S2
S2	□	1	→	S3
S3	□	1	정지	Halt

실행 결과

테이프:   □ □ 1 1 1 □ □

02.03. 예제 3 – 1 1 1 → 1 1 (마지막 기호 삭제)

목표

테이프에 1 1 1이 있으면, 마지막 1 하나를 지웁니다.

초기 상태

테이프:   □ 1 1 1 □
          ↑
         (헤드)
상태: S1

명령표

상태	읽은 기호	쓸 기호	이동	다음 상태
S1	1	1	→	S1
S1	□	□	←	S2
S2	1	□	정지	Halt

실행 결과

테이프:   □ 1 1 □ □

---

03. 핵심 정리

• 튜링 기계는 복잡한 계산도 아주 단순한 방식으로 처리합니다.
• 명령표만 잘 구성하면, 어떤 알고리즘이든 구현 가능합니다.
• 이러한 성질 때문에, 튜링 기계는 컴퓨터 과학의 이론적 기초로 사용됩니다.
• 현대 컴퓨터는 튜링 기계를 훨씬 빠르고 복잡하게 만든 구조라고 볼 수 있습니다.

---

04. 참고: 튜링 완전성

튜링 기계로 표현 가능한 계산은 모두 튜링 완전(Turing Complete) 합니다.

JavaScript, Python, C언어 같은 대부분의 프로그래밍 언어도 이 성질을 가지고 있습니다.