토요일에 시험보기 때문에… 오토마타를 열심히 보고 있습니다.
(라고 말하기엔 너무 놀고 있지만서도.)

최근에야 알게된 몇가지 사실들.

(1) If L is recursive, then L is decidable.
(2) If L is NP, then L is decidable.

음.. 그리고 (2)로 인해 당연히 P는 decidable.

근데 이것에 대한 해설이 없어서…
사실 Prof. Park 이 주신 책이 있긴한데 더럽게 어려워서.. ㅠㅠ
(지은이가 Greibach랍니다. ㅠㅠ 기억을 되살려드리자면 Context Free Grammar의
pumping lemma를 위한 normal form이 Greibach Normal Form이었죠.)

다시 remind를 위해 부연하면, decidable은 계산의 결과가 yes/no라고 할때
그 문제의 알고리즘이 존재하는가에 대한 이야기입니다.

다시.. 이제 위 두가지 valid 한 명제에 대한 저의 해설을 쓰자면,
(1)의 경우, 어떤 문제가 decidable이면 계산의 결과인 yes/no를
말할 수 있다. 마찬가지로 이를 L에 속한다와 그렇지 않다로 치환할 수 있다.
따라서 recursive<=>decidable이다.

(2)의 경우, NP라면 multitape turing machine으로 nondeterministic하게
polynomial time안에 문제에 답할 수 있다. 따라서, 문제의 yes/no를
L에 속한다와 속하지 않는다(즉, 멤버쉽)로 바꾸면 L에 대한 멤버쉽을
polynomial time에 답할 수 있다. 즉 recursive이다. 이렇게 되는 것
같습니다. 왜냐면 decidable하다고 할때는 알고리즘이 존재하지 않는다는
것인데, 알고리즘이 존재하지 않는다고 말할때는 그것이 원래 풀 수 없는
문제이다(halting problem같이) 또는 L에 속하지 않는 w에 대하여 TM이
never halts할 수 있다가 가능성이겠죠. 근데 NP라고 하면 time bound를
줄 수 있다는 말이므로 never halts에 대한 가능성을 배제할 수 있고,
따라서 문제를 polynomial하게 푼다고 했으므로 L에 속한다만 답하는 TM이라고
할지라도 우리는 polynomial 시간안에 L에 속한다고 답이 나오지않으면
자동으로 L에 속하지 않음을 알 수 있겠죠. 따라서, NP이면 멤버십 알고리즘이
존재할 수 밖에 없음.

제 해설이 맞을까요??? 흠…

셤때문에 오토마타 뒤쪽의 내용을 정말 자세히 보고 있는데, 덕분에 오토마타에
대한 시야가 많이 넓어졌네요.. 학부때는 이게 왜 그렇게 어려웠던지.. 물론
지금도 도무지 모르는 것 투성이지만.

어쨌든 저 위의 2가지 사실을 알면 상당히 많은 gre subject 문제의 난관을
헤쳐나갈 수 있는 것 같네요…