[계산이론] #06. Decidability와 Halting Problem
Decidable?
Alphabet $\Sigma$에 대한 Language $A$가 있다고 생각 합시다. 이때, $w\in A$인 모든 $w$는 Accept 하고, $w \notin A$인 모든 $w$는 Reject 하는 Turing Machine $M$이 존재하면 이 Language $A$를 Decidable이라고 합니다.
지난번 글에서 TM으로 해결 가능한 문제와 C++, Java 등으로 해결할 수 있는 문제는 전부 Equivalent하다고 했고, 이러한 알고리즘을 처치-튜링 문제라고 한다고 했었는데요. 그래서 어떤 Language가 Decidable이라는 것은, 이 Language를 작성하는 알고리즘은 해결 가능하다는 것을 의미합니다.
예전 글에서 비슷한 정의를 DFA에 대해서도 내렸었는데요, DFA가 Accept하는 언어를 우리는 Regular Language라고 불렀었죠. 비슷하게 TM이 Accept하는 언어를 Decidable Language라 부릅니다. 이번 글에서는 어떤 Language가 Decidable인지, 어떤 Language가 Undecidable인지 살펴볼 건데요, 그전에 몇 가지 테크닉을 알아보고 갑시다.
Encoding Strings
0과 1로만 이루어진 문자열 2개가 있고, 이 2개를 하나로 합치고 싶다고 생각합시다. 하나의 문자열로 만들어서 DFA에 넣든, TM에 넣든 하는 상황을 생각하시면 됩니다. 예를 들어, $w_1 = 00110$, $w_2 = 1010$이라고 생각할게요.
그런데 이 둘을 합치겠다고 $w=w_1 w_2 = 001101010$라고 해두면 문제가 생깁니다. 바로 나중에 어디까지가 $w_1$이고 어디부터가 $w_2$인지 알 수가 없기 때문입니다. 그래서 그냥 무작정 두 문자열을 합치지 말고, 두 문자열 사이에 Separator를 넣어주는 것입니다.
이렇게 0을 00으로, 1은 01으로, 그리고 Separator로 11을 사용하면 문제가 깔끔하게 해결됩니다.
위와 같은 방법을 사용하면 $m\times n$ 행렬도 0과 1로만 이루어진 문자열로 표현이 가능합니다.
$$ m=2,\; n=3,\; M=\begin{pmatrix}
2 & 1 & 3 \\
4 & 6 & 5 \\
\end{pmatrix}$$
이 행렬을 문자열로 표현하면 아래와 같습니다.
먼저 $m$, $n$의 크기가 2와 3이므로 이를 이진수로 바꿉니다. 그럼 $m$은 10, $n$은 11이 되고, 이를 다시 Encoding 하여 0100, 0101으로 바꿔줍니다. 그 뒤로부터는 행렬의 각 원소를 역시 이진수로 바꾸어 쭉 나열해 준 것입니다.
Halting Problem
위와 같은 방식을 이용하면 DFA와 TM 역시 Binary String으로 표현 가능합니다. Transition Function이 행렬 형태로 표현 가능하기 때문이죠. 어떤 Machine을 Binary String으로 표현한 문자열 $C$가 있을 때 이 Machine에 문자열 $w$를 넣는 것을 $\left<C,w \right>$라고 표현하겠습니다. 이 표현을 이용해서 아래와 같은 Language를 정의할 수 있는데요.
$$A_{DFA}=\left\{\left<M,w \right>:M\ is \ DFA\ that\ accepts\ w \right\}$$
이때, 이 Language $A_{DFA}$는 Decidable입니다.
위 말이 무슨 뜻인지를 찬찬히 생각해 보겠습니다. $A_{DFA}$가 Decidable이라는 것은 이 Language에 속하는 임의의 문자열 $u=\left<M, w\right>$만을 모두 Accept 하는 어떤 알고리즘이 존재하고, 이 알고리즘을 나타낼 수 있는 TM이 존재한다는 뜻입니다. 이 알고리즘은 $M$이 $w$를 Accept 하면 Accept, $M$이 $w$를 Reject 하면 Reject 하는 알고리즘을 의미하겠죠.
즉, 쉽게 말해서 $M$이 $w$를 Accept 하는지, Reject 하는지 판단하는 알고리즘, TM이 존재하냐는 것입니다. 당연히 존재합니다. $u=\left<M, w\right>$를 입력받아서 $M$의 시뮬레이션을 진행하는 TM을 만들면 그 자체로 증명이 끝난 것입니다.
같은 방법으로 $A_{NFA}$ 역시 Decidable 한 Language입니다.
그러면 $A_{TM}$은 어떨까요? 아까와는 다르게, 이 Language는 Undecidable 합니다. $A_{TM}$은 그 정의에 따라 임의의 TM 하나와 임의의 문자열 하나가 주어졌을 때, 이 TM이 이 문자열을 Accpet 하는지, Reject 하는지 판단하는 역할을 수행합니다. 이 Language가 Undecidable이라는 것은 이를 판단하는 알고리즘은 존재하지 않는다는 뜻이겠죠. 왜 그럴까요? $A_{TM}$이 Decidable이라고 가정한 뒤에, 모순임을 보여서 증명해 보도록 하겠습니다.
Decidable Language인 $A_{TM}=\left<M, w\right>$가 있다고 생각합시다. $A_{TM}$은 Decidable Language이므로, 이 Language의 원소만을 Accept 하는 TM이 존재합니다. 이 TM을 $H$라고 하겠습니다. $H$는 $\left<M, w\right>$를 입력받아 만약 $\left<M, w\right> \in A_{TM}$일 경우 Accpet State, 그 외의 경우 Reject State가 됩니다. 쉽게 말해, Machine 하나와 문자열 하나를 입력받아 이 Machine이 문자열을 Accept하는지, Reject하는지를 출력합니다.
이때, 새로운 TM $D$를 정의하겠습니다. $D$는 $\left<M\right>$을 입력받았을 때, $H$에 $\left<M, \left<M\right> \right>$를 집어넣습니다. 그리고 그 결과가 Accpet이면 Reject State, 그 결과가 Reject이면 Accept State가 됩니다. (오타 아닙니다. $H$의 결과와 반대의 결과를 출력한다고 생각하시면 됩니다.)
살짝 헷갈리실 텐데, 아래를 읽으면서 이게 뭐였지? 싶으시면 다시 위쪽에 올라와서 정의를 확인하시고, 이런 식으로 읽으시면 이해가 될 겁니다.
자. 이제 $D$에 $\left<D\right>$를 한번 넣어보겠습니다. 그러면 $D$는 $D$의 정의에 따라 $H$에 $\left<D, \left<D\right> \right>$를 집어넣고 그 결과에 따라 행동하겠죠? (그 결과가 Accpet이면 Reject, Reject이면 Accept)
만약 $D$가 $\left<D\right>$를 Accept한다고 가정합시다. 이 말은 $H$가 $\left<D, \left<D\right> \right>$를 Reject 했다는 것을 의미합니다. 그런데 이는 모순입니다. 왜냐하면, $H$는 어떤 Machine과 어떤 문자열을 입력받아 이 Machine이 문자열을 Accept 하는지, Reject 하는지 판단하는 TM이잖아요? 그런데 $D$가 $\left<D\right>$를 Accept한다고 했으므로 $H$는 $\left<D, \left<D\right> \right>$를 Accpet 해야 합니다. 그러므로 모순이 발생합니다.
반대로, $D$가 $\left<D\right>$를 Reject 한다고 가정해도 같은 모순이 발생합니다. 따라서, 이러한 $H$는 존재할 수 없습니다.
마찬가지로, 아래와 같은 Language를 한번 정의해 보겠습니다.
$$Halt=\left\{\left<P,w \right>:P\ is\ C + + \ programm\ that\ terminates\ w \right\}$$
여기서 Terminate라는 말은, 이 프로그램이 문자열 $w$를 계산한 결과에 초점을 맞추는 것이 아니라 $P$가 $w$를 계산할 수 있는지 없는지에 초점을 맞춥니다. 2개의 수를 더하는 프로그램에 3개의 수를 넣는다던가, 문자열을 넣는다던가 하는 상황 말이죠. 2개의 수를 더하는 프로그램에 3과 4를 넣으면 이 프로그램은 Terminate됩니다. 하지만, 이 프로그램에 abadeid를 넣으면 이 프로그램은 Terminate되지 않습니다.
$Halt$ 역시 Undecidable 합니다. 이 말을 다르게 말하면, 어떤 프로그램에 어떤 값을 집어넣었을 때 그 프로그램이 이 값을 받아들일 수 있는지 없는지를 판단할 수 있는 알고리즘이 존재할 수 없다는 것입니다.
이 역시 $Halt$가 Decidable하다고 가정하고, 모순이 발생함을 보여서 증명해보도록 하겠습니다. $Halt$가 Decidable이면, 아래와 같이 작동하는 C++ 프로그램 $H$가 존재합니다.
$\left<P, w\right>$를 입력받아 $\left<P, w\right> \in Halt$이면 True를 출력, $\left<P, w\right> \notin Halt$이면 False를 출력
$\left<P, w\right>\in Halt$는 곧 프로그램 $P$가 $w$를 계산할 수 있음을 의미하므로, $P$에 $w$를 입력했을 때 Terminate되면 $H$에 $\left<P, w\right>$를 넣었을 때 True, 아니면 False라고 생각할 수 있습니다.
편의상, 프로그램 $P$에 $w$를 넣었을 때 나오는 값을 $P\left(w\right)$라고 합시다.
이 때 $\left< P\right>$를 입력받아 아래와 같이 작동하는 알고리즘 $Q$를 생각합시다.
while $H\left ( P, \left<P \right> \right )$ = True: wait 1 second
이 알고리즘은 무슨 기능을 할까요? $H\left ( P, \left<P \right> \right )$는 $P$가 $\left<P\right>$를 입력받았을 때 Terminate되면 True, 되지 않으면 False의 값을 가집니다. 따라서, while문에 True가 들어가게 되면 위 프로그램은 무한 루프에 빠져 Terminate되지 않고, while문에 False가 들어가면 위 프로그램은 Terminate됩니다. 즉, $Q\left(P\right)$는 아래와 같이 작동합니다.
"$P$가 $\left<P\right>$를 입력받았을 때 Ternimate되면 $Q$는 $\left<P\right>$를 입력받았을 때 무한 루프에 빠지게 되고, Ternimate되지 않으면 $Q$는 Terminate됩니다."
이 때, $Q$에 $\left< Q\right>$를 집어넣어보겠습니다. 그러면 위쪽에 있는 문장에서 $P$를 그대로 $Q$로 바꿔주기만 하면 됩니다.
"$Q$가 $\left<Q\right>$를 입력받았을 때 Terminate되면 $Q$는 $\left<Q\right>$를 입력받았을 때 무한 루프에 빠지게 되고, Ternimate되지 않으면 $Q$는 Terminate됩니다."
말이 안되죠? 모순이 발생하기 때문에 $Halt$는 Undecidable입니다.
이 문제를 Halting Problem이라고 부릅니다. 궁극적으로는 C++, Java 등의 프로그램이 세상의 모든 문제를 해결할 수 없다는 것을 의미합니다.
유튜브에서 우연히 발견한 영상인데요, 한글 자막도 있고 위 과정을 일반인 수준에서도 이해 가능하도록 쉽게 설명하는 애니메이션이니 심심할 때 한번 보시면 도움이 될 듯합니다.
감사합니다.
이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.