정지 문제는 주어진 프로그램이 특정 입력에 대해 유한한 시간 안에 실행을 마치는지 판정하는 문제이다. 계산 가능성 이론에서 결정 불가능한 문제의 대표적인 예이다.
일반 알고리즘의 한계
프로그램과 입력의 모든 조합에 대해 종료 여부를 정확히 판단하고 스스로도 반드시 종료하는 알고리즘은 존재하지 않는다. 이 한계는 컴퓨터의 속도가 부족해서 아직 풀이를 찾지 못했다는 의미와 다르다.
개별 사례의 판정
일반적인 판정 알고리즘이 없다는 사실은 모든 프로그램의 동작을 알 수 없다는 뜻이 아니다. 즉시 반환하는 프로그램은 종료함을 알 수 있고, 조건 없이 같은 동작을 반복하는 단순한 무한 반복은 종료하지 않음을 증명할 수 있다. 결정 불가능성은 모든 경우를 처리하는 하나의 보편적인 절차에 관한 성질이다.
증명의 개요
모든 프로그램의 종료 여부를 판정하는 절차가 있다고 가정한다. 그 절차가 자기 자신을 입력받은 프로그램에 대해 내린 예측과 반대로 행동하는 프로그램을 구성한다. 이 프로그램을 자기 자신에게 적용하면 종료한다고 예측할 때 종료하지 않고, 종료하지 않는다고 예측할 때 종료하는 모순이 생긴다.