이번 문제는 튜링의 멈춤정리(turing's halting theorem)에 대한 얘기입니다. 프로시저가 있을 때 이 프로시저가 끝없이 돌아가는지 아닌지를 확인할 수 있는 프로시저(여기서는 halts?)는 존재하지 않는다는 것을 증명하는 문제입니다. 코드와 식, 힌트 등이 전부 제공되기에 그리 어렵지 않게 문제를 풀 수 있었습니다.

   1: (define (run-forever) (run-forever))

   2:  

   3: (define (try p)

   4:   (if (halts? p p)

   5:       (run-forever)

   6:       'halted))

  위와 같은 코드에서 (try try)을 실행시켰을 때 halts? 프로시저의 정의에 어긋나는 것을 보여주면 된다고 합니다. 따라서 저는 이렇게 생각하였습니다.

  만약 위에서 설명한 일을 하는 프로시저인 halts? 프로시저가 존재한다고 가정하고, 만약 (try try)가 halt한다면 halts? 프로시저를 true를 내놓을 것입니다. 그렇게 되면 try 프로시저 안의 if문에 따라 (run-forever)가 실행되어 이것이 끝없이 실행될 것이니 (try try)가 halt하지 않습니다.

  만약 (try try)가 halt하지 않다면 halts? 프로시저는 false를 내놓을 것입니다. 그렇게 되면 try 프로시저 안의 if문에 따라 'halted 문자열을 돌려주고 종료(halt)할 것입니다.

  어느 쪽이든 모순된 결과가 나오기에 그 전제인 'halts? 프로시저가 존재한다.'는 가정이 틀렸다고 할 수 있습니다. 따라서 halts? 프로시저는 존재하지 않습니다.

  여기서 하나 재미있는 것은 만약 halts? 프로시저가 반대로 결과물을 내놓는다면 어떤가 하는 것입니다. 즉, 종료하면 false, 끝없이 돌면 true를 반환한다고 하면 위의 코드에서는 문제가 없습니다. 하지만 만약 다음과 같은 프로시저가 있다면 역시 같은 논리로 모순이 발생하게 될 것입니다.

   1: (define (run-forever) (run-forever))

   2:  

   3: (define (try p)

   4:   (if (halts? p p)

   5:       'halted

   6:       (run-forever)))

  따라서 어떤 값을 내놓든 halts? 프로시저는 존재하지 않습니다.

  이렇게 문제를 풀었지만, 저는 증명을 그리 완벽하고 깔끔하게 하지 못하는 터라 관련 문서를 찾아보았습니다. 하지만 아쉽게도 아직 100% 이해를 하지 못해 여기에 대한 설명을 할 수 없습니다. 참조 문서로 링크를 남기니 후에 여기에 대해 적을 때 참조할 수 있기를 바랍니다.

참조

• 해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 505
• http://en.wikipedia.org/wiki/Ill-posed
• http://www.answers.com/topic/well-posed-problem
• http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
• http://www.aistudy.com/computer/church_turing_thesis.htm
• http://www.aistudy.com/computer/halting_problem.htm
• http://en.wikipedia.org/wiki/Halting_problem#Sketch_of_proof
• http://www.aistudy.com/math/mechanism_math.htm#_bookmark_5

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.