[계산이론] #08. Enumerability

Rice's Theorem

세상에 존재하는 모든 TM의 Binary Encoding의 집합, $T$를 정의합시다. Rice's Theorem은 아래와 같이 $T$의 부분집합 $P$를 정의하면 $P$는 Undecidable이라는 것입니다.

1. $P \neq \pi$
2. $P \neq T$
3. $L\left ( M_1 \right )=L\left ( M_2 \right )$인 임의의 두 TM $M_1$과 $M_2$에 대해 $\left< M_1 \right>\in P$ and $\left< M_2 \right>\in P$ 이거나, $\left< M_1 \right>\notin P$ and $\left< M_2 \right>\notin P$

 

1, 2번 규칙은 $P$가 공집합도 아니고, 모든 TM을 포함하는 집합도 아니라는 조건을 위한 것입니다. 중요한 것은 3번째 규칙입니다. 이 규칙은 직관적으로 알 수 있듯 어떤 $M$이 $P$의 원소인지 아닌지는 $M$ 그 자체가 아닌 $L\left(P\right)$에 따라서 결정된다는 뜻입니다.

예를 들어, 아래 3개의 Language는 Rice's Theorem에 의해 전부 Undecidable입니다.

$$P_1=\left\{\left<M \right>:\epsilon \in L\left ( M \right ) \right\}$$

$$P_2=\left\{\left<M \right>:L\left ( M \right )=\left\{1011, 00011000 \right\} \right\}$$

$$P_3=\left\{\left<M \right>:L\left ( M \right ) \ is \ regular \right\}$$

 

이제 Rice's Theorem을 한번 증명해 보겠습니다. 먼저 $P$가 Decidable이라고 가정한 뒤에, $Halt$가 Decidable임을 보일 것입니다. 그러면 이는 모순이 되므로 $P$가 Undecidable임이 증명됩니다.

$P$가 Decidable하다고 가정했으므로, $P$에 대응되는 TM이 존재할 것입니다. 이 TM을 $H$라고 하겠습니다. 그리고 $M_1$은 첫 번째 단계가 진행되면 곧바로 Reject State로 전환되는 TM이라고 하겠습니다. 그러면 $M_1$을 Accept 하는 문자열은 존재하지 않으므로 $L\left(M_1\right)=\pi$가 됩니다. 이제 $\left< M_1 \right>\notin P$라고 가정하겠습니다. (마지막 부분에 $\left< M_1 \right>\in P$인 경우에서도 증명을 진행합니다.) $\left< M_2 \right>\in P$ 인 TM $M_2$를 잡아줍시다.

여기서 아래와 같이 동작하는 Turing Machine $T_{M_w}(x)$를 생각하겠습니다.

1. $M$에 $w$를 넣었을 때 $M$이 Terminate 될 경우
   1. $M_2$에 $x$를 넣어 $M_2$가 Accept 할 경우
      1. $T_{M_w}(x)$는 Accpet State로 Terminate
   2. $M_2$에 $x$를 넣어 $M_2$가 Reject 할 경우
      1. $T_{M_w}(x)$는 Reject State로 Terminate

 

$M$에 $w$를 넣었을 때 Terminate된다고 가정하겠습니다. (즉, $\left< M, w \right>\in Halt$) 그러면, $L\left(T_{M_w} \right)=L\left(M_2\right)$ 입니다. 그러면 Rice Theorem의 3번째 조건에 의해 $\left< M_2 \right>\in P$ 이므로 $\left< M_{M_w} \right>\in P$가 됩니다. 

이번에는 $M$에 $w$를 넣었을 때 Terminate되지 않는다고 가정하겠습니다. (즉, $\left< M, w \right>\notin Halt$) 그러면  $T_{M_w}$는 어떤 Input에도 Terminate 되지 않으므로, $L\left(T_{M_w}\right) = \pi$입니다. 따라서, $L\left(T_{M_w} \right)=L\left(M_1\right)$ 입니다. 그러면 Rice Theorem의 3번째 조건에 의해 $\left< M_1 \right>\notin P$ 이므로 $\left< M_{M_w} \right>\notin P$가 됩니다. 

여기서 아래와 같이 동작하는 Turing Machine$H' \left( \left< M, w \right> \right)$을 생각하겠습니다.

1. $H$에 $\left< T_{M_2} \right>$를 넣었을 때 $H$가 Accept 할 경우
   1. $H'$은 Accept State
2. $H $에 $\left< T_{M_2} \right>$를 넣었을 때 $H$가 Reject 할 경우
   1. $ H'$은 Reject State

 

눈치가 빠르신 분들은 알겠지만, $H'$은 주어진 TM에 주어진 문자열을 넣었을 때 그 결과가 Accept인지 Reject인지 판단하는 Halting Problem을 해결하는 TM입니다.

이제 $\left< M, w \right>\in Halt$인 경우부터 다시 생각해 보겠습니다. $\left< M_{M_w} \right>\in P$로부터 $H'$은 $\left< M, w \right>$를 Accept 합니다.

반대로 $\left< M, w \right>\notin Halt$인 경우를 생각해보겠습니다. 마찬가지로 $\left< M_{M_w} \right>\notin P$로부터, $H'$은Terminate되는 것은 당연하고,  $\left< M, w \right>$를 Reject 합니다.

어라? Halting Problem을 해결하는 $H'$이 생겼습니다. 근데 이런 $H'$은 존재할 수 없으므로, 모순이 발생하게 됩니다.

증명의 제일 첫 번째 과정에서 $\left< M_1 \right>\notin P$라는 가정을 하고 증명을 전개해왔는데요, $\left< M_1 \right>\in P$인 경우도 완전히 똑같지만, $P$를 $\bar{P}$로 바꾸어서 진행하게 되면 $\bar{P}$가 Undecidable임을 증명할 수 있습니다. 모든 Language $L$에 대해서 $L$이 Decidable이면 $\bar{L}$ 역시 Decidable이기 때문에, $P$가 Undecidable임을 증명할 수 있습니다.

 

Enumerability

Alphabet $\Sigma$에 대한 Language $A$가 있다고 생각합시다. 이때, 모든 문자열 $w$에 대해 아래 조건을 만족하는 TM $M$이 존재하면, Language $A$를 Enumerable이라고 부릅니다.

1. $w\in A$일 경우 $M$에 $w$를 넣으면 Accept State로 Terminate 됩니다.
2. $w\notin A$일 경우 $M$에 $w$를 넣으면 Terminate 되지 않거나, Reject State로 Terminate 됩니다.

 

Enumerable Language와 Decidable Language의 차이점은, Decidable Language $A'$의 경우 $A'$은 $w \notin A'$를 입력받았을 때 항상 Reject State로 Terminate 되어야 하지만 Enumerable Language는 그렇지 않다는 것입니다. 따라서, 모든 Decidable Language는 Enumerable Language입니다.

 

Hilbert's Problem

Hilbert's Problem은 수학자 Hilbert가 제시한 23가지의 문제들을 다 같이 묶어서 부르는 말인데요, 저희는 그중에 하나인 11번 문제를 한번 볼 겁니다. (다른 문제들은 다루지 않을 예정이므로, 원래는 "힐베르트 문제 11번"이 맞는 말이지만 편의상 "힐베르트 문제"라고만 부르겠습니다.)

힐베르트 문제는 정수 계수를 가진 다항방정식이 정수해를 가지는지, 가지지 않는지를 판별하는 문제입니다. 정수해를 가지는 정수 계수 다항방정식을 $p$라고 하고, 존재하는 모든 $p$를 Binary String으로 변환한 $\left< p \right>$의 집합을 $Hilbert$라 하겠습니다.

이 전 글에서, 이 $Hilbert$는 Undecidable이라고 말한 적이 있었는데요, 이번 글에서는 $Hilbert$가 Enumerable임을 보일 것입니다. 이를 증명하기 위해서 저희는 알고리즘 Hilbert를 만들 겁니다. 이 Hilbert는 $p$를 입력받아 만약 $p$가 정수해를 가지면 유한한 시간 내에 그 정수해를 찾아내고, 정수해가 없으면 우리에게 정수해가 없다는 사실을 알려주거나 Terminate 되지 않습니다. 이런 알고리즘 Hilbert를 만들면, Language $Hilbert$가 Enumerable임이 바로 증명되는 겁니다.

알고리즘 Hilbert는 어떤 방식으로 동작하느냐? 간단합니다. 가능한 모든 Tuple $\left ( x_1, x_2, ...\cdots, x_n \right ) \in \mathbb{Z}^n$을 전부 $p$에 대입하고, 그 값이 0이면 알고리즘을 Terminate 시키고 Accept합니다. 이제 중요한 것은 어떤 순서로 모든 $ \mathbb{Z}^n $을 시도해 보냐는 것입니다.

먼저 $ \mathbb{Z}^2 $을 예시로 설명을 해보도록 하겠습니다. 가장 먼저 Hilbert는 (0, 0)을 방문합니다. 이를 우리는 $H_0$라고 표현하며, 그림으로 나타내면 아래와 같습니다.

그다음으로 $H_1$을 방문할 건데요, (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0) 등이 이에 해당합니다. 식으로 나타내면 $H_1=\left\{\left ( x_1, x_2 \right ): -1\leq x_1\leq 1, -1\leq x_2\leq 1, \left ( x_1, x_2 \right )\notin H_0 \right\}$ 이며, 그림으로는 아래와 같습니다.

그리고 아래는 다음에 방문할 $H_2$를 나타낸 그림입니다.

이렇게 순서대로 모든 $\mathbb{Z}^2$을 방문할 수 있습니다. 이는 $ \mathbb{Z}^n $으로 쉽게 일반화가 가능합니다.

따라서 위와 같은 알고리즘 Hilbert를 만들 수 있으므로, Language $Hilbert$는 Enumerable 합니다.

 

$A_{TM}$

이 전 글에서 아래와 같은 Language $A_{TM}$이 Undecidable이라는 사실에 대해 알아보았었습니다.

$$A_{TM}=\left\{\left<M,w \right>:M\ is \ TM\ that\ accepts\ w \right\}$$

이 Language는 Decidable하진 않지만 Enumerable이긴 합니다. 위의 예시와 같이 알고리즘 $P$를 만들어서 $A_{TM}$이 Enumerable임을 한번 보여보도록 하겠습니다.

$P$는 $\left< M, w \right>$를 입력받으면 아래와 같이 동작합니다.

1. $M$에 $w$를 넣어 시뮬레이션을 진행합니다.
2. $M$이 Accept State에 도달하면, $P$는 Accept State로 Terminate 됩니다.
3. $M$이 Reject State에 도달하면, $P$는 Reject State로 Terminate 됩니다.
4. $M$이 Terminate 되지 않으면, $P$도 Terminat 되지 않습니다.

 

이렇게 $A_{TM}$이 Enumerable임을 쉽게 증명할 수 있었습니다.

 

Enumerator

Language $A$에 대해, 아래의 조건을 만족하는 Turing Machine $E$를 $A$의 Enumerator라 부릅니다.

$E$에는 Print Tape와 Print State가 존재합니다. 각각의 Step에서 $E$는 Print Tape에 알파벳을 작성합니다. 그리고 $E$가 Print State에 들어가면 현재 Print Tape에 적힌 문자열이 Printer로 보내지고 Print Tape에 있는 알파벳은 전부 지워집니다.

이때, 모든 문자열 $w\in A$는 적어도 한 번은 Printer로 보내지게 되며, 모든 문자열 $w\notin A$는 Printer로 보내지지 않습니다. 즉, $A$의 Enumerator는 $A$의 모든 문자열을 Print 합니다. 정해진 순서는 없으며, 어떤 문자열은 여러 번 출력될 수도 있습니다. 만약 $A$가 무한 집합이라면 $E$는 Terminate 되지 않습니다. 그러나 $A$에 존재하는 모든 문자열은 언젠가 Print 됩니다.

 

이 글로만은 감이 잘 오지 않으실 텐데, 예시를 한번 들어보겠습니다. $A=\left\{0^n: n\geq 0 \right\}$의 Enumerator는 아래와 같이 작동합니다.

1. n ← 0
2. while True do
   1. for i ← 1, n do
      1. write 0 on Print Tape
   2. Enter the Print State
   3. n ← n + 1

 

이 Enumerator의 가장 중요한 성질 중 하나는, Enumerator가 존재하는 Language는 항상 Enumerable이라는 사실입니다. 그 역도 성립합니다.

먼저 Enumerator $E$와 Language $A$가 있을 때, $A$에 대응되는 Turing Machine $M$을 만들어 $A$가 Enumerable임을 증명해 보도록 하겠습니다.

$M\left(w\right)$은 먼저 $E$를 작동시키고, $E$가 Print State로 들어갈 때마다 Print Tape에 적힌 문자열과 $w$를 비교합니다. 만약 같은 경우 $M$은 Accpet 상태로 Terminate 됩니다.

만약 $w\in A$일 경우 $E$가 작동하는 동안 Print Tape에 적힌 문자열과 $w$가 같은 상황이 발생할 것이고, $M$은 Accept State가 됩니다. 하지만 $w\notin A$일 경우 $E$가 계속 작동해도 Print Tape에 적힌 문자열과 $w$가 같은 상황은 일어나지 않으므로 $M$은 Terminate 하지 않습니다. 따라서, 이런 Turing Machine $M$이 존재하므로 $A$는 Enumerable입니다.

 

반대로, $A$가 Enumerable 하다고 가정하고 $E$가 항상 존재함을 보이겠습니다. $A$가 Enumerable 하다는 뜻은, $w\in A$를 입력했을 때 Accept State로 Terminate 되고 $w\notin A$를 입력했을 때 Terminate 하지 않거나 Reject State로 Terminate 되는 Turing Machine $M$이 존재한다는 뜻입니다.

주어진 Alphabet으로 만들 수 있는 모든 문자열의 집합을 $S=\left\{s_1, s_2, s_3, \cdots \right\}$ 라고 하겠습니다. 그러면 아래와 같이 동작하는 Turing Machine $E$를 만들 수 있습니다.

1. n ← 1
2. while True do
   1. for i ← 1, n do
      1. $M$을 Input $s_i$에 대해 n개의 Step만큼 작동시킴
      2. if $M$이 Accept
         1. Print Tape에 $s_i$를 작성
         2. Print State에 진입
   2. n ← n + 1

 

이렇게 동작하는 $E$는 $A$의 Enumerator이므로 그 역도 성립함이 증명되었습니다.

 

마무리

이번 글에서는 Enumerability가 무엇인지, 그리고 Enumerable Language는 어떤 성질을 가지며 어떤 Language가 Enumerable 한 지 알아보았습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.