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 , 정지 문제 )

2 Comments:

At 2:08 AM, Blogger vita6000 said...

한동훈님안녕하세요.파코즈에올려주신게시물 네이버 블로그/카페에서 우클릭 및 내용 선택하기와관련해서 여기까지찾아왔습니다. 동훈님께서 올려주신유틸 익스플로러에선아주잘되더라구요. 헌데 크롬에서는안되어서혹시도움받을수있을까코멘트남깁니다.
크롬사용중이며 구글홈페이지에서받아설치하였으니stable버전맞는거같습니다.
4.1.249.1064 (45376) 이 버전이 stable버전맞지요?혹시나해서 chromechannel-2.0.exe이걸로stable클릭선택하고업데이트버튼클릭하면 원래stable버전이라그런지 문구뜨면서안됩니다. 그럼 버전은제대로인거같은데 크롬바로가기대상T부분에 --enable-user-scripts 적용누르고확인후에 구글 크롬이 설치된 폴더의 User DATA\Default 아래에

User Scripts 라는 폴더가생긴다하였는데 전 안생깁니다. 무엇이 문제인지알수있을까요? 그리고혹시나 제컴퓨터문제라면 다른컴퓨터에서설치한다음 61326.user.js가포함된User Scripts폴더를 제컴퓨터로복사해오면 복사방지해제기능이 정상적으로 수행될수있을까요?

마지막으로 대상T 뒷부분에 --enable-user-scripts" 이거붙여넣기할때 끝부분에 " ☜이거넣어줘야하는건지요?
"C:\~ ~ ~ chrome.exe" 여기뒤에붙여넣기하는데 exe뒷부분에 " 이것을 지우고 붙여넣기해줘야하나요? 그리고 한칸띄우고써야하는지 또 scripts마지막부분에 "이거붙여줘야하는지 자세하게좀알려주시면 정말많음도움되겠습니다.
이거해결해보려고오늘하루 날새네요 ㅡ.ㅡ vita6000@naver.com 메일주시거나 여기에 댓글달아주시면감사하겠습니다.

 
At 9:03 AM, Blogger dyhan81 said...

안녕하세요. 한동윤입니다.

Google Chrome 2.0 부터는 greasemonkey (user scripts) 모듈이 제거되었기 때문에 해당 스위치가 동작하지 않습니다.

부가 프로그램으로 Chrome에서 Anti-DIsabler for Naver를 만들어보려고 하고 있으나 Chrome의 확장 프로그램 작동 방식이 Greasemonkey의 그것과 상이하여 어려움이 있습니다.

미안합니다. 일단 Firefox를 사용하시기 바랍니다.

 

Post a Comment

<< Home