튜링머신에 1개의 프로그램과 Input자료 1개를 넣으면서 "야 너 이게 유한한 단계 후에 답이 나올지 나에게 풀어보기 전에 미리 알려줄 수 있어?" 라는 질문을 할 때 이를 해결해줄 수 있는 특정한 단일 프로그램이 있는가가 정지 문제이다.
1936년 앨런 튜링은 이것을 해결할 수 있는 일반화된 방법은 없다라는 결론을 내렸으며[1], 이는 논리학적으로 결정불가능함(undecidable)이 증명된 최초의 문제다.
즉, 해결방법이 있다라는 가정에서 모순이 발생한다는 것을 보임으로써 증명한다.
이 함수는 a가 i 입력에 대해 정지하고 결과를 반환하면 참을, 아니면 거짓을 반환한다.
- a: 사용될 임의의 프로그램
- i: 사용될 임의의 input
function subroutine(s) {
if exit(s,s) == false
return true
else
infinite loop
}
- 참일 경우:
exit
의 정의에 의해subroutine(subroutine)
이 정상적으로 종료해야 한다. 근데exit(subroutine, subroutine)
이 참이라고 가정했으므로 subroutine의 조건문에 의해 무한루프를 한다. 즉 참일 수가 없다. - 거짓일 경우:
exit
의 정의에 의해subroutine(subroutine)
이 무한 루프를 돌아야 한다. 근데exit(subroutine, subroutine)
이 거짓이라고 가정했으므로 subroutine의 조건문에 의해 true를 리턴하고 끝난다. 즉 거짓일 수가 없다.
즉 루프이면 트루를 반환하고 루프가 아니라면 루프를 하게하니까 문제가 발생!