정지 문제: 모든 프로그램을 만들 수 있을까?

컴퓨터에게 일을 시키기 위해 컴퓨터가 해야 할 일을 매우 논리적으로 정리한 것을 프로그램이라고 한다.

컴퓨터는 프로그램을 읽고, 프로그램대로 작업을 실행한 후 프로그램에 따라 결과를 보여준다.

 

컴퓨터 덕에 우리는 이전에 상상도 못 할 정도의 일을 순식간에 처리할 수 있게 되었다. 하지만 우리는 컴퓨터로 모든 문제를 풀 수 있는가? 우리는 무엇이든 원하는 모든 것을 프로그램으로 작성하여 컴퓨터에게 시킬 수 있는가?

 

이번 글에서 컴퓨터가 풀 수 없는 문제. 정지 문제에 대해 다루고자 한다.

---

정지 문제

주어진 프로그램이 해결하고자 하는 문제를 해결할 수 있는지 판별하는 프로그램을 만들 수 있는가?

 

프로그램은 하나의 함수로 생각할 수 있다. 예를 들어 하나의 정수를 입력으로 받아 제곱을 하는 프로그램은 다음 함수와 같다.

$f(x)=x^2$

그리고 이 프로그램은 항상 입력의 제곱을 계산할 수 있다. 즉, 문제를 해결할 수 있다.

 

다른 프로그램을 생각해보자. 정수 2개를 입력받아 나눈 몫을 계산하는 프로그램은 다음과 같다.

$f(a,\:b)=\frac{a}{b}$

여기에 $b\leftarrow 0$을 넣어보자. 어떤 값이던 0으로 나눌 순 없다. 즉 프로그램은 입력에 따라 문제를 해결하지 못할 수도 있다,

 

우리가 만들고자 하는 프로그램은 다음 함수이다.

$h(P,\;i)$

P는 프로그램이고, i는 P가 가질 수 있는 입력 중 하나이다.

예를 들어 프로그램 $P$를 다음과 같이 정의하고

$P(x)=\frac{1}{x}$

$h(P,\;5)$을 실행하면 결과는 true, 프로그램 P가 문제를 잘 해결한다는 뜻이다.

$h(P,\;0)$을 실행하면 결과는 false, 프로그램 P가 문제를 해결하지 못한다는 뜻이다.

---

$h(P,\;i)$는 존재할까?

$h(P,\;i)$가 문제를 일으키는 프로그램을 만들어보자.

function s(a):
    if h(a, a) == false:
        return true
    else:
        infinite loop

a 하나를 입력으로 가지는 함수 s는 만약 프로그램 a가 프로그램 a를 입력으로 받을 때 a가 문제를 해결하지 못한다면 true를, 문제를 해결한다면 무한루프에 빠져들어 유한한 시간 이내에 답을 내지 못한다(=문제를 해결하지 못한다).

 

이때 함수 s는 결과를 뒤집는다. 즉, a(a)가 문제를 해결하지 못한다면 s의 결과는 true, a(a)가 문제를 해결한다면 s는 문제를 해결하지 못한다.

 

이제 다음 질문을 던져보자.

$h(s,\;s)$의 결과는 무엇인가?

• $h(s,\;s)=\mathrm{true}$ 인 경우
  프로그램 h의 결과가 참이니 s(s)는 문제를 해결해야 한다.
  하지만 막상 s(s)를 실행해보면 h(s, s)는 참이므로 s(s)는 무한루프에 빠져 문제를 해결하지 못한다.
  즉, 모순이 발생, $h(s,\;s)=\mathrm{true}$ 일 수 없다.
• $h(s,\;s)=\mathrm{false}$ 인 경우
  프로그램 h의 결과가 거짓이니 s(s)는 문제를 해결하지 못해야 한다,
  하지만 막상 s(s)를 실행해보면 h(s, s)는 거짓이므로 s(s)는 참을 결과로 내놓으며 문제를 해결했다.
  즉, 모순이 발생, $h(s,\;s)=\mathrm{true}$ 일 수 없다.

결국 프로그램 h는 참도, 거짓도 될 수 없다. 하지만 이는 모순이다. 프로그램 h는 항상 입력된 프로그램이 문제를 잘 해결하는지 판별해야 하기 때문이다. 이 모순은 앞선 대전제, "프로그램 h가 존재한다"를 붕괴시키어 결국 다음 결론을 낸다.

우리가 원하는 프로그램 $h$는 만들 수 없다.

---

정말 $h$는 존재하지 않을까?

개발 도구(IDE) 중에는 잠재적으로 프로그램이 문제를 해결하지 못하게 하는 실수를 지적해주는 기능이 있다.

다음 코드는 실제로 IDE가 지적해준 코드이다.

void repeat(a) {
	repeat(a+1); // 경고: repeat 함수가 무한히 실행됩니다.
}

int match(int input) {
	return switch(input) { // 경고: 모든 경우에서 함수가 결과를 반환하지는 않습니다.
    	case 1 -> 0;
        case 2 -> 5;
        case 3 -> 2;
        case 7 -> 6;
    }
}

그럼 앞서 프로그램 h가 존재하지 않는다고 증명했는데 사실은 있는 걸까? 위 경우는 어떻게 문제를 예견한 것일까?

 

이는 프로그램 h와 디버거(위의 지적을 해주는 프로그램)가 가질 수 있는 입력에는 차이가 있기 때문이다.

프로그램 h는 모든 프로그램을 입력으로 가진다. 이 프로그램은 어떤 언어로도 쓰여있을 수 있고, 어떤 프로그램도 될 수 있다. 또한 어떤 경우에도 프로그램이 문제를 해결할 수 있는지 정확히 판단해야 한다.

하지만 디버거는 C언어용 디버거, Java용 디버거, C#용 디버거 등 언어에 따라 따로 만들어져 있고, 이들은 100% 정확한 결과를 보장하지 않는다. 문제를 잘 해결하지 못하더라고 지적을 못해줄 수도 있고, 반대로 정상적인 프로그램에 문제가 있다고 할 수도 있다.

즉, 프로그램에 문제가 있는지 어느 정도만 예측하는 디버거는 프로그램 h에는 한참 못 미치는 프로그램이며, 앞선 증명의 반례가 되지 못한다.

만약 프로그램 h가 실제로 존재한다면 참 좋겠지만, 아쉽게도 그런 프로그램은 존재하지 않는다.