decision problem
컴퓨터 알고리즘에서 decision problem(결정 문제, 판정 문제)란 특정 입력에 대해 예-아니로 답이 있는 문제를 의미한다.
이는 알고리즘 이론과 복잡도 이론에서 중요한 개념 중 하나이다.
Halting Problem
halting problem(정지 문제)는 decision problem의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제가 해결 가능한지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다.
문제 정의
프로그램 M과 입력 X가 있을 때, M에 입력 X를 시키면 종료할 것인가?
- M(X): 프로그램 M에 입력 X를 주고 실행시킨 상태
- 사람이 문제를 푼다고 생각하고, M과 X가 모두 문자열이라 가정한다.
- 모든 경우에 해결이 돼야한다.
- M(X)는 종료한다 / 혹은 종료하지 않는다
- M(X)의 출력을 Yes이다, 혹은 No이다
프로그램이 종료된다는 것은 어떤 것이고, 종료하지 않는 다는 것은 어떠한 상태를 의미하는가?
우리는 for(;;){ } 과 같은 코드가 무한루프에 빠진 다는 사실을 알고 있다.
그렇다면 목표 코드가 5분동안 / 1시간 동안 / 30시간동안 끝나지 않는다면 종료되지 않는다고 정의할 수 있을까?
The Proof (by Alan Turing)
귀류법 사용
- 프로그램 D가 존재한다고 가정한다.
- D(M,X)를 실행하면 Yes(종료한다) / No(종료하지 않는다) 중 하나만 출력하고 프로그램이 종료된다.
- 프로그램 D가 존재하므로 D'이 존재할 수 있다. D' 은 다음과 같이 동작한다.
- M(X)가 멈춤 > D'(M,X)는 멈추지 않는다.
- M(X)가 멈추지 않음 > D'(M,X)는 멈춘다.
- 프로그램 D와 D'이 존재하므로 S가 존재할 수 있다. S는 다음과 같이 동작한다.
- M(M)이 멈춤 > S(M)은 멈추지 않는다.
- M(M)이 멈추지 않음 > S(M)은 멈춘다.
- S가 M을 입력으로 받으면, D'(M,M)을 실행하면 된다.
- M은 프로그램이지만 문자열일 뿐이므로(그렇게 가정함) D'의 입력으로 줄 수 있고, M의 입력으로도 줄 수 있다.
- 프로그램 D, D', S가 존재하므로 다음이 성립한다.
- S: M(M)이 멈춤 > S(M)은 멈추지 않고, M(M)이 멈추지 않음 > S(M)은 멈춤
M → S를 넣으면.. - S(S)가 멈춤 > S(S)는 멈추지 않음
- S(S)가 멈추지 않음 > S(S)는 멈춤
- S: M(M)이 멈춤 > S(M)은 멈추지 않고, M(M)이 멈추지 않음 > S(M)은 멈춤
>>>>>> 모순 발생
