컴퓨터에게 일을 시키기 위해 컴퓨터가 해야 할 일을 매우 논리적으로 정리한 것을 프로그램이라고 한다.
컴퓨터는 프로그램을 읽고, 프로그램대로 작업을 실행한 후 프로그램에 따라 결과를 보여준다.
컴퓨터 덕에 우리는 이전에 상상도 못 할 정도의 일을 순식간에 처리할 수 있게 되었다. 하지만 우리는 컴퓨터로 모든 문제를 풀 수 있는가? 우리는 무엇이든 원하는 모든 것을 프로그램으로 작성하여 컴퓨터에게 시킬 수 있는가?
이번 글에서 컴퓨터가 풀 수 없는 문제. 정지 문제에 대해 다루고자 한다.
정지 문제
주어진 프로그램이 해결하고자 하는 문제를 해결할 수 있는지 판별하는 프로그램을 만들 수 있는가?
프로그램은 하나의 함수로 생각할 수 있다. 예를 들어 하나의 정수를 입력으로 받아 제곱을 하는 프로그램은 다음 함수와 같다.
$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 loopa 하나를 입력으로 가지는 함수 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가 실제로 존재한다면 참 좋겠지만, 아쉽게도 그런 프로그램은 존재하지 않는다.