정지 문제: 모든 프로그램의 종료를 판정할 수 없는 이유
정지 문제는 임의 프로그램 P와 입력 x를 받아 P가 x에서 언젠가 멈추는지 판단하는 문제다. 모든 경우에 멈추면서 정확히 예·아니오를 반환하는 일반 알고리즘은 존재하지 않는다. 메모리나 CPU가 부족해서 생기는 한계보다 더 근본적인 계산 불가능성이다.
정지 문제의 불가능성은 모든 프로그램과 입력을 정확하게 판정하는 일반 절차에 대한 결과다.
만능 판정기를 가정하면 모순이 생긴다
H(P,x)가 항상 종료하며 정지 여부를 정확하게 알려 준다고 가정하자. 프로그램의 코드를 입력 데이터로 다룰 수 있으므로 다음 D를 만들 수 있다. H가 자기 입력에서 멈춘다고 예측하면 D는 영원히 반복하고, 멈추지 않는다고 예측하면 즉시 멈춘다.
D(program_description):
if H(program_description, program_description) == HALTS:
loop forever
else:
halt immediately
이제 D의 설명을 D 자신에게 넣는다. H가 D(D)가 멈춘다고 답하면 정의상 D(D)는 반복한다. H가 멈추지 않는다고 답하면 정의상 D(D)는 멈춘다. 두 경우 모두 정확하다는 가정과 충돌하므로 그런 H는 존재할 수 없다.
자기 참조는 유한한 입력으로 표현된다
프로그램 설명은 유한한 문자열이나 숫자로 부호화할 수 있다. D가 물리적으로 자기 몸을 넣는다는 뜻이 아니라 자기 코드의 표현을 데이터로 전달한다는 뜻이다. 이 점을 이해하면 말장난처럼 보이는 논증이 계산 모델의 정식 구성으로 읽힌다.
정지하는 경우만 확인하는 인식기는 가능하다. P(x)를 한 단계씩 모사하다 멈추면 예라고 답한다. 그러나 계속 실행 중인 상태에서 언젠가 멈출지 영원히 실행할지는 일반적으로 확정할 수 없다. 충분히 오래 기다리는 방식은 아니오를 항상 판정하지 못한다.
Simulation for a halting input:
step, step, step, halt -> answer YES
Simulation for a nonhalting input:
step, step, step, ... -> no general finite cutoff proves NO
백만 단계 안에 멈추는지처럼 유한한 실행 한계를 정하면 모사해 결정할 수 있다. 하지만 그 한계를 넘겨 멈추는 프로그램도 있으므로 원래의 무제한 정지 문제와 다른 문제다. 특정 프로그램의 종료를 증명하는 일도 가능하며 일반 판정기 불가능성과 모순되지 않는다.
유한 상태 시스템의 무한 실행은 상태 반복을 통해 분석할 수 있다. 반면 무제한 정수나 테이프를 갖는 일반 프로그램은 유한한 상태 수 가정이 성립하지 않는다. 제한 모델의 결과를 일반 언어로 옮길 때 이 차이를 확인해야 한다.
정적 분석 도구는 일부 프로그램을 정확히 분석하거나 종료를 보장하기 위해 보수적 결과와 알 수 없음을 허용한다. 일반적인 모든 입력에서 완벽하게 종료 여부를 판정하겠다는 목표가 불가능한 것이다. 실무에서 타임아웃과 제한 실행을 쓰는 이유를 이해하면서도, 그것을 종료의 수학적 증명으로 혼동하지 않는 것이 중요하다.