힐베르트의 10번째 문제와 튜링 기계

힐베르트의 10번째 문제는 힐베르트의 23개의 문제 중 하나로, 수학적 명제의 증명에 컴퓨터의 개념이 사용된 예 중 하나이다.

배경

힐베르트의 문제

1900년 파리에서 개최된 국제 수학자 대회에서 다비트 힐베르트(David Hilbert)는 23개의 문제를 제시하였다. 이 문제들은 당시에는 전부 해결되지 않았던 것들로, 수학의 발전 방향을 제시하기 위해 엄선된 것들이었다. 그 이후로 많은 문제가 해결되었지만, 일부는 지금까지 해결되지 않았다. 현재 수학에서 유명한 난제인 리만 가설도 힐베르트의 문제 중 하나이다. 문제의 해결 여부를 떠나 이 문제들은 원래의 목적대로 수학의 발전에 지대한 영향을 끼쳤다.

이 중 10번째 문제는 특히 그 입지가 독특하다. 이 문제가 특별한 이유는, 처음 발표되었을 때 문제의 정의가 모호하였으나, 이후 새로운 개념이 도입되면서 명확해졌기 때문이다. 힐베르트가 처음에 제시했던 문제는 다음과 같다.

임의의 디오판토스 방정식이 해를 가지는지를 유한 번의 연산을 사용해 판별할 수 있는 과정을 제시하라.

여기서 디오판토스 방정식(Diophantine equation)은 임의의 개수의 미지수를 가지고 모든 계수가 정수이며 오직 정수해만을 고려하는 다항방정식이다. 즉 이 문제는 다음과 같이 풀어 쓸 수 있다.

임의의 개수의 미지수를 가지고 모든 계수가 정수인 임의의 다항방정식이 정수해를 가지는지를 유한 번의 연산을 사용해 판별할 수 있는 과정을 제시하라.

디오판토스 방정식은 고대 로마 시대에 살았던 수학자인 디오판토스(Diophantus)의 이름이 붙은 것에서 짐작할 수 있듯이 고대부터 연구되어 왔던 수학의 주요 관심사였다. 이러한 디오판토스 방정식이 해를 가지는지 판별하는 방법이 밝혀진다는 것은 매우 큰 의미가 있을 것이다.

결론부터 말하자면, 그러한 방법은 존재하지 않음이 밝혀졌다. 즉 어떤 (정수 계수) 다항식에 대해서도 정수해 존재 여부를 판별할 수 있는 일반적인 방법은 존재하지 않는다. 흥미로운 점은 힐베르트가 처음으로 제시한 문제의 목표는 과정의 존재 여부를 밝히는 것이 아닌 과정이 무엇인가를 찾는 것이었다. 당시 힐베르트는 이러한 과정이 반드시 존재할 것이라고 믿었음을 짐작할 수 있다. 1900년대 초에는 아직 괴델의 불완전성 정리나 정지 문제 등 해결이 불가능한 문제에 대한 논의가 본격적으로 이루어지기 전이었기 때문에 이러한 과정이 존재하지 않을 것이라고 예상치 못했을 수 있다.

이러한 배경에 의해 야기된 또 다른 문제점으로, 힐베르트가 제시한 처음의 문제에는 모호한 점이 있었다. “유한 번의 연산을 사용한 판별 과정”이라는 개념이 명확히 정의되지 않은 것이다. 여기서 한 번의 “연산”으로 허용되는 것이 무엇인지가 확실하지 않다. 일단 사칙연산의 경우 확실히 한 번의 연산으로 생각할 수 있을 것이다. 거듭제곱, 제곱근 역시 단일 연산으로 간주할 만하다. 그렇다면 더 복잡한 연산은 어떨까? 지수함수, 삼각함수, 무한급수, 극한, 미분, 적분 등은 한 번의 연산으로 간주할 수 있을까?

이러한 모호한 정의는 그러한 과정이 “존재하지 않음”을 증명하려고 할 때 특히 문제가 된다. 앞에서 말한 것처럼 만약 사칙연산, 거듭제곱, 제곱근과 같이 간단한 연산 몇 개를 조합하여 판별하는 방법이 밝혀졌다면 문제는 해결된 것이 된다. 예를 들어 복소수 계수를 가지는 이차방정식 $ax^2 + bx + c = 0$의 두 개의 복소수 근을 찾는 과정은 다음과 같다(근의 공식).

\[x_1 = \frac{-b - \sqrt{b^2 - 4ac}}{2a}, \quad x_2 = \frac{-b + \sqrt{b^2 - 4ac}}{2a}\]

두 근을 구하기 위해 정해진 횟수의 기본 연산을 사용했으므로, 이는 확실히 “유한 번의 연산을 사용한 과정”에 해당한다. 따라서 “복소수 계수를 가지는 이차방정식의 해를 구하는 과정이 존재하는가?”라는 질문에는 그렇다고 답할 수 있다.

그러나 이런 방법이 존재하지 않는다는 것을 밝히려면, 모든 “유한 번의 연산을 사용한 과정”을 조사하여 이들 중 디오판토스 방정식의 해의 존재를 판별하는 것이 없음을 밝혀야 한다. 그러기 위해서는 그 과정들의 집합이 무엇인지 확실히 해야 한다. 그러나 이 문제가 발표된 1900년대 초에는 아직 이에 대한 정의가 없었다.

튜링 기계와 알고리즘의 정의

1936년, 알론조 처치(Alonzo Church)와 앨런 튜링(Alan Turing)은 각각 람다 대수(λ-calculus)와 튜링 기계(Turing machine)를 정의하였다. 이 두 개념은 “연산”이라는 행위가 무엇인가를 명확히 정의하는 계산 모형이다. 두 모형은 서로 동등한 계산 능력을 갖추고 있으며, 현재까지 개발된 계산 모형 중 가장 광범위한 능력을 갖추고 있다. 이것이 튜링 기계가 이후 컴퓨터의 논리적 모형으로 채택된 이유이다. 유한 상태 오토마타(finite automata), 푸시다운 오토마타(pushdown automata) 등 다른 계산 모형들도 존재하나 이들은 (튜링 기계는 할 수 있는) 비교적 간단한 작업조차 하지 못하는 경우가 있어 한계가 명백하다. 반면 튜링 기계는 인간이 생각해 낸 모든 알고리즘을 모두 시행할 수 있었다. 따라서 “유한 번의 연산으로 이루어진 과정”, 즉 “알고리즘”이라는 개념은 곧 “튜링 기계로 할 수 있는 작업”으로 명확히 정의가 내려졌다.

그러나 어떤 문제는 튜링 기계로도 해결할 수 없다. 여기서 해결할 수 없다는 것은, 해당 문제의 답을 구하고 정지하는 튜링 기계가 존재하지 않는다는 것이다. 사실 이러한 문제 중 하나는 튜링 기계의 개념과 동시에 발표되었는데, 그것은 바로 정지 문제(halting problem)이다. 이 외에도 정지 문제와 같이 해결될 수 없는 여러 문제가 밝혀졌다.

튜링 기계를 사용한 문제 재정의

이제 힐베르트의 10번째 문제를 튜링 기계를 사용하여 다시 정의할 것이다. 문제는 다음과 같다.

임의의 개수의 미지수와 정수 계수를 가지는 주어진 다항방정식이 정수해를 가지면 accept, 그렇지 않으면 reject 하는 튜링 기계가 존재하는가?

정답은 “그렇지 않다”이다. 이러한 튜링 기계는 존재하지 않는다. 이 사실은 1970년 Yuri Matiyasevich 등에 의해 증명되었다. 여기서 힐베르트가 제시한 원래의 문제를 다시 살펴보면 흥미로운 점을 알 수 있다. 원래의 문제는 “이러한 알고리즘이 존재하는가”를 물어본 것이 아니라 “이러한 알고리즘을 찾아라”였다. 즉 힐베르트는 이러한 알고리즘이 존재할 것이라고 믿고 있었음을 짐작할 수 있다.

이에 대해 알아보기 전, 문제에서 요구하는 것을 약화해 보자.

임의의 개수의 미지수를와 정수 계수를 가지는 주어진 다항방정식이 정수해를 가지면 accept 하는 튜링 기계가 존재하는가?

원래의 문제에서 달라진 점은 튜링 기계가 해를 가지지 않을 때 reject 하지 않고 영원히 동작하는 것을 허용하는 것이다. 이러한 튜링 기계는 존재하며, 이를 증명할 것이다.

우선 튜링 기계가 다항식의 정보를 읽어오거나 다항식의 미지수에 값을 대입한 값을 계산하는 것을 할 수 있다는 사실을 받아들이자. 튜링 기계의 계산 능력을 생각하면 당연하지만, 명확성을 위해 언급하였다. 또한 다음 사실을 이해하자.

임의의 $n$에 대해, $n$개의 정수를 묶은 순서쌍은 가산 집합이다(countable set). 즉 모든 순서쌍을 $x_1, x_2, x_3, \ldots$와 같이 나열할 수 있다.

이제 다음 작업을 하는 튜링 기계 $M$을 정의하자.

1. 입력된 다항식 $p$의 미지수 개수를 찾는다.

2. $p$에 $x_1, x_2, x_3, \ldots$를 하나씩 대입한다. 만약 $p$의 값이 $0$이 된다면 accept 한다.

사실 $M$은 모든 미지수 조합을 차례차례 대입하여 해인지를 확인하는 매우 단순한 알고리즘이다. 만약 $(a_1, \ldots, a_n)$이 $p$의 해가 된다면 언젠가는 accept될 것이다. 반면 $p$의 해가 없다면 과정 2가 무한히 반복되어 $M$은 정지하지 않을 것이다. $M$은 해가 있는 경우는 유한 번의 연산 후 결과를 내놓으므로 판정할 수 있지만, 해가 없는 경우 연산이 영원히 끝나지 않으므로 답을 알 수 없다. 만약 연산이 아무리 많이 진행되었다고 해도, 바로 다음에 끝나버릴 수 있으므로 $p$가 해를 가지지 않는다고 멋대로 판단을 내릴 수 없다. 따라서 $M$은 원래 문제에 대한 완전한 해결책은 아니다.

여기서 이런 생각을 할 수 있다. 만약 해의 후보가 될 수 없는 것들을 사전에 제거할 수 있지 않을까? 이 아이디어는 미지수가 한 개인 경우에 적용할 수 있다. 미지수가 한 개인 경우 유리근 정리(rational root theorem)를 사용하여 정수해의 후보를 유한개로 줄일 수 있다. 유리근 정리는 다음과 같다.

계수가 모두 정수인 다항방정식 $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 = 0$이 유리수해를 가진다면 해당 해는 $a_0$의 인수 / $a_n$의 인수 형태로 표현된다.

정리에 따르면 $a_0$의 인수 / $a_n$의 인수를 모두 모아놓은 집합은 모든 유리수해들을 포함하게 된다. 따라서 이것이 유리수해의 후보 집합이 된다. $a_0$의 인수와 $a_n$의 인수의 개수는 유한하므로 유리수해의 후보 역시 유한개이다. 또한 모든 정수해는 유리수해이므로, 유리수해들의 집합에서 정수인 것들만 모아놓으면 정수해의 후보가 된다. 이 정수해 후보들의 집합을 $X$라고 하고, 다음과 같이 튜링 기계 $M_1$을 정의하자.

1. $p$에 $x_1, \ldots, x_k \in X$를 하나씩 대입한다. 만약 $p$의 값이 $0$이 된다면 accept한다.

2. 과정 1이 끝날 때까지 accept되지 않았다면 reject한다.

이제 $M_1$은 항상 유한 번의 연산 후에 종료되어 정수해의 존재 여부를 내놓는다.

그러나 임의의 미지수 개수를 가진 다항식의 경우 이렇게 후보를 줄여서 과정을 유한 번으로 줄일 수 없다. 더 나아가 어떤 튜링 기계도 유한 번에 해의 존재 여부를 결정할 수 없다. 이것을 Yuri Matiyasevich 등이 증명한 것이다.

미지수가 한 개인 경우와 같이 모든 입력에 대해 유한 번 연산 후에 accept 또는 reject를 출력하는 튜링 기계가 존재한다면($M_1$) 해당 문제를 결정 가능하다(decidable)라고 한다. 원래의 문제 같이 accpet 하는 경우는 유한 번 연산 후에 동작이 끝나지만 그렇지 않은 경우 연산이 끝나지 않을 수 있는 튜링 기계가 존재한다면($M$) semidecidable 또는 Turing-recognizable 하다고 한다. 힐베르트의 10번째 문제는 후자에는 해당되지만 전자에는 해당하지 않는다.

참고문헌

• Sipser, M. (2012) Introduction to the Theory of Computation, 3rd ed., Cengage Learning.
• https://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem