halting problem 잡지식

컴퓨터과학 계열 지식입니다.
혹시 이 문제가 뭐였는지 고민하는 분에게 검색되어 도움이 되기를 기대하면서 적습니다.


어떤 프로그램 P에 어떤 입력 I를 적용했을 때 이 프로그램이 끝날지, 끝나지 않을지를 검증하는 프로그램은 존재하지 않는다.

증명:

이런 프로그램이 있다고 하고 그것을 H라 하자. 이 H는 프로그램 P와 입력 I를 받아, P(I)가 끝나면 halt를 출력하고 끝나지 않으면 loop를 출력하는 프로그램이다.

H(P,I) =
만약 P(I)가 끝난다면 "halt".
아니면 "loop".
 
그러면 여기서 한 프로그램 V를 다음과 같이 정의할 수 있다.

V(P) =
H(P,P)="loop"라면 "halt".
아니면 무한루프를 돌며 프로그램이 끝나지 않는다.
 

그렇다면 V(V)는 어떤 결과를 내는가?
만약 H(V,V)="halt"라면 V(V)는 끝나지만, V의 정의에 의해서 V(V)는 무한루프를 돌아야 한다.
H(V,V)="loop"라면 V(V)는 끝나지 않으나, V의 정의에 의해서 V(V)는 끝나야 한다.

즉 H가 존재한다면 어떤 경우라도 모순이 생긴다.
그러므로 H는 존재하지 않는다.


요컨대, 어떤 프로그램과 입력값을 주었을 때 그 프로그램이 종료하는지 아닌지를 판별해 주는 알고리즘은 존재할 수 없다.

덧글

  • 마군 2009/04/01 14:20 # 삭제 답글

    해답을 잊어 검색하던 차에 잘 보고 갑니다.
    카나코님의 기대가 이 글에 남아 도움이 되네요. 감사합니다.
  • 카나코 2009/04/21 17:27 #

    기쁜 일입니다.
  • 전현철 2009/04/20 23:14 # 삭제 답글

    아... 지금 20번째보는데

    이해가안가네요..ㅠㅠ 내일 이산수학 시험인데...ㅋㅋㅋㅋㅋ

    그래도 이해해볼게요...
  • 카나코 2009/04/21 17:27 #

    시험 잘 보셨기를 바랍니다. ^^
  • 박군 2011/04/14 00:20 # 삭제 답글

    안녕하세요 잘보고갑니다
    그런데..만약 H(V,V)="halt"라면 V(V)는 끝나지만, <==이부분에서 V(V)가 아닌 H(V)가 끝나는게 아닌가요..?
    아니면 V(V)는 끝나지만, 이라는 표현을 없애던지요..
    제가 잘못생각하고있는건가요?
  • 카나코 2011/04/17 21:57 #

    안녕하세요. 말씀하신 부분에서는 V(V)가 끝나는 것이 맞습니다. 그것이 바로 H(V,V)의 정의이기 때문입니다.
  • ㅇㅅㅇ 2018/09/04 21:56 # 삭제 답글

    감사합니다 ㅜㅜ 수업때 이해안갔던 부분이 교수님의 오타라는걸 이걸 보고 깨달았어요!
댓글 입력 영역


purearea's twitter