| NP 완전 문제 | 여러 가지 NP 완전문제 | NP-완전성과 변환성 |

NP 완전 문제

■ 종료문제(Halting Problem)

어떤 프로그램 P가 정상적으로 수행되어서 종료하는지를 결정하는 문제

1936년 Alan Turing에 의해서 증명됨

정리 : 종료 문제는 결정 불가능하다.

증명 : 이 문제를 풀 수 있는 알고리즘이 존재한다고 가정하자. 그 알고리즘은 어떤 프로그램을 입력으로 받아서 그 프로그램이 종료하면 '예' 라는 답을 주고, 종료하지 않으면 '아니오' 라는 답을 줄 것이다. 그 알고리즘을 Halt라고 하면, 다음과 같은 말도안돼 알고리즘을 만들 수 있다.

algorithm 말도안돼
      if Halt(말도안돼) == '예' then
                          while true do print '야호'

(1) 만일 말도안돼 알고리즘이 정상적으로 종료하는 알고리즘이라고 한다면, Halt(말도안돼)는
     '예' 가되고, 따라서 이 알고리즘은 절대로 종료하지 않는다. 이는 가정과 상반된다.

(2) 만일 말도안돼 알고리즘이 정상적으로 종료하지 않는 알고리즘이라고 한다면, Halt(말도안돼)      는 '아니오' 가 되고, 따라서 이 알고리즘은 종료하게 된다. 이도 마찬가지로 가정과 상반된다.

(3) 결론적으로, Halt라는 알고리즘은 존재할 수 없다.