정지 문제

프로그램과 입력이 주어질 때 그 프로그램이 그 입력에서 언젠가 멈추는지 판정하는 문제다. 튜링은 1936년에 이를 푸는 알고리즘이 존재할 수 없음을 증명했다. 판정 프로그램이 있다고 가정하고, 「내가 멈춘다고 판정되면 영원히 돌고 아니면 멈추는」 프로그램을 만들어 모순을 끌어내는 대각선 논법이다. 풀 수 없는 문제가 있다는 것을 처음 보인 결과로, 하한 증명의 원형이다. 정지 문제는 NP-난해이지만 NP 에 속하지 않는다.