[계산이론] 튜링 머신

Turing Machine, Language, Grammar, 그리고 계산 불가능한 문제(Undecidability)에 대한 핵심 개념을 정리한다.

---

1. 기본 정의 (Language & Grammar)

Language (언어)

• 정의: 알파벳 $\Sigma$로 이루어진 String(문자열)들의 집합이다.
• 예시: $\{0^n 1^n : n \ge 1\}$, $\{a^{n^2} : n \ge 1\}$ 등.

Grammar (문법)

언어를 생성하는 규칙 체계로, 4-tuple로 정의된다.

$G = (V, \Sigma, S, P)$

• $V$ (Variables): 변수 집합.
• $\Sigma$ (Terminals): String을 구성하는 알파벳.
• $S$ (Start Variable): 시작 변수.
• $P$ (Productions): 생성 규칙.

---

Context-free Grammar (CFG, 문맥 무관 문법)

• 모든 생성 규칙의 형태가 $A \rightarrow (\Sigma \cup V)^*$ 꼴을 갖는다.
• 특징: 좌변에는 오직 문자(변수) 1개만 올 수 있다. 즉, 문맥(앞뒤 사정)을 보지 않고 변환한다.

예제: $\{ 0^n 1^n : n \ge 1 \}$ 생성하기

이 언어를 생성하는 문법 $G = (V, \Sigma, S, P)$를 정의에 맞춰 작성하면 다음과 같다.

1. $V$: $\{ S \}$
   • 변수(Non-terminal)는 $S$ 하나만 사용한다.
2. $\Sigma$: $\{ 0, 1 \}$
   • 실제 언어를 구성하는 알파벳은 0과 1이다.
3. $S$: $S$
   • $S$에서 생성을 시작한다.
4. $P$:
   • $S \rightarrow 0S1$ (재귀: 0과 1을 양쪽에 하나씩 계속 붙여 나감)
   • $S \rightarrow 01$ (종료: 가장 안쪽의 최소 단위 01을 만들고 끝냄)

생성 과정 예시 (000111 만들기):
$S \Rightarrow 0S1 \Rightarrow 00S11 \Rightarrow 00\mathbf{01}11$ (종료 규칙 적용)

Context-Sensitive Grammar (CSG)는 자연어 처리 등 복잡한 문맥 검사가 필요할 때 쓰이지만, 이를 분석(파싱)하는 데 시간이 너무 오래 걸리거나(지수 시간) 효율적인 알고리즘을 만들기 어렵다는 단점이 있다.

반면, CFG (Context-Free Grammar)는 Stack을 이용해서 프로그래밍의 핵심인 중첩 구조(Nesting)를 표현할 수 있는 마지노선이자, O($n^3$) 혹은 O(n) 수준으로 파싱을 효율적으로 할 수 있는 알고리즘이 존재한다. 때문에 C, Java, Python 등 대부분의 프로그래밍 언어는 CFG를 기반으로 만들어진다.

하지만 CFG라도 $E \to E + E \mid \text{int}$ 처럼 작성하면 동일한 수식에 대해 연산 순서가 다른 두 개 이상의 파스 트리가 생길 수 있다. 이를 Ambiguous Grammar라고 한다. 이렇게 되면 컴퓨터가 코드를 실행할 때 의미를 확정할 수 없으므로, 프로그래밍 언어는 반드시 Unambiguous CFG로 정의되어야 한다.

보다 자세한 이야기는 오토마타 및 촘스키 위계(Chomsky Hierarchy), 컴파일러 등에서 다룬다.

---

2. 튜링 머신 (Turing Machine)

튜링 머신은 테이프(Tape), 헤드(Head), 상태(State)를 가진 계산 모델이다.

Formal Definition

수학적으로 튜링 머신 $M$은 다음과 같은 7-튜플(7-tuple)로 정의된다.

$M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$

1. $Q$: 상태들의 유한 집합 (Finite set of states)
   • 기계가 가질 수 있는 모든 상태 (예: 시작, 진행 중, 완료 등)
2. $\Sigma$: 입력 알파벳 (Input alphabet)
   • 초기 테이프에 적혀 있는 문자들의 집합 (Blank 제외)
3. $\Gamma$: 테이프 알파벳 (Tape alphabet)
   • 테이프에 쓸 수 있는 모든 기호 ($\Sigma \subset \Gamma$, Blank 포함)
4. $\delta$: 전이 함수 (Transition function)
   • $Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$
   • "현재 상태에서 어떤 문자를 읽었을 때 $\rightarrow$ 다음 상태로 가고, 문자를 쓰고, 헤드를 이동(L/R)하라"는 규칙
5. $q_0$: 시작 상태 (Start state, $q_0 \in Q$)
6. $B$: 공백 기호 (Blank symbol, $B \in \Gamma - \Sigma$)
   • 입력이 없는 빈 칸을 나타내는 기호
7. $F$: 수락 상태 집합 (Set of accepting states, $F \subseteq Q$)

TM의 동작 원리

입력($w$)이 들어왔을 때, 전이 함수 $\delta$에 따라 다음을 수행한다.
1. Write: 현재 위치에 기호를 쓴다.
2. Move: 헤드를 왼쪽($\leftarrow$)이나 오른쪽($\rightarrow$)으로 이동하거나 머무른다(Stay).
3. State: 상태를 변경한다.

TM이 정의하는 언어의 종류

가장 헷갈리기 쉬운 개념이므로 명확히 구분해야 한다.

1) 재귀 열거 언어 (Recursively Enumerable, RE)

• 정의: TM이 인식(Recognize)하는 언어.
• 언어에 속하는 문자열($w \in L$)에 대해서는 반드시 정지(Halt)하고 Yes를 뱉는다.
• 주의: 언어에 속하지 않는 문자열($w \notin L$)에 대해서는 무한 루프(Loop)를 돌 수도 있다. 즉, No라고 답하지 않고 영원히 돌 수 있다.

2) 재귀 언어 (Recursive Language)

• 정의: TM이 결정(Decide)하는 언어.
• 모든 입력에 대해 무조건 정지(Halt)해야 한다.
• 언어에 속하면 Yes, 속하지 않으면 No 상태로 가서 멈춘다.
• Church-Turing 명제: "재귀 언어 = 컴퓨터로 계산(해결) 가능한 문제"라고 정의한다.

정리:

• $L$과 $\bar{L}$(보수)이 모두 재귀 열거(RE)라면, $L$은 재귀(Recursive) 언어이다.
• 즉, Yes일 때도 멈추고 No일 때도 멈추는 기계를 각각 만들 수 있다면, 둘을 합쳐서 완벽한 판별기를 만들 수 있다.

참고로 재귀 언어이면 당연히 재귀 열거 언어이다.

---

3. 계산 불가능성 (Undecidability)

튜링 머신으로도 풀 수 없는 문제들이 존재한다. 가장 유명한 것이 Halting Problem이다. 그밖에도 Post 대응 문제, Rice's Theorem 등이 계산 불가능함이 증명되어 있다.

1) 정지 문제 (Halting Problem)

• 문제: 임의의 TM $M$과 입력 $w$가 주어졌을 때, "$M$이 $w$를 입력받아 정지할 것인가?"를 결정하는 문제.
• 언어 정의: $L_u = \{ \langle M, w \rangle : w \in L(M) \}$.
• 결론: 이 문제는 계산 불가(Undecidable)이다. 즉, $L_u$는 재귀 언어가 아니다.

증명: 대각선 논법 (Diagonalization Method)

이 증명은 실수의 집합이 자연수의 집합보다 크다는 것을 증명한 '칸토어의 대각선 논법'을 응용한 것이다.

1. Setup
모든 튜링 머신(TM)은 이진 문자열로 인코딩할 수 있으므로, 세상에 존재하는 모든 TM을 $M_1, M_2, M_3, \dots$와 같이 순서대로 나열할 수 있다. (가산 집합)
입력값 역시 $w_1, w_2, w_3, \dots$로 나열할 수 있다.

이제 모든 TM과 모든 입력에 대한 정지 여부를 표(Table)로 만들어 보자.
($H$는 정지하면 Accept(A), 정지하지 않으면 Loop(L)라고 판정한다고 가정)

기계 \ 입력	$\langle M_1 \rangle$	$\langle M_2 \rangle$	$\langle M_3 \rangle$	$\langle M_4 \rangle$	$\dots$
$M_1$	A	A	L	A	$\dots$
$M_2$	L	L	L	A	$\dots$
$M_3$	A	A	A	L	$\dots$
$M_4$	L	L	A	L	$\dots$
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\ddots$

위 표에서 대각선 성분(밑줄 친 부분)은 기계 $M_i$에게 자기 자신의 코드 $\langle M_i \rangle$를 입력했을 때의 결과($M_i(\langle M_i \rangle)$)를 나타낸다.

2. The Diagonal Killer
이제 대각선에 있는 값들을 뒤집어서(Flip) 행동하는 새로운 기계 $D$를 정의한다.

• 대각선이 A (Accept)이면 $\rightarrow$ $D$는 L (Loop)
• 대각선이 L (Loop)이면 $\rightarrow$ $D$는 A (Accept)

즉, $D$의 동작은 다음과 같다.

3. Contradiction
만약 정지 문제를 판별할 수 있다면, 이 기계 $D$도 분명히 튜링 머신이므로 위 표의 어딘가(행)에 존재해야 한다.
$D$가 표의 $k$번째 줄($M_k$)에 있다고 가정해 보자. ($D = M_k$)

이제 $D$에게 자기 자신($\langle D \rangle$)을 입력으로 주면 무슨 일이 생길까? (표의 $k$행 $k$열)

• 만약 $D$가 정지한다면(Accept)?
  • 정의에 따라 대각선 값을 뒤집어야 하므로 $D$는 무한 루프(Loop)를 돌아야 한다. $\rightarrow$ 모순!
• 만약 $D$가 무한 루프라면(Loop)?
  • 정의에 따라 대각선 값을 뒤집어야 하므로 $D$는 정지(Accept)해야 한다. $\rightarrow$ 모순!

4. 결론
기계 $D$는 표 안의 어떤 행($M_k$)과도 일치할 수 없다. (적어도 대각선 위치에서는 값이 다르기 때문)
하지만 우리는 처음에 "모든 튜링 머신을 나열했다"고 가정했다.
따라서 $D$ 같은 기계를 만들어내는 전제 조건, 즉 "정지 문제를 판별하는 기계 $H$가 존재한다"는 가정이 틀렸다.

2) 포스트 대응 문제 (Post Correspondence Problem, PCP)

• 문제: 위/아래가 다른 문자열로 된 타일들이 주어졌을 때 ($u_1/v_1, \dots, u_n/v_n$), 타일들을 잘 배열해서 위쪽 문자열 합과 아래쪽 문자열 합이 같게 만들 수 있는가?
• 결론: 이 문제는 계산 불가이다.

3) Context-free Grammar(CFG) 관련 불가능한 문제들

다음 문제들은 튜링 머신으로 결정할 수 없다 (Undecidable).

• 두 CFG $G_1, G_2$에 대해 교집합이 공집합인가? ($L(G_1) \cap L(G_2) = \emptyset?$)
• CFG $G$가 팰린드롬(Palindrome)인 문자열을 포함하는가?
• CFG $G$가 모든 문자열을 생성하는가? ($L(G) = \Sigma^*$?)

4) 라이스 정리 (Rice's Theorem)

정지 문제가 "프로그램이 멈출지 알 수 없다"는 것이었다면, 라이스 정리는 이를 일반화하여 "프로그램의 행동(Semantic)에 관한 그 어떤 질문도 결정할 수 없다"는 강력한 정리이다.

정리: 튜링 머신이 인식하는 언어 $L(M)$에 대해, 비자명한(Non-trivial) 성질 $P$를 판별하는 문제는 결정 불가능(Undecidable)하다.

의미 분석

1. 비자명한 성질(Non-trivial):
   • 모든 튜링 머신이 다 가지고 있거나(All), 아무도 가지고 있지 않은(None) 뻔한 성질이 아닌 것.
   • 즉, "어떤 프로그램은 만족하고, 어떤 프로그램은 만족하지 않는" 유의미한 특징들.
2. 문법 vs 행동:
   • "코드에 if문이 있는가?" 같은 코드 자체(문법)에 대한 검사는 가능하다.
   • 하지만 "이 코드가 hello를 출력하는가?" 같은 실행 결과(행동)에 대한 검사는 불가능하다.

현실 세계에 주는 시사점 (무결성 검증의 한계)

이 정리는 소프트웨어 공학적으로 매우 중요한 절망적인(?) 사실을 알려준다.

1. 완벽한 버그 검사기(Verifier)는 불가능하다.
   • "이 프로그램이 버그 없이 명세서대로 완벽하게 동작하는가?"를 자동으로 판별하는 프로그램은 존재할 수 없다.
   • 따라서 우리는 정적 분석, 테스트 코드, QA 등 보조적인 수단을 쓸 뿐, 수학적으로 완벽한 검증은 불가능하다.
2. 완벽한 악성코드 탐지기(Antivirus)는 불가능하다.
   • "이 프로그램이 바이러스(악성 행위)인가?"를 결정하는 것 역시 행동에 관한 문제이므로 불가능하다.
   • 백신 프로그램들이 특정 패턴(Signature)을 검사하는 방식에 의존하는 이유가 바로 이것이다.

결론: 우리는 프로그램의 소스 코드만 보고 그 프로그램이 런타임에 정확히 어떤 행동을 할지 완벽하게 예측하는 알고리즘을 만들 수 없다.

---

튜링머신이 탄생하게 된 역사적 맥락이나 motivation에 대한 인사이트는 아래 포스트를 참고
https://velog.io/@jm-sens/Fundamentals-of-ECE-1