알고리즘1 The HALTING Problem

The HALTING Problem

프로그램에 입력이 들어오면 종료할 것이냐?

멈추지 않는다면 알려주는 것이 좋지 않을까?

무한루프는 멈추지 않는 프로그램 중 하나

 

어떤 프로그램이 종료하지 않는지를 미리 알 수 있는가?

언젠가 끝난다는 것을 말할 수 있는 시점이 있을까?

반대로 절대로 안 끝난다는 것을 확신할 수 있는 시점이 있을까?

 

---

Alan Turing의 증명

-> 결론 : 이 문제는 안 풀린다.

-> 이 문제는 풀린다고 가정함. (귀류법으로 증명)

 

 

프로그램 D = 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 종료할 지 영원히 계속 수행될지 판단할 수 있다고 하자.

- 프로그램 D는 Yes/No를 대답하는 프로그램

- 프로그램 D는 항상 종료함

 

즉, 프로그램 D의 입력은 어떤 프로그램과 그 프로그램에 주어질 입력이고,

출력은 종료 여부이다.

 

D(M,X)를 실행하면 Yes/ No 중 하나를 출력하고 종료하는 프로그램 D를 만들었다고 가정

(프로그램 M이 멈추는 지 안 멈추지는 지 알려주는 프로그램이 있다. D는 항상 종료해야 함)

 

M이 멈춘다면 D의 출력값은 yes, M이 멈추지 않는다면 no

 

 

 

D' (D와 반대의 동작하므로 D가 있으면 D'을 가정할 수 있다..) :

M(X)가 멈추는 경우 D'(M,X)는 멈추지 않고,

M(X)가 멈추지 않는 경우 D'(M,X)는 멈춘다.

D의 출력이 no면 멈추고, yes면 무한루프

 

 

S : (D'에서 X를 M으로 바꾸면 됨)

M(M)이 멈추면 S(M)은 멈추지 않고

M(M)이 멈추지 않는 경우 S(M)은 멈춘다.

S가 M을 입력으로 받으면 D'(M,M)을 돌리기만 하면 됨

 

 

S(S)가 멈추면 S(S)는 멈추지 않고

S(S)가 멈추지 않으면 S(S)는 멈춘다.

 

 

 

---

 

예시

배경: 어떤 연구소 과제

목표: PHP코드 해킹 방지

방법: PHP코드를 분석해서 해킹 공격에 취약한 부분이 있는지 보자 (ex SQL인젝션)

=> 모든 경우를 다 확인할 수 없으며 안풀리는 문제임. 

 

---

결국 종료하지 않는 시점을 말할 수 없다.

trouble() 종료되려면 halt()가 false를 반환해야 한다.

하지만 이것은 halt()가 끝나지 않는다는 것을 의미한다.

halt()가 종료되어 true를 반환한다면 역시 trouble()은 종료되지 않는다.