[알고리즘] The Halting Problem

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

The Halting Problem

---

프로그램 M과 입력 X가 있을 때,

M에 입력 X를 주고 수행을 시킨다면(M(X)) 이 프로그램은 종료하는가?

 

'Halting Problem을 푼다'는 것은

M과 X의 모든 경우에, 어떠한 프로그램이 반드시 종료하는지, 아니면 영원히 수행될지(e.g., 무한 루프)를

해당 프로그램을 돌려보기 전에 판별할 수 있다고 하는 것과 같다.

 

→ Halting Problem은 풀 수 없다.

 

 

The Proof

---

by. Alan Turing

 

가정: 프로그램 D는 존재한다

모든 프로그램 M과 M에 대한 모든 입력 X에 대해서

M(X)를 실행하면 이것이 종료할지, 아니면 영원히 수행될지를 판단할 수 있는 프로그램 D가 존재한다.

 

- M(X)가 종료한다면, 즉 D(M, X)가 종료한다면 Yes를 출력한다.

- M(X)가 영원히 수행된다면, 즉 D(M, X)가 종료하지 않는다면 No를 출력한다.

 

Halting Problem이 풀린다면 프로그램 D는 존재해야 한다.

 

프로그램 S

위의 프로그램 D를 통해서 아래 두 조건을 가지는 프로그램 S를 만들 수 있다.

 

- M(M)이 멈추는 경우(D(M, M)의 결과가 No인 경우), S(M)은 멈추지 않는다.

- M(M)이 멈추지 않는 경우(D(M, M)의 결과가 Yes인 경우), S(M)은 멈춘다.

 

이때 M(M)은 프로그램에게 자기의 소스 코드를 입력으로 주는 경우를 말한다.

이 경우에도 M은 멈추거나, 멈추지 않을 것이다.

 

S(S)

그렇다면 프로그램 S의 입력으로 자기 자신(S)을 준다면 어떻게 될까?

 

- S(S)이 멈추는 경우, S(S)는 멈추지 않는다.

- S(S)이 멈추지 않는 경우, S(S)는 멈춘다.

 

→ 모순이 발생한다.

 

따라서 프로그램 D는 존재하지 않는다.

= 모든 경우에 어떤 프로그램이 종료하는지를 알 수 있는 방법은 없다.

 

 

정리

---

1. M(X) - halts
        - loop

2. D(M, X) - yes
           - no
   이러한 program이 존재한다고 가정하자.

3. S(M) - loop
        - halts
   M(M), 즉 D(M, M)을 통해서 만들어낼 수 있는 program이다.

4. S(S)
   → 모순이 발생한다.