[계산 이론] The Halting Problem

 

컴퓨터를 전공 배우고 있는 사람 입장에서, Halting Problem정도는 한번 증명해 보고 정리해 두면 좋을 것 같다 생각하여 글을 남겨봅니다!

 

1. Halting Problem 이란?

우선 정의부터 살펴보자!

There’s no algorithm that can look at a program’s source code and always correctly determine if the program will run forever or not.

 

사람의 언어로 조금 바꿔보면, 유한시간안에 프로그램을 실행해보지 않고 정지할지 말지를 결정하는 알고리즘은 존재하지 않는다는 의미이다!

 

2. Proof by contradiction

다음과 같이 "input과 output을 갖는 halt라는 프로그램(알고리즘)이 있다" 라고 가정해보자!

input 2개가 모두 <>로 감싸져 있는데, 이는 인코딩 되어있다는 의미이며, 프로그램의 인자로 전달하기 위함이다.

 

다음과 같이 내부에서 halt를 호출하는 프로그램 trouble을 생각해 보자!

function trouble(string s){ 
    if (halt(s, s) == false) return true;
    else loop forever; // while(1){}; 
}

 

모든 프로그램은 String으로 표현할 수 있으므로, 위 프로그램 trouble을 String t로 변환했다고 해보자!

 

이 String t를 프로그램 trouble의 입력으로 하는, trouble(t)의 실행결과를 생각해 보자!

즉, trouble() 메서드 자시 자신의 input으로 String으로 변환된 trouble t를 전달한 것이다, 약간 자기가 자기를 판단하게 된다고 표현하면 조금은 이해하기 편할 수도?

 

1. trouble(t)가 halt 하려면, line 2에서 halt(t, t)가 false를 반환해야 한다. 그러나 halt(t, t)가 false를 return 하려면, halt 프로그램의 설명 (2)에서처럼 프로그램 t가 t를 입력으로 받아 그 실행이 loop forever 해야 한다. 즉, trouble(t)가 loop forever해야 한다. 이는 모순이다. (멈추려면 무한이 돌아야 한다니? 모순이다!!)

2. trouble(t)가 loop forever 하려면, line 2에서 halt(t, t)가 true를 return 해야 한다. 그러나, halt(t, t)가 true를 return 하려면, halt프로그램의 설명 (1)에서처럼 프로그램 t가 t를 입력으로 받아 그 실행이 종료해야 한다. 즉, trouble(t)가 종료해야 한다. 모순이다! (무한이 돌려면 종료해야 하다니!! 엄청난 모순)

 

즉, 맨 처음 가정이 잘못된 것이다!!

 

비록 undeciable이지만, recognizable까지는 된다.