d라이브러리

지금까지 논리주의 프로그램, 수학 체계의 무모순성, 그리고 증명 불가능한 문장 등 괴델의 불완전성 정리를 이해하기 위한 다양한 이야기를 했어요. 어떤 독자는 이런 이야기가 무슨 의미가 있는지 궁금할 텐데 앞서 설명한 괴델의 불완전성 정리는 21세기의 가장 놀라운 발명품인 ‘컴퓨터ʼ가 탄생하는 데 큰 역할을 했어요. 오늘은 그 이야기를 해 볼게요.

♥ 유용한 수학

“나는 유용한 일을 한 적이 없다. 나의 어떤 발견도 직접적이든 간접적이든, 좋든 나쁘든 상관없이 세상을 변화시키지 않았고 앞으로도 변화시키지 않을 것이다”

많은 수학자가 자신의 연구가 현실에서 얼마나 쓸모 있을지에 대해 신경 쓰지 않을지도 모릅니다. 감히 추측하자면 독일 수학자 다비트 힐베르트나 미국 수학자 쿠르트 괴델도 하디와 비슷한 마음으로 논리학 연구에 임했을 것입니다.

그럼에도 많은 수학 연구는 뜻밖의 과정을 거쳐 공학이나 과학에서 아주 유용하게 사용됩니다. 괴델의 불완전성 정리도 그런 사례 중 하나입니다. 순수논리학에서만 다룰 것 같은 이 정리는 컴퓨터를 이 세상에 등장시켰지요.

◆ 가상의 기계

시간을 잠시 거슬러 올라가 볼까요. 1928년 힐베르트는 수학의 발전을 위한 두 가지 과업을 제시합니다. 첫째는 참인 명제는 항상 증명 가능하다는 것을 보이는 것이고, 둘째는 어떤 명제가 주어졌을 때 이 명제가 증명 가능한지 아닌지를 판단하는 방법을 제시하는 것입니다. 수학 용어로 말하자면 첫 번째 목표는 수학의 완전성을, 두 번째 목표는 수학의 결정 가능성을 보이는 것입니다.

그러나 1931년 괴델의 불완전성 정리가 발표됨으로써 힐베르트의 첫 번째 목표는 불가능한 것으로 드러났습니다. 충격적인 발표에 자극을 받은 영국 수학자 막스 뉴먼은 자신의 강의에 불완전성 정리에 관한 내용을 포함하는데요. 이 수업의 수강생 중에는 앨런 튜링이라는 천재 학생이 있었습니다. 튜링은 영국 수학자로, 훗날 컴퓨터 공학 및 정보공학의 이론적 토대를 마련하는 인물이지요. 튜링은 괴델의 불완전성 정리에 깊은 감명을 받고, 어떻게 하면 괴델의 아이디어를 발전시켜 힐베르트의 두 번째 목표 또한 불가능하다는 것을 보일 수 있을지 궁리했어요. 이윽고 1936년 튜링은 수학의 결정 가능성마저 반증하는 논문을 발표하는데요. 이 논문은 아주 독창적인 아이디어를 사용합니다.

튜링은 어떤 가상의 기계를 상상했습니다. 현대 학자들은 이 기계를 ‘튜링 기계’라고 불러요. 튜링 기계는 주어진 일련의 절차(프로그램)을 수행하는 기계예요. 예를 들어 아래의 두 절차를 입력 받았을 때 튜링 기계의 출력 값은 다음과 같습니다.

튜링 기계의 동작은 단순하지만 튜링 기계는 상상 이상으로 강력합니다. 튜링 기계는 다른 기계가 풀 수 있는 문제라면 모두 풀 수 있거든요. 예를 들어 공학용 계산기로 ‘방정식’을 풀 수 있으므로, 튜링 기계도 가능합니다. 심지어 컴퓨터로 두는 체스도 튜링 기계로 둘 수 있습니다. 만약 튜링 기계가 해결할 수 없는 문제가 존재한다면 그것은 그 문제를 해결하는 기계적인 절차가 아예 존재하지 않음을 의미합니다.

♠ 튜링 기계가 못 푸는 문제

그렇다면 과연 튜링 기계가 해결할 수 없는 문제가 있을까요? 언뜻 보기에는 없을 듯합니다. 컴퓨터는 로켓도 쏘아 올리고, 바둑도 두고, 자동차도 운전합니다. 튜링 기계는 컴퓨터보다도 더 강력한 기계지요.

그러나 튜링 기계로도 풀 수 없는  문제가 있는데요, 바로 ‘정지 문제’입니다.

예를 들어 볼게요. 프로그램 Five는 입력 값이 5보다 작으면 정상적으로 종료하지만, 입력 값이 5 이상이면 영원히 종료하지 않습니다. 따라서 우리가 찾고자 하는 프로그램 P(x)는 Five와 4를 입력 받으면 참을 출력하고, Five와 6을 입력 받으면 거짓을 출력해야 합니다.

언뜻 보면 정지 문제는 체스 두기나 자동차 운전하기보다 훨씬 쉽게 느껴집니다. 그러나 튜링은 정지 문제를 푸는 프로그램은 논리적으로 존재할 수 없음을 보였습니다. 모든 명제가 증명 가능한지 기계적으로 판별하는 것이 가능하다면 ‘프로그램 P(x)는 정상적으로 종료한다’라는 명제 역시 P(x)가 정상적으로 종료하는지 판별할 수 있는데요. 정지 문제를 풀 수 없다는 사실은 수학이 결정 가능성을 지니지 않음을 의미합니다!