Turing Machines

상위 문서: 계산 이론 개론

개요

튜링 머신(Turing Machine)은 계산의 본질을 단순한 모델로 표현한 이론적 컴퓨터 모델이다. 튜링 머신은 모든 계산 가능한 것을 정의하는 최초의 이론적 모델로서 현대 컴퓨터의 이론적 토대를 마련했다. 또한 , 튜링 머신을 통해 계산 가능성의 한계를 증명하고, 어떤 언어의 능력을 평가하는 '튜링 완전성' 개념의 기반이 되었다.

Basic Concepts of Turing Machines

튜링 머신의 핵심적인 구성요소는 Control unit, Tape, Read/Write Head이다:

1. Control unit: Control unit은 유한한 상태 집합 Q 중 하나의 상태에 머물며 작동한다.
   • 현재 상태를 기억하고 다음 동작을 결정하는 역할을 한다.
2. Tape: 무한히 긴 1차원 테이프이며, 칸에는 하나의 기호(symbol)를 쓸 수 있다.
   • 이때 사용할 수 있는 기호들의 집합을 테이프 알파벳[math]\displaystyle{ (\Gamma) }[/math]이라고 한다.
3. Read/Write Head: 한 번에 한 칸씩 왼쪽(L) 또는 오른쪽(R)으로 이동하면서, 현재 칸의 기호를 읽거나 바꾼다.

튜링 머신은 위의 구성 요소를 바탕으로 유한한 개수의 명령(전이 함수, transition function)을 따라서 작동한다.

Mathematical Formalization

튜링 머신은 아래와 같은 7-튜플([math]\displaystyle{ Q, \Sigma, , \Gamma, \delta, q_0, q_{accept}, q_{reject} }[/math])을 통해서 정의된다:

1. [math]\displaystyle{ Q }[/math]: 상태들의 유한 집합(states)
2. [math]\displaystyle{ \Sigma }[/math]: 입력 알파벳 (input alphabet)
3. [math]\displaystyle{ \Gamma }[/math]: 테이프 알파벳 (tape alphabet), [math]\displaystyle{ \Sigma \in \Gamma, \textvisiblespace \in \Gamma }[/math]
4. [math]\displaystyle{ \delta }[/math]: 전이 함수(transition function)이며, 아래와 같은 형식이다:
   [math]\displaystyle{ \delta: Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\} }[/math]
5. [math]\displaystyle{ q_0 }[/math]: 시작 상태(start state)
6. [math]\displaystyle{ q_{accept} }[/math]: 받아들이는 상태(accept state)
7. [math]\displaystyle{ q_{reject} }[/math]: 거부 상태(reject state)

튜링 머신의 전이 함수를 풀어 설명하면, 아래와 같은 형태이다:

“만약 현재 상태가 q이고, 테이프에서 기호 a를 읽었다면,

이를 기호 b로 바꾸고, 머리를 L 또는 R로 한 칸 이동한 뒤, 상태를 r로 바꿔라.” 즉, 명령은 (q, a) → (r, b, L/R)과 같이 정의된다고 할 수 있다.

튜링 기계의 형식적 정의는 사람마다 약간씩 다를 수 있다. 예를 들어, reject 상태를 따로 두지 않고 accept 상태 만을 정의하고 나머지는 자동으로 reject로 간주하기도 한다. 또한 테이프의 왼쪽 끝 표시(left-end marker)를 따로 두어 기계가 더 이상 왼쪽으로 이동하지 않도록 제한하기도 하기도 한다. 해당 위키에서 참조하는 Michael Sipser의 『Introduction to the Theory of Computation, Third Edition』에서도 아래와 같이 추가적인 정의를 추가한다:

"어떤 구성 [math]\displaystyle{ (u,q,v) }[/math]에서 [math]\displaystyle{ q\in \{q_{accept},q_{reject}\} }[/math]일 때, 반드시 하나의 후속 구성(successor configuration)을 가진다."

이는 모호하지 않은(결정적) 동작을 보장하여 결정적 튜링 머신(Deterministic Turing Machine)을 전제로 하기 위한 것이다.

Configurations of Turing Machines

튜링 머신에서의 구성(Configuration)이란 튜링 머신의 현재 상태 전체를 나타내는 한 단위 상태이다. 이는 아래와 같이 정의된다:

[math]\displaystyle{ (u,q,v) }[/math]

이때 [math]\displaystyle{ q \in Q }[/math]는 현재 튜링 머신이 위치한 상태를 나타낸다. 또한 [math]\displaystyle{ u \in \Gamma* }[/math]는 헤드의 왼쪽에 있는 테이프 내용을, [math]\displaystyle{ v\in \Gamma^+ }[/math]는 헤드의 오른쪽에 있는 테이프 내용을 의미한다. 예를 들어 [math]\displaystyle{ (u,q,v)= (101, q_3, 0\textvisiblespace\textvisiblespace\textvisiblespace) }[/math]와 같이 구성이 주어지면, 현재 상태는 [math]\displaystyle{ q_3 }[/math]이며, 테이프 왼쪽에는 "101"이, 오른쪽에는 "0"과 공백이 있다는 것을 의미한다. 이때 공백은 테이프 위에서 아무것도 적혀 있지 않은 칸을 의미하며, 입력 이외의 칸을 나타내기 위해 사용하는 심볼이다. 이때 중요한 것은 오른쪽 끝의 공백은 몇 개가 있든 동일한 구성으로 간주한다. 이는 아래와 같이 나타낼 수 있다:

[math]\displaystyle{ (u,q,v\textvisiblespace^n)=(u,q,v\textvisiblespace^m) for\,\, n,m\ge 0 }[/math]

이는 튜링 기계가 “무한히 많은 빈 칸”을 상정하므로, 불필요한 공백 개수는 의미가 없기 때문이다.

아래 표는 튜링 머신이 계산을 시작하거나 끝내는 특수 상태들을 열거한 것이다:

구성 유형	형태
시작 구성 (Start configuration)	[math]\displaystyle{ q_0w }[/math]
Accept 구성 (Accepting)	[math]\displaystyle{ uq_{accept}v }[/math]
Reject 구성 (Rejecting)	[math]\displaystyle{ uq_{reject}v }[/math]

이때 어떤 튜링 머신 M이 [math]\displaystyle{ w }[/math]를 accept한다고 하는 것은 아래 조건들을 만족하는 구성열(sequence)이 존재할 때이다:

1. [math]\displaystyle{ C_1=q_0w }[/math]
2. 중간의 [math]\displaystyle{ C_i }[/math]들은 accept/reject가 아닌 일반 상태
3. 각 [math]\displaystyle{ C_i }[/math]는 [math]\displaystyle{ C_{i+1} }[/math]을 yield함
4. 마지막 [math]\displaystyle{ C_k }[/math]는 accepting configuration

즉, [math]\displaystyle{ C_1 \Rightarrow C_2 \Rightarrow \cdots \Rightarrow C_k }[/math]이고, [math]\displaystyle{ C_k }[/math]가 accept 상태에 도달하면 문자열 [math]\displaystyle{ w }[/math]는 accept된다.

The Yields Relation

튜링 머신이 한 단계에서 다음 단계로 이동하는 규칙은 [math]\displaystyle{ \delta }[/math]와, 해당 튜링머신의 구성을 통해 정의된다. 예를 들어,

Configuration [math]\displaystyle{ C_1 }[/math] yields [math]\displaystyle{ C2 }[/math]

는 주어진 튜링 머신의 상태가 단 한번의 동작으로 [math]\displaystyle{ C_1 }[/math]에서 [math]\displaystyle{ C_2 }[/math]로 바뀐다는 것을 의미한다. 이때, 이 yield 관계(relation)는 전이함수 [math]\displaystyle{ \delta }[/math]에 의해서 결정된다. 이때 yield 관계는 아래와 같이 구분된다:

1. 왼쪽으로 이동 (Move Left)
   • [math]\displaystyle{ q_ibv }[/math] yields [math]\displaystyle{ q_jcv,\,\,if\,\, \delta(q_i,b)=(q_j,c,L) }[/math]: 단순히 머리 위치를 그대로 두고, 공백을 유지한다.
   • [math]\displaystyle{ uaq_ibv }[/math] yields [math]\displaystyle{ uq_jacv,\,\,if\,\, \delta(q_i,b)=(q_j,c,L) }[/math]: [math]\displaystyle{ b }[/math]를 [math]\displaystyle{ c }[/math]로 바꾸고 왼쪽으로 이동하여 왼쪽 기호 [math]\displaystyle{ a }[/math] 위로 헤드를 옮긴다.
2. 오른쪽으로 이동 (Move Right)
   • [math]\displaystyle{ uaq_ib }[/math] yields [math]\displaystyle{ uacq_j\textvisiblespace,\,\,if\,\, \delta(q_i,b)=(q_j,c,R) }[/math]: 공백(blank)을 새로 하나 추가해야 한다.
   • [math]\displaystyle{ uaq_ibv }[/math] yields [math]\displaystyle{ uacq_jv,\,\,if\,\, \delta(q_i,b)=(q_j,c,R) }[/math]: [math]\displaystyle{ b }[/math]를 [math]\displaystyle{ c }[/math]로 바꾸고, 한 칸 오른쪽으로 이동한다.

Deciders and Languages

어떤 튜링 머신 [math]\displaystyle{ M }[/math]이 decider라고 불리기 위해서는 입력 문자열에서 출발했을 때, 영원히 멈추지 않고 돌기만 하는 경우가 없어야 한다. 즉, 어떤 입력 [math]\displaystyle{ w }[/math]에 대해서도 반드시 Accepting 혹은 Rejecting 구성에 도달해야 한다. 이때 모든 튜링 기계가 Decider인 것은 아니며, 어떤 기계는 특정 입력에서 무한 루프에 빠질 수도 있다. 이러한 경우를 recognizer라고 부른다. 이에 따라 튜링 기계가 인식(recognize)하거나 결정(decide)할 수 있는지 여부에 따라 언어(Language)의 종류를 구분할 수 있다. 아래는 이를 정리한 표이다:

구분	정의	특징
Turing-recognizable	어떤 튜링 기계 M이 있어서, L=L(M) 일 때	입력이 언어에 속하면 Accept, 속하지 않으면 멈추지 않고 무한 루프 가능
Turing-decidable	어떤 Decider M이 있어서, L=L(M) 일 때	모든 입력에 대해 반드시 멈추며, Accept 또는 Reject 중 하나 출력

이때 모든 Decidable 언어는 Recognizable 언어이지만, 그 반대(Recognizable → Decidable)는 성립하지 않는다. 이때 중요한 것은, "모든 정규 언어가 튜링 기계로 결정 가능하다(decidable)"하다는 것이다. 언어를 입력받을 때, 해당 입력이 끝나는 것은 공백(blank symbol)을 통해 판단한다. 즉, 입력을 다 읽고 처음 만나는 blank가 입력의 끝이다.

Turing Machine Hacking

튜링 머신은 프로그래밍 언어처럼 다룰 수 있으며, 해당 문단에서는 튜링 머신을 활용한 여러 테크닉에 대해 설명한다. 튜링 머신도 프로그래밍 언어처럼 패턴과 관용구(idiom)가 존재하며, 입력의 끝을 찾거나, 테이프의 처음으로 돌아가거나, 특정 영역을 표시하는 등의 “기본 동작”들을 잘 다루면 복잡한 계산을 구현할 수 있다.

먼저, 입력의 오른쪽 끝을 찾기 위해서는 처음으로 등장하는 [math]\displaystyle{ \textvisiblespace }[/math]를 찾으면 된다. 그 이유는 [math]\displaystyle{ \textvisiblespace }[/math]이 입력 알파벳에는 포함되지 않지만, 튜링 머신의 테이프 알파벳에는 포함되기 때문이다. 이로 인해 튜링 머신의 테이프에는 입력 문자열이 적혀 있고, 테이프의 끝은 [math]\displaystyle{ \textvisiblespace }[/math]으로 채워져 있다.
반대로 테이프의 맨 왼쪽으로 돌아가기 위해서는 첫 단계에서 현재 보고 있는 기호를 기억(finite control)하고, 그 자리를 특별한 마커(symbol)로 바꾼다. 이후 왼쪽으로 계속 이동하다가 그 마커를 만나면 “출발점”을 찾을 수 있다.

테이프의 칸을 “표시(mark)”하는 방법을 확장하면, 테이프 알파벳의 각 기호마다 표시(mark) 여부에 따라 어떤 셀을 “방문했음” 혹은 “처리했음”으로 표시할 때 활용할 수 있다.

이 외에도 표시(mark)를 활용하는 방법으로는 스크래치 영역(scratch) 영역을 임의로 만드는 것이 있다. 예를 들어 프로그래밍에서의 “임시 변수 메모리 영역”을 튜링 머신에서도 활용하기 위해서는 입력의 오른쪽 끝을 찾은 뒤, 그 옆에 특별한 마커를 써서 임시 작업 공간을 확보할 수 있다. 이러한 임시 작업 공간은 필요시 가장 오른쪽으로 가서 해당 마커를 찾아 사용될 수 있다.
스크래치 영역은 마치 호출 스택(call stack)과 같이 활용될 수도 있다. 현재 상태(복귀할 위치)를 스택에 저장하고, 서브루틴의 첫 상태로 점프한 후 끝나면 스택에 저장된 복귀할 위치로 돌아오는 구조를 만들면 된다.
또한 스크래치 영역의 일부를 레지스터 처럼 사용하여 입력의 일부 값을 복사해서 저장하거나, 연산 중간 결과를 보관할 수도 있다.

Turing Machine Variants

튜링 머신은 다양한 확장 버전이 존재한다. 이는 아래와 같다:

1. Multi-track tape: 표준 TM 테이프의 각 칸이 하나의 기호만 저장한다면, 멀티트랙 TM 테이프는 각 칸이 여러 기호 묶음을 저장한다.
2. Two-way infinite tape: 테이프가 오른쪽뿐만 아니라 왼쪽 방향으로도 무한히 뻗어 있다.
3. Multiple tapes with independent heads: 테이프 여러 개이며 각각에 대한 헤드가 따로 존재하여 움직인다.
4. Nondeterminism: 여러 선택지를 동시에 탐색하는 튜링 머신이다.

이때 중요한 것은 튜링머신을 여러 방식으로 강화(멀티트랙, 양방향 테이프, 여러 테이프, 비결정성)해도 ‘어떤 언어를 인식할 수 있는가 / 결정할 수 있는가’라는 능력은 변화하지 않는다는 것이다. 단지 시간과 공간적인 측면에서의 효율성만 달라진다.

TMs as Language Enumerators

튜링머신은 입력을 받아 accept/reject하는 방식으로 언어를 정의할 수도 있지만, 반대로 “언어의 모든 문자열을 하나씩 출력해 나가는 방식”으로도 언어를 정의할 수 있다. 이러한 방식으로 사용되는 기계를 enumerator라고 한다. 이는 테이프 두개를 사용하여 구성된다:

1. 출력 테이프: 오른쪽으로만 움직이며 출력을 하는데에 사용된다. 또한 한번 쓰면 덮어 쓸 수 없다.
2. 작업 테이프: 계산을 하는 데에 사용된다.

튜링 머신은 처음에 두 테이프가 모두 비어있을 떄 시작한다. 이때 튜링 머신이 특수기호 # 을 출력테이프에 찍을 때마다 “한 개의 문자열을 다 출력했다”고 간주한다. 즉, 출력 형식은 아래와 같다:

w1 # w2 # w3 # ...

이렇게 나열된 문자열들의 모임이 해당 튜링 머신이이 열거하는 언어이다. 이때 어떤 언어 L이 Turing-enumerable하다는 것은 어떤 튜링 머신이 L의 모든 가능한 문자열을 출력해낼 수 있다는 것을 의미한다. 이때 중요한 것은 Turing-recognizable과 Turing-enumerable은 동치라는 것이다. 또한 아래의 관계가 성립한다:

Turing-decidable [math]\displaystyle{ \subset }[/math] Turing-recognizable [math]\displaystyle{ \equiv }[/math] Turing-enumerable

이는 decider는 모든 입력에서 halt하는 반면, recognizer는 정답이 맞으면 halt하고 accept, 틀리면 halt하거나 loop해도 되기 때문이다. 즉, decider는 모든 입력에 대해 항상 halt하므로 recognizer의 조건을 더욱 강하게 충족한다.

Using TMs to Compute Functions

튜링머신은 단순히 “accept or reject”만 하는 기계가 아니다. 튜링머신은 입력이 주어지면 어떤 출력을 만들어내는 계산 장치로도 사용할 수 있다. 예를 들어, 함수 [math]\displaystyle{ f(w)=x }[/math]를 계산하기 위해서는 입력 [math]\displaystyle{ w }[/math]를 어떤 튜링 머신 M을 사용하여 출력 [math]\displaystyle{ x }[/math]를 얻으면 된다. 하지만 TM이 모든 입력에서 반드시 halt하는 것이 아니기 때문에 튜링머신이 계산하는 함수는 부분 함수(partial function)일 수 있다. halt하지 않으면 튜링머신이 무한루프에 빠지고, 이는 출력이 만들어지지 않는 상황이기 때문이다.

일반적인 함수 [math]\displaystyle{ f }[/math]는 아래의 조건을 만족하는 [math]\displaystyle{ \Sigma*\times\Sigma* }[/math]의 부분집합으로 정의된다:

[math]\displaystyle{ (w,x)\in f\land (w,y)\in f\rightarrow x=y }[/math]

이때 total function [math]\displaystyle{ f }[/math]는 모든 입력 [math]\displaystyle{ w }[/math]에 대해서 어떤 출력 [math]\displaystyle{ x }[/math]가 존재하는 것으로 정의된다.

튜링머신에 의해서 계산되는 함수 [math]\displaystyle{ f(M) }[/math]은 아래와 같이 정의된다:

[math]\displaystyle{ f(M)=\{(w,x)|M }[/math]이 입력 [math]\displaystyle{ w }[/math]를 주었을 때 halt하고 accept했으며, accept 순간 테이프의 내용이 [math]\displaystyle{ x }[/math]인 경우[math]\displaystyle{ \} }[/math]

즉, [math]\displaystyle{ f(M) }[/math]이 [math]\displaystyle{ w }[/math]를 입력으로 받아 accept 상태로 멈추고 그 순간 테이프가 [math]\displaystyle{ x }[/math]를 담고 있다면 그때 [math]\displaystyle{ (w,x) }[/math]가 [math]\displaystyle{ f(M) }[/math]의 입력/출력 쌍이 된다는 것이다. 하지만 튜링머신에서 출력 [math]\displaystyle{ x }[/math]가 [math]\displaystyle{ x\notin \Sigma* }[/math]이라면 이는 유효한 입력/출력 쌍이 되지 않는다. 이때 [math]\displaystyle{ f }[/math]가 어떤 튜링머신 [math]\displaystyle{ M }[/math]에 의해서 partial function이라면 [math]\displaystyle{ f }[/math]는 computable partial function이라고 한다. 또한 [math]\displaystyle{ f }[/math]가 total이고, 튜링머신이 모든 입력에서 halt해 결과를 준다면 [math]\displaystyle{ f }[/math]는 total computable function이다.

Church-Turing Thesis

Church-Turing Thesis는 어떤 합리적인(reasonable)” 알고리즘이든, 그것이 언어 L을 결정하거나 인식하거나 함수를 계산하는 방식이든, 결국 그 능력은 튜링머신으로 표현 가능한 계산 능력과 완전히 동일하다는 것을 의미한다. 이때 “Reasonable"이라는 말의 의미는 아래와 같다:

1. 계산 기계는 유한한 규칙으로 동작하고, 필요한 만큼 확장 가능한 저장소(메모리)를 사용한다.
   • 실제 컴퓨터, RAM, 종이와 연필, 계산기 등 모두가 이에 해당한다.
   • 튜링머신도 테이프가 무한하다고 가정한다.
2. 알고리즘은 기본 연산들의 유한한 집합으로 표현될 수 있다.
   • 우리가 짜는 프로그램이든, 사람이 수행하는 알고리즘이든 “유한한 규칙, 단계, 연산”으로 되어 있어야 한다는 것을 의미한다.
   • 튜링머신도 유한한 상태·전이 표로 정의된다.
3. 각 기본 연산은 유한 시간 안에 수행되며 유한한 저장을 사용한다.
   • 무한한 계산 단계를 한 번에 수행하는 “초능력” 연산은 허용되지 않는 다는 것을 의미한다.
   • 튜링머신도 한 스텝씩 움직이며 작동한다.
4. 각 기본 연산의 효과는 예측 가능해야 한다.
   • 같은 상태·조건에서 항상 같은 결과를 내야하며, 비결정적·무작위적 초능력은 허용되지 않는 다는 것을 의미한다.
   • 튜링머신은 완전히 기계적·결정적 규칙으로 작동한다.

따라서 결론적으로 Church-Turing Thesis에 대해서 설명하면 아래와 같다:

• 언어 L을 어떤 알고리즘이 결정(decide)할 수 있다면 → TM도 할 수 있다
• 언어 L을 어떤 알고리즘이 인식(recognize)할 수 있다면 → TM도 할 수 있다
• 어떤 알고리즘이 어떤 partial function을 계산한다면 → TM으로도 계산 가능
• 어떤 알고리즘이 어떤 total function을 계산한다면 → TM으로도 계산 가능

즉, 컴퓨터로 할 수 있는 계산은 튜링머신으로 할 수 있는 계산과 정확히 동일하다. 이는 "알고리즘" 자체가 엄밀하지 않은 개념이기에 수학적으로 증명되지 않은 명제이지만, 경험적으로 매우 강력하게 지지된다.

Encoding Objects as Strings

컴퓨터 이론(특히 decidability/complexity)은 모든 입력을 문자열 형태로 다루기 때문에, DFA나 튜링 머신과 같은 복잡한 “기계”도 문자열 형태로 인코딩해야 한다. 이는 튜링머신은 “입력 테이프”에 문자열만을 읽어 들이며, 컴퓨터 이론에서는 이런 "기계"들을 입력으로 분석하는 문제를 다루기 때문이다. 예를 들어 아래는 DFA의 transition function을 튜플들의 나열로 표현한 것이다.

[math]\displaystyle{ (q_1\#a_1\#b_1)(q_2\#a_2\#b_2)\cdots(q_n\#a_n\#b_n) }[/math]

위에서 [math]\displaystyle{ q_i }[/math]는 DFA의 상태를, [math]\displaystyle{ a_i }[/math]는 입력 심볼을, [math]\displaystyle{ b_i }[/math]는 다음 상태를 의미한다. 이때 중간의 [math]\displaystyle{ \# }[/math]은 객체를 구분하기 위한 구분자로서 사용되었다. 이를 통해서 튜링머신이 이 문자열을 "읽고 파싱함"으로써 DFA의 구조를 이해하는데 사용할 수 있다. 이때 상태나 입력 심볼이 많아질수록, 알파벳으로 표현하면 길이가 매우 길어진다. 따라서 이를 단순화 하기 위해서 상태/심볼을 이진수로 표현하여야 한다. 예를 들면 아래와 같다:

[math]\displaystyle{ (q1 \rightarrow 0000) }[/math]
[math]\displaystyle{ (a1 \rightarrow 00) }[/math]
[math]\displaystyle{ (b1 \rightarrow 0001) }[/math]
[math]\displaystyle{ (0000\#00\#0001) }[/math]

이러한 방식으로 모든 전이함수를 이진수로 인코딩할 수 있다. 이와 같은 방식으로 DFA의 입력 테이프에 올라가는 문자열을 길이 제한 없이 표현하기 위해 입력 문자열도 아래와 같이 인코딩 가능하다:

[math]\displaystyle{ (00\#01\#10\#00\#00\#11) }[/math]

이때 기계, 그래프, 정수 등의 어떤 객체 [math]\displaystyle{ x }[/math]를 문자열로 나타낸 것을 [math]\displaystyle{ \langle x\rangle }[/math]과 같이 표현할 수 있다. 예를 들어, [math]\displaystyle{ \langle DFA\rangle }[/math]는 DFA를 문자열로 encode한 것이고, [math]\displaystyle{ \langle G\rangle }[/math]은 그래프를 문자열 형태로 나타낸 것이다.

Decidability and Complexity

문제의 결정가능성(decidability)에 대해서 고려할 때에는 인코딩의 길이와 방식같은 세부적인 사항이 문제되지 않는다. 이는 입력의 길이와 형식이 문제 풀이의 가능 여부에 영향을 미치지 않기 때문이다. 하지만 문제의 복잡도(complexity)를 고려할 때에는 인코딩의 길이가 큰 영향을 끼친다. 이는 인코딩의 길이가 입력 크기 n에 대해 직접적으로 영향을 미치기 때문이다. 따라서 이 경우에는 엄격하게 binary encoding을 규정해야 한다.

Relationship between Classes of Languages

아래는 컴퓨터 이론에서 다루는 언어(문자열 집합)들의 계층 관계를 나타낸 것이다:

Regular [math]\displaystyle{ \subseteq }[/math] CFL [math]\displaystyle{ \subseteq }[/math] Decidable [math]\displaystyle{ \subseteq }[/math] Recognizable [math]\displaystyle{ \subseteq }[/math] Other

안쪽일수록 단순한 기계로 인식 가능한 언어이고, 바깥으로 갈수록 더 강력한 계산 모델이 필요하다. 이는 단순히 “복잡성의 차이”가 아니라, 바로 결정 가능성(decidability) 과 직접적으로 연결된다. 언어 클래스가 바깥으로 갈수록 “결정 가능한 것”에서 점점 벗어나기 때문이다. 아래는 각 언어들에 대한 설명이다:

1. Regular, Context-Free 언어: 둘 다 결정 가능(decidable)
   • Regular 언어 → DFA/NFA는 항상 결정 가능
   • Context-Free 언어 → CYK algorithm, deterministic PDA 등으로 항상 결정 가능
2. Decidable 언어: 모든 입력에서 halt 하는 튜링머신이 있는 언어
   • 따라서 모든 decidable 언어는 알고리즘으로 완전히 판정 가능한 언어들이다.
3. Turing-recognizable 언어: 어떤 입력에 대해 halt하지 않고 무한 loop를 돌 수도 있다.
4. Recognizable 바깥의 언어들: 이는 더 심각한 수준의 undecidable 언어들이며, 어떤 알고리즘도 해당 언어를 인식조차 못한다.

Undecidability

위에서 언급하였듯이, 어떤 언어들은 Turing-recognizable조차 될 수 없는 undeterministic 언어이다. 이는 아래와 같은 논증을 통해 증명될 수 있다:

1. 모든 튜링 머신은 유한한 문자열로 인코딩할 수 있는데, 유한 문자열 집합 [math]\displaystyle{ \Sigma* }[/math]은 countable이다.
2. 언어는 [math]\displaystyle{ \Sigma* }[/math]의 부분집합이므로, 부분집합 전체는 [math]\displaystyle{ \mathcal{P}(\Sigma*) }[/math]이므로 uncountable하다.
3. 따라서 모든 언어 중 대다수는 튜링 머신으로 인식(recognize)조차 할 수 없다.

또한 recognizable이지만 decidable은 아닌 언어들이 존재한다는 것은 계산할 수 있는 것에는 본질적 한계가 있다는 것을 의미한다.

Universal Turing Machine

아래와 같은 언어 [math]\displaystyle{ A_{TM} }[/math]을 고려해보자:

[math]\displaystyle{ A_{TM}=\{\langle M, w\rangle|M\,\,\, acept \,\,\, w\} }[/math]

이러한 언어 [math]\displaystyle{ A_{TM} }[/math]은 입력으로 받은 [math]\displaystyle{ \langle M, w\rangle }[/math] 튜링 머신 [math]\displaystyle{ U }[/math]를 재구성한다. 튜링 머신 [math]\displaystyle{ U }[/math]는 [math]\displaystyle{ M }[/math]을 [math]\displaystyle{ w }[/math]에 대해 시뮬레이션하며, [math]\displaystyle{ M }[/math]이 accept/reject하면 [math]\displaystyle{ U }[/math]도 이에 따라 accept/reject한다. 물론 [math]\displaystyle{ M }[/math]이 무한 루프면 [math]\displaystyle{ U }[/math]도 멈추지 않고 무한 루프를 돈다. 이때, 다른 모든 튜링 머신 [math]\displaystyle{ M }[/math]을 입력받아 [math]\displaystyle{ w }[/math]에 대해 시뮬레이션하는 튜링 머신 [math]\displaystyle{ U }[/math]를 Universal 튜링 머신이라고 한다.

Undecidablity of Universal TM

이때 [math]\displaystyle{ A_{TM} }[/math]은 undecidable하다. 이를 증명하기 위해서는 아래와 같은 decider [math]\displaystyle{ H }[/math]가 있다고 가정해야 한다:

입력: [math]\displaystyle{ \langle M, w\rangle }[/math]
출력: [math]\displaystyle{ M }[/math]이 [math]\displaystyle{ w }[/math]를 accept하면 → H accepts
     [math]\displaystyle{ M }[/math]이 [math]\displaystyle{ w }[/math]를 reject하면 → H rejects
     [math]\displaystyle{ M }[/math]이 loop해도 [math]\displaystyle{ H }[/math]는 반드시 accept/reject 중 하나를 출력한다.

하지만 이는 모순을 일으킨다. 또한 아래와 같은 universal 튜링머신 [math]\displaystyle{ D }[/math]를 만들어야 한다:

입력: [math]\displaystyle{ \langle M \rangle }[/math]
동작: [math]\displaystyle{ H(\langle M, \langle M\rangle \rangle) }[/math]을 실행한다.
출력: [math]\displaystyle{ H }[/math]의 답을 뒤집는다. 
       H가 accept → D는 reject
       H가 reject → D는 accept
[math]\displaystyle{ \therefore\,\,\, D(M)=not \,\,\, H(\langle M, \langle M \rangle \rangle) }[/math]

즉, [math]\displaystyle{ D }[/math]는 "M 자기 자신에 대해 M이 무엇을 하는지"를 무조건 반대로 따라 한다. 이때 [math]\displaystyle{ D(\langle D \rangle) }[/math]을 실행하면, 이는 모순을 일으킨다. 먼저 [math]\displaystyle{ D(\langle D \rangle)=accept }[/math]이면, [math]\displaystyle{ H(\langle M, \langle M \rangle \rangle) }[/math]은 D가 자기 자신을 accept한다고 판단하였으므로, [math]\displaystyle{ D }[/math]는 이를 뒤집어 reject해야 하기 때문이다. 이는 모순을 일으키며, [math]\displaystyle{ D(\langle D \rangle)=reject }[/math]일 때에도 마찬가지로 모순을 일으킨다. 따라서 [math]\displaystyle{ H }[/math]는 실제로 존재할 수 없으며, [math]\displaystyle{ A_{TM} }[/math]은 undecidable하다.

이때 [math]\displaystyle{ D }[/math]가 decidable하기 위해서는 [math]\displaystyle{ L(D) }[/math]와 [math]\displaystyle{ L(D) }[/math]의 여집합이 모두 recognizable해야 한다. 이때 [math]\displaystyle{ A_{TM} }[/math]은 recognizable하므로, [math]\displaystyle{ A_{TM} }[/math]의 여집합은 unrecognizable하다.