halting problem
우리 교수님이 항상 이 halting problem에 대한 이야기를 첫 수업마다 한다.
재밌는 이야기라 정리해보자.
이발사 문제
우선 이발사 문제에 대해 알아보자.
어떤 마을에는 이발사가 한 명 있는데 이 이발사는 스스로 이발하지 않는 사람 모두 이발을 해준다.
그러면 이발사의 머리는 누가 이발을 하는가?
만약 스스로 이발한다면 이발사가 이발을 하면 안된다.
그렇다고 이발을 하지 않는다면 이발사가 이발을 해줘야 한다.
따라서 이발사가 자기 스스로 이발을 하지 않는 사람 모두를 이발한다는 가정은 잘못됐다.
정지 문제(Halting Problem)
정지 문제란 어떤 프로그램이 종료하지 않는지를 돌려보기 전에 알 수 있는가?에 대한 문제이다.
우리가 프로그램을 돌릴 때 끝난다면 끝난다는 사실을 알 수 있다.
하지만 끝나지 않는다면 이게 실행이 오래 걸리는지, 진짜 안 끝나는지를 구분할 수 없다.
그러면 어떤 프로그램을 입력으로 넣어 그 프로그램이 끝나는지 안 끝나는지 판별하는 프로그램을 만들 수 있을까?
이는 귀류법을 통해서 불가능하다고 증명할 수 있다.
귀류법
가정 : 프로그램 D는 모든 프로그램 M에 대한 모든 입력 X에 대해 M(X)의 종료 여부를 판단할 수 있다.
프로그램 D는 YES or NO 만을 대답하고, 항상 결과를 낸 후 종료한다.
D(M, X) -> YES or NO 대답 -> 종료 라는 흐름을 가지게 된다.
이 프로그램 D로 not_D 프로그램을 만들 것이다.
not_D는 M(X)를 입력으로 받아 M(X)가 멈추면 not_D는 멈추지 않고, M(X)가 멈추지 않으면 not_D는 멈춘다.
D(M, X)의 결과가 YES면 not_D는 무한 루프, NO면 멈추는 프로그램이다.
D(M, X)를 만들 수 있다면 not_D를 쉽게 만들 수 있음이 자명하다.
이제 S(M)이라는 프로그램을 만들고, 이는 not_D(M, M)의 기능을 한다.
S(M)은 M(M)이 멈추는 경우 S(M)이 멈추지 않고 M(M)이 멈추지 않으면 S(M)은 멈춘다.
프로그램도 문자열이기 때문에 입력값으로도 들어 갈 수 있다.
이제 S(S)를 실행하면 어떻게 될까?
S(S)는 not_D(S, S)의 기능을 한다.
S(S)는 S(S)가 멈추는 경우 S(S)가 멈추지 않고, S(S)가 멈추지 않으면 S(S)가 멈춘다는 결론이 나온다.
이는 모순이기 때문에 맨 처음 가정이 잘못됐다.
따라서 프로그램 D는 만들 수 없고, 프로그램의 종료 여부를 판단 할 수 없다.
이렇게 논리적으로 프로그램의 정지 여부를 확인하는 프로그램은 만들 수 없다는 결론이 나온다.