정지 문제의 정의

어떤 알고리즘이 무한 루프에 빠지는지 알아내는 알고리즘이 존재할까?

이 질문에 대한 답을 우리는 정지 문제를 통해 알 수 있다. 이를 증명해보자.

정지 문제의 증명 과정

프로그램은 함수로 생각할 수 있다.

어떤 프로그램은 어떤 입력값을 받고 입력값에 대해 어떤 과정을 거쳐 어떤 값을 출력하는 것으로 생각할 수 있다. 그리고 우리는 이것을 어떤 함수로 생각할 수 있다. 예를 들어, 어떤 수를 입력받으면 이 수의 두 배를 출력하는 프로그램이 있다고 생각하면, 이 프로그램 $P$는 $P(a)=2*a$와 같이 생각할 수 있다.
이렇게 프로그램을 함수로 표현할 수 있기 때문에 우리는 어떤 프로그램, 즉 함수가 무한 루프에 빠지는지 빠지지 않는지를 알아내는 함수가 존재하는지의 여부를 알아내면 정지 문제에 대한 답을 얻을 수 있다.

귀류법을 통한 정지문제의 증명

귀류법으로 정지 문제를 증명하기 위해 다음과 같이 가정하자.

어떤 알고리즘이 정지하는지, 무한 루프에 빠지는지 알아내는 알고리즘은 존재한다.

위 가정이 성립하므로 우리는 다음과 같은 프로그램이 존재한다고 생각할 수 있다. 임의의 프로그램과 입력 $P$, $a$에 대하여, \(\text{HALT}(P, a) = {\begin{cases} \text{true} & \text{if } P(a) \text{ halts} \\ \text{false} & \text{otherwise} \end{cases}}\)
그리고 다음과 같은 프로그램을 입력으로 받는 프로그램 $A(P)$가 있다고 가정하자.

\[A(P) = {\begin{cases} \text{run forever} & \text{if } \text{HALT}(P, P) \\ \text{halt} & \text{otherwise} \end{cases}}\]

여기서 우리는 $A(A)$가 무한루프에 빠지거나 정지하는 두 가지 가능성을 생각할 수 있다. 이 두 가지 경우를 다음과 같이 생각해보자.

  1. $A(A)$가 무한 루프에 빠진다.
    이 경우 프로그램 $A$의 정의에 따라 $\text{HALT}(A, A)$는 참이다. 그런데, $\text{HALT}(A, A)$가 참이면, $A(A)$는 정지한다.
  2. $A(A)$가 정지한다.
    이 경우 프로그램 $A$의 정의에 따라 $\text{HALT}(A, A)$는 거짓이다. 그런데, $\text{HALT}(A, A)$가 거짓이면, $A(A)$는 무한 루프에 빠진다.

여기서 $A(A)$가 정지하는 상황과 무한 루프에 빠지는 상황이 양립한다. 그런데 이는 양립할 수 없다. 여기에서 모순이 발생하므로 가정은 틀렸다.
따라서, 어떤 알고리즘이 정지하는지, 무한 루프에 빠지는지 알아낼 수 있는 알고리즘은 존재하지 않는다.
이 상황은 러셀의 역설에서 모순이 발생하는 상황과 비슷하다는 것도 알 수 있다.