Tuesday, February 21, 2006

Halting Problem (정지 문제)

컴퓨터 사이언스(CS)에서 알고리즘에서의 계산 복잡도 이론(Computational complexity theory)을 배울 때, 컴퓨터 언어론을 배울때 꼭 짚고 넘어가는 결정(판정)문제 중 하나입니다.
과연 "문제를 풀 수 있는지 없는지 알 수 있는 판단 할 수 있는 알고리즘이 있는가 없는가?" 다시 말하자면, "문제를 푸는 알고리즘이 있는지 없는지 알 수 있는 알고리즘이 있다는가 없는가?". 또 다시 말해, "문제를 풀어내는 프로그램을 만들 수 있는지 없는지 알 수 있는 프로그램을 만들 수 있는가 없는가?"

만약, 만들 수 있다면 컴퓨터로 못푸는 문제는 없게 됩니다. 왜냐하면 문제가 풀리는지 안 플리는지 적어도 알 수 있으니까 문제가 안 풀리면, "그 문제는 시간을 아무리 많이 줘도 풀 수 없습니다." "왜?" "컴퓨터가 그랬으니까요."하면 되는 거니까요. 컴퓨터가 모든 문제를 풀어낼 수 있는 거죠. 하지만 현실에서는 컴퓨터로 못푸는 문제가 존재합니다. 컴퓨터가 아무리 빨라져도, 시간을 많이 줘도 못푸는 문제가 존재합니다. 예를 들어, "이 세상에서 가장 큰수를 내놔봐라" 그런 문제는 풀 수 없는 겁니다. 그런 문제는 컴퓨터에 의존하지 말고 인간이 고민해서 "이 세상에서 가장 큰 수란 없다. 단, 가장 큰 수로 계속 접근하는 '무한대'란 존재할 수 있다."라고 결론을 내려야하는 겁니다. 따라서 컴퓨터에서는 판정 가능한지 않은지는 너무나도 중요한 문제 입니다.

그렇다면, 프로그램이 풀 수 있는 문제인가를 판단하는 프로그램이 존재하지 않음을 명확하게 증명 해보세요. 벌써 머리가 지끈 거리기 시작하나요? 저도 학교에서 이 문제를 첨 배울때 교수님이 그렇게 말씀하셔서 정말 풀어내야하는 문젠 줄 알고 그랬습니다. 그런데 다행스럽게도 수학적 증명을 영국의 유명한 수학자이자 현대 컴퓨터의 기본 구조를 창시해낸 "튜링"이 "Halting problem(정지 문제)"이라고 불리우는 이 문제를 이미 증명했습니다. "튜링 기계에서는 정지 문제를 결정할 수 없다."라고 했습니다.

이 글이 과연 정지 문제를 명확하게 이해할 수 있는 글인지는 자신이 없네요. 더 알고 싶으시면 아래의 레퍼런스를 참조하세요. (라고 무책임하게 말합니다. 하핳. 이 문제에 대해서 완전히 명확하게 쓸 수 있다는 자신이 생기면 다시 더 정확하게 글을 써보도록 하겠습니다.)

Reference:
1. Halting Problems (Craig S. Kaplan - University of Waterloo, Canada)
2. Wikipedia (Halting Problem , 정지 문제 )