[암호학] 14. Classes 2

Dove-Tailing Technique

Classes E 는 Enumerable 한 Problem들의 집합이라고 정의했다.

왜 그런지 알아보자.

 

Classes E는 문제를 해결할 때 String 단위가 아니라 String안에 있는 Symbol단위로 진행한다.

예를들어 $S_1 = a_{11}a_{12}a_{13}..., ..., S_i = a_{i1}a_{i2}a_{i3}$이 있으면

$a_{11} \rightarrow a_{12} \rightarrow a_{21} \rightarrow a_{13} \rightarrow a_{22} \rightarrow a_{31} \rightarrow \dots$이런식으로 진행하며 해결한다.

이런 방법을 Dove-Tailing Technique이라고 하고 이 때문에 Enumerable하다.

 

D, E, co-E

지난 시간 이런 그림이 있었다.

그냥 그려서 이런 모양이었지만 $D = E \cap co$-$E$가 성립한다.

즉 실제로는 아래와 같다.

이를 증명해보자.

 

proof)

집합 $A, B$가 같다는 것을 증명하는 방법은 $A \subseteq B $이고 $B \subseteq A$여야 한다.

 

Step 1) $D \subseteq E \cap co$-$E$

이건 지난번에 이미 했다.

D에서 Yes -> Halt, No -> $\infty$ 로 치환하면 $D \subseteq E$

Yes -> $\infty$, No -> Halt 로 치환하면 $D \subseteq co$-$E$

 

Step 2) $E \cap co$-$E \subseteq D$

어떤 Problem $L$에 대해 $M_1$은 Halt $x \in L$, $\infty$ $x \notin L$, $M_2$는 $\infty$ $x \in L$, Halt $x \notin L $이라고 하자.

그럼 $M_1$은 $E$에 속하고 $M_2$는 $co$-$E$에 속한다.

이제 $L$을 해결하기 위해 두 머신을 돌렸을 때 $M_1$이 Halt하면 Yes, $M_2$가 Halt하면 No라고 한다면 이는 $D$가 된다.

 

따라서 $D = E \cap co$-$E$가 성립한다.$\Box$

 

그럼 이제 $E \cap D^c$가 존재하는지 궁금할 수 있다.

만약에 존재한다면 $D \neq E$이고 그렇지 않다면 $D = E$가 된다.

그리고 $|E| = |co$-$E|$이므로(대칭) 존재하지 않는다면 $D = E = co$-$E$까지 성립한다.

 

Halting Problem

앞으로 여기에서 Halting Problem을 $H$라고 하자.

$H \in D$인지 확인하고싶다.

 

$H$를 해결하는 머신 $M$에 대해 $D_1(M,x)$가 존재해서 $M(x)$가 halt하면 Yes, 그렇지 않으면 No라고 한다.

그럼 $D_1$은 "모든 입력"에서 halt해야 한다. 그렇지 않으면 $D$에 존재하지 않는다.

$D_2(M, x)$는 $M(x)$가 halt하면 $\infty$ 그렇지 않으면 halt라고 정의하자.

그리고 $D_2(M, M) = S(M)$이라고 하자. $x$자리는 인풋인데 인풋으로 머신을 넣은 것이다. (모든 입력에 머신도 포함된다.)

$S$도 머신이기 때문에 $S(S)$도 가능하다.

$S(S) = D_2(S, S)$이고 정의에 따라 $S(S)$가 halt하면 $\infty$ 그렇지 않으면 halt이다.

하지만 이렇게 되면 $S(S)$는 halt하면서 $\infty$인 상태가 동시에 존재하게 되므로 모순이다.

 

이는 가정이 잘못된 것이므로 $H \notin D$가 된다. $\Box$

 

즉 $E \cap D^c$인 Problem $H$가 존재하고 $E \neq D$이다.

Halting Problem은 Undecidable하다.