[자료구조] The Halting Problem (정지 문제)

해당 본문은 학교수업시간에 배운 강의내용을 기반으로 정리하는 요약글 입니다. 정확하지 않은 점이 있으면 지적해주시면 감사하겠습니다.

 

1. Halting Problem이란?

어떤 프로그램이 어떠한 입력값을 받았을 때 종료되는지 아닌지를 돌려보기 "전에" 알 수 있는가?

 

당연히 프로그램을 돌려봐서 끝난다면 끝난다는 것 을 알수 있지만, 우리는 프로그램을 돌리기 전에 먼저 알고싶다!

코드를 작성하다보면 컴파일에러도 잡아주고, 문법에러도 잡아준다, 어찌 저찌 잘 해보면 실행전에 종료되는지의 유무를 알수 있지 않을까?

 

1 - 1) 문제의 목적

세상엔 컴퓨터로 풀기 쉬운 문제가 있고, 풀기 어려운 문제가 있다.

그런데 세상엔 컴퓨터로 풀 수 없는 문제도 있다.

정지 문제는 컴퓨터로 풀 수 없는 문제들 중 하나이다.

 

"해결 불가능한(unsolvable)" 문제

 

해결 불가능한 문제가 존재한다는 역사상 첫 번째 증명은, 앨런 튜링의 "정지 문제" 이다.

 

2. The Proof (by Alan Turing!)

2 - 1) 가정

우리는 귀류법을 통해 가정이 틀렸음을 증명할 것 이다.

1. D를 만드는 것이 가능하다 가정했고
2. D를 통해 잘못된 결과를 반환하는 S를 만들었다.
3. 전제에 모순되므로, D를 만드는것은 불가능하다.

 

2 - 1 - 1) 프로그램 D

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

• 프로그램 D는 Yes/No만을 대답하는 프로그램
• 프로그램 D는 항상 종료함
• M은 검사할 프로그램의 소스 코드
• X는 M에 입력할 input이다

 

즉, 프로그램 D의 입력은 (어떤 프로그램과 M, 그 프로그램에 주어질 입력 X)이고, 출력은 종료 여부이다

• D(M, X)를 실행하면 Yes/No 중 하나를 출력하고 종료한다.

▶ M(X) 코드

def M(X):
    while X > 0:
        print("running...")
    return 1

위 코드를 통해 M(7)은 계속 "running..."을 출력할 것 이고 => D(M, 7)은 NO를 출력하고 종료한다.

위 코드를 통해 M(-1)은 1을 반환하고 종료되며 => D(M, 1)은 YES를 출력하고 종료한다.

 

누가 저런 프로그램 D를 만들었다고 가정을 해보자!

 

이렇게 D가 있다 가정하면 다음 D'은 만들기 매우 쉽다.

 

2 - 1 - 2) 프로그램 D'

프로그램 존재하는 D가 있다면, 다음 새로운 D'는 쉽게 정의할수가 있다.

• D′: M(X)가 멈추는 경우 D′(M, X)는 멈추지 않고, M(X)가 멈추지 않는 경우 D′(M, X)는 멈춘다
  • 즉, D(M, X)의 출력이 No이면 M은 멈추고, 출력이 Yes이면 M은 멈추지 않고 무한루프를 돌게된다.

 

▶ D'(M, X) 코드

def D'(M, X):
    if D(M, X) == "YES":
    	while true:
            continue
    elif D(M, X) == "NO":
        return

위 코드를 통해 M(7)은 계속 "running..."을 출력할 것 이고 => D'(M, 7)은 멈춘다.

위 코드를 통해 M(-1)은 1을 반환하고 종료되며 => D'(M, 1)은 멈추지 않는다.

 

D'은 그냥 D를 이용하는 몇줄 안되는 코드 이다.

 

2 - 1 - 3) 프로그램 S

• S: M(M)이 멈추는 경우 S(M)은 멈추지 않고,
      M(M)이 멈추지 않는 경우 S(M)은 멈춘다
  • S가 M을 입력으로 받으면, D′(M, M)을 돌리기만 하면 됨!
  • M은 프로그램이지만 문자열일 뿐이므로 D′의 입력으로 줄 수 있고 M 의 입력으로도 줄 수 있음 (그냥 입력으로 바이트를 전달한다고 생각하자)

즉, S는 돌려볼 프로그램 M을 입력으로 받지만, M이 돌릴 입력 X는 받지 않는다.

M만 입력으로 받는다. 즉 프로그램 M은 입력으로 자신의 소스코드 M을 받는 것 이다!

 

▶ S(M) 코드

def S(M):
    D'(M, M)

 

2 - 1 - 4) S(S)를 돌리면???

S: S(S)가 멈추는 경우 S(S)는 멈추지 않고, S(S)가 멈추지 않는 경우 S(S)는 멈춘다

 

??????????????? 앵? S(S)가 멈추는 경우 S(S)가 멈추지 않는다고 ?????????????????

 

말이 안되는 상황이 발생한 것 이다.

 

이는 가정이 틀렸기 때문에 발생한 것 이다, 

1) D를 만드는 것이 가능하다 가정했고

2) D를 통해 잘못된 결과를 반환하는 S를 만들었다.

3) 전제에 모순되므로, D를 만드는것은 불가능하다.

 

3) 참고

https://johngrib.github.io/wiki/halting-problem/

정지 문제