[계산이론] #09. Non-Enumerability

Enumerable한 언어의 집합은 Countable인가?

지난 글에서 Enumerable한 언어에 대해 알아보았습니다. Binary Language (0과 1로만 이루어진 언어) 중 Enumerable한 모든 언어의 집합 $ \varepsilon $을 정의하겠습니다. 그러면 이 집합 $ \varepsilon $은 Countable입니다. (Countable이 무엇인지에 대해서는 이 글을 참고하세요.)

어떤 언어 $A$가 Enumerable이라면, $A$의 원소인 문자열이 들어오면 Accept하고 $A$의 원소가 아닌 문자열이 들어오면 Reject하거나 Terminate하지 않는 TM $T_A$가 존재한다는 성질이 있었죠. 이 성질을 사용해 위의 $ \varepsilon $이 Countable임을 증명해보도록 하겠습니다.

Enumerable Language의 집합을 $ \varepsilon$이라고 했다면, Enumerable Language $A$에 대응되는 TM $T_A$의 Binary Representation(이진 표현) $\left<T_A \right>$의 집합을 $S$라고 하겠습니다.

그러면 집합 $ \varepsilon $에서의 $S$로의 함수 $f$를 $f\left ( A \right )=\left<T_A \right>$와 같이 정의할 수 있습니다. 그리고 이 함수는 Bijection이죠. 따라서 $ \varepsilon $과 $S$의 집합의 크기는 같습니다. 따라서 $S$가 Countable임을 증명한다면 $ \varepsilon $도 Countable임을 보일 수 있습니다.

그런데 $S$가 Countable임을 보이는 것은 아주 간단합니다. $S$는 TM들의 이진 표현의 집합이기 때문에 길이가 0인 집합 - 길이가 1인 집합 - 길이가 2인 집합 - 이렇게 정렬하는 것이 가능합니다. 따라서, $S$는 Countable입니다.

 

모든 언어의 집합은 Countable인가?

이렇게 Enumerable한 Binary Language의 집합  $ \varepsilon $이 Countable임을 보였습니다. 이번에는 모든 Binary Language의 집합 $ \pounds $을 보겠습니다. 이 집합은 Countable하지 않은데요. 이에 대한 증명은 어떻게 할 수 있을까요?

무한한 이진 문자열의 집합을 $B$라고 하겠습니다. 그럼 저희가 이미 보였듯 이 집합은 Uncountable인데요, 저희는 $ \pounds $의 크기와 $B$의 크기가 같음을 보여서 $ \pounds $가 Uncountable임을 보이겠습니다. 모든 Binary Language의 집합 $ \pounds $에서 길이가 무한대인 이진 문자열의 집합 $B$로의 함수 $g$를 아래와 같이 정의하겠습니다.

모든 Binary String의 집합, $ \left\{0,1 \right\}^{*}$을 저희는 길이가 짧은 순서대로 배열할 수 있습니다. $\varepsilon $, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, ... 이렇게요. 이것들을 각각 $s_1$, $s_2$, $s_3$, ... 라고 하겠습니다. 이 때, 한 언어 $A \subseteq \left\{0,1 \right\}^{*}$에 대해 $g\left ( A \right )$의 n번째 문자는 $s_n \in A$이면 1, 아니면 0이 됩니다.

예를 들어서 1, 10, 11, 101, 111, 1001, ... 이렇게 이어지는 언어 $A$가 있을 때, $g\left ( A \right )$는

이 표에 따라 0010011000001...이 됩니다. 이 함수 $g$는 Bijection이기 때문에 $ \pounds $과 $B$의 크기는 같고, 이렇게 $ \pounds $이 Uncountable임을 보일 수 있습니다.

 

Decidable과 Enumerable

지금까지 Enumerable Language의 집합은 Countable이며, 모든 Language의 집합은 Uncountable임을 보였습니다. 이를 통해 Enumerable하지 않은 Language가 존재한다는 사실을 알 수 있습니다. 반면, 모든 Language는 Countable합니다. 그 언어에 포함된 문자열을 길이가 증가하는 순서로 배열할 수 있기 때문입니다.

사실 당연한 소리일 수 있습니다. Enumerable하다는 것이 Countable함을 보여주지는 않으니깐요.

이와 비슷하게 어떤 언어가 Decidable하면, 그 언어는 Enumerable하다는 것, 그리고 그 역은 성립하지 않는다는 것을 말씀드렸었는데요. 그러나 $A$가 Enumerable일 때 $\bar{A}$도 Enumerable이면 $A$는 Decidable하다고 말할 수 있습니다. 이의 역도 성립하고요. 이에 대한 증명은 생략하도록 하겠습니다.

또한, 이 글에서 보였듯 $A_{TM}$은 Decidable하지 않지만 Enumerable입니다. 이 말은 $\bar{A_{TM}}$은 Enumerable하지 않다는 것을 의미합니다. ( $\bar{A_{TM}}$ 도 Enumerable하다면 바로 위의 성질에 의해 $ A_{TM} $도 Decidable하기 때문입니다.) 이와 같은 방식으로, $\bar{Halt}$ 역시 Enumerable하지 않다는 것을 보일 수 있습니다.

 

정리하면, 한 언어가 Enumerable하고 그 Complement도 Enumerable한 경우가 존재합니다. 그런 언어는 Decidable하고요. 그리고 Enumerable하지만 그 Complement는 Enumerable하지 않은 언어 역시 존재합니다. 그 예시로 $A_{TM}$과 $Halt$가 있었고요. 그렇다면, 어떤 언어와 그 Complement 둘 다 Enumerable하지 않은 언어는 존재할까요?

결론부터 말하자면 존재합니다. $L\left ( M_1 \right )=L\left ( M_2 \right )$인 모든 두 Turing Machine의 쌍 $M_1$, $M_2$에 대해 모든 $\left<M_1, M_2 \right>$를 포함하는 언어 $EQ_{TM}$가 그 예시입니다.

(이에 대한 증명은 나중에 적어두겠습니다.)

감사합니다.

---

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