튜링의 불완전성 정리 증명

※ 혼자 공부한 내용을 정리한 글입니다. 엄밀한 내용이 궁금하다면 참고 문헌을 읽어 보길 권합니다.

1. 불완전성 정리란?

힐베르트는 수학 체계가 완전하다고 믿었다. 즉 모든 참인 증명은 수학 체계의 공리에서 유도될 수 있으며 따라서 공리에서부터 출발하여 모든 참인 증명을 기계적으로 만들 수 있다고 여겼다. 하지만 괴델이 자연수의 체계에 대해 자연수 체계 속에서 증명될 수 없지만 체계 외부에서 보면 참인 명제가 존재한다는 것을 증명했으며, 이를 불완전성 정리라고 한다.

 

간략한 증명 방법은 다음과 같다.

G = G는 증명불가능하다.

이러한 명제 G가 존재한다고 가정하자. 명제 G는 거짓일 수 없으므로 참이지만 증명불가능한 명제가 되며, 곧 공리계의 불완전성을 의미한다. 위 명제는 명제 속에서 자기 자신을 언급하는 순환논증의 오류를 범하고 있기 때문에 수학의 불완전성과는 상관없다고 여겨졌지만, 괴델이 명제를 고유한 자연수와 대응시켜 메타수학의 명제를 수학의 명제로 바꾸고, 이를 통해 명제 안에서 자기 자신을 오류 없이 언급할 수 있음을 보여 수학 체계의 불완전성을 증명할 수 있었다.

 

2. 튜링의 불완전성 정리

튜링은 자신만의 증명에서 ‘기계적’이라는 말에 주목했다. 튜링은 기계적인 과정이 무엇인지를 정의한 뒤, 자신이 정의한 기계적인 방법을 통해 절대 풀 수 없는 문제를 제시하였다. 이 과정에서 자신이 정의한 기계적인 방법이 충분히 범용적이라는 것을 증명하기 위해 다양한 예시와 함께 ‘보편만능의 기계’라는 기계를 생각해 냈다. 이를 통해 기계적으로는 수학의 모든 사실을 알아낼 수 없음을, 즉 불완전성 정리를 증명한 것이다.

 

튜링이 정의한 기계는 네 개의 부품으로 이루어진다. 이 네 개의 부품으로 이루어진 가상의 기계를 튜링기계라고 한다. 튜링기계는 칸이 한 줄로 무한히 늘어져 있는 테이프와 테이프의 임의의 칸을 가리키며 해당 칸의 값을 읽거나 수정할 수 있는 화살표, 현재 기계의 상태를 특정한 기호로 나타내는 장치, 현재 화살표가 가리키는 값과 기계의 상태를 고려하여 기계의 동작을 정의해 놓은 규칙표로 구성되어 있다. 이러한 부품을 사용하여 수많은 튜링기계를 만들 수 있다.

 

튜링기계는 규칙표에 따라 칸의 값을 바꾸고, 자신의 상태를 바꾸고, 화살표를 어느 방향으로 이동시킬지 결정한다. 즉, 튜링기계를 특징하는 가장 핵심적인 요소는 그 기계의 규칙표이다. 규칙표에서 사용하는 기호의 개수는 유한하게 한정되어 있으며, 따라서 각 기호를 특정한 자연수와 대응시킬 수 있다. 규칙표의 기호를 모두 대응시킨 자연수로 바꾼 뒤 자연수를 일렬로 쭉 나열하면 규칙표 전체와 대응되는 자연수가 하나 만들어진다. 이때 각 기호가 모두 각자 다른 자연수에 대응되었다면 규칙표 또한 고유한 자연수와 대응시킬 수 있으며 마찬가지로 자연수를 고유한 규칙표로 바꾸는 작업도 수월하게 할 수 있다. 즉, 튜링기계를 정의역으로, 자연수를 치역으로 가지는 일대일함수가 존재한다.

 

자연수에 대응되는 튜링기계는 유일하며 자연수는 규칙에 따라 서술되어 있으므로 다른 튜링기계를 입력으로 받아 실행하는 튜링기계를 상상해 볼 수 있다. 이러한 튜링기계는 다른 모든 튜링기계의 일을 모두 수행할 수 있기 때문에 이러한 튜링기계를 ‘보편만능의 기계’라고 부른다. 보편만능의 기계는 튜링이 제시한 여러 다른 튜링기계와 함께 튜링기계가 모든 기계적 동작을 수행할 수 있다는 논거로 사용되었고, 아직까지 튜링기계를 능가하는 기능을 가진 기계적 동작의 정의는 등장하지 못했다.

 

다시 불완전성 정리로 돌아오면, 기계적인 과정을 통해 모든 수학적 사실을 만들어낼 수 있다는 말은 이러한 일을 하는 튜링기계가 존재한다는 것과 같다. 이러한 튜링기계를 A라고 부르자. 튜링기계 A가 해결하지 못하는 문제를 제시한다면 불완전성 정리를 증명하게 된다. 이를 위해 튜링기계의 멈춤 집합이라는 개념이 활용된다. 튜링기계는 항상 유한한 작업을 수행하고 멈출 수도, 항상 영원히 멈추지 않을 수도, 입력에 따라 멈춤 여부가 결정될 수도 있다. 여기서 멈춤 집합이라는 개념이 탄생한다. 임의의 튜링기계 M이 있을 때, M의 멈춤 집합은 M을 멈추게 하는 모든 입력들의 집합이다. ‘모든’이라는 표현에 주의해야 한다.

 

이때 대각선 논법을 사용하여 모든 튜링기계의 멈춤집합과 다른 집합을 만들 수 있다. 이 집합을 D라고 부르자. D를 만들기 위해서는 다음 작업을 모든 튜링기계에 대해 수행해 주어야 한다. 임의의 튜링기계 M에 대해 M을 자연수로 나타낸 수를 m이라고 부르겠다. 이때 m이 M의 멈춤 집합에 속하지 않을 때만 m을 D에 넣는다. 이 작업을 모든 튜링기계에 대해 수행하면, 모든 튜링기계는 자신을 나타낸 자연수를 D 또는 자신의 멈춤 집합 중 한 곳에만 가지게 되고, 따라서 D는 모든 튜링기계의 멈춤 집합과 다르다. 다시 말하면, D를 멈춤 집합으로 가지는 튜링기계는 존재할 수 없다.

 

이제 임의의 자연수 n에 대해 “n은 집합 D의 원소이다”라는 명제를 생각해보자. 이 명제는 말할 것도 없이 자연수 체계 내부의 명제이다. 하지만 튜링기계 A로 이 명제를 해결할 수 있다면 모순이 발생한다. 이 명제를 해결할 수 있다면, 튜링기계 A를 보편만능의 기계로 흉내낸 것에 적당한 규칙을 더하여 n이 집합 D에 속한다면 그대로 멈추고, 그렇지 않다면 영원히 멈추지 않는 튜링기계를 만들 수 있기 때문이다. 이러한 튜링기계의 멈춤 집합은 정확히 집합 D가 되며, 이는 집합 D의 정의와 모순된다. 따라서 튜링기계 A가 해결하지 못하는 문제를 제시했으므로 불완전성 정리를 증명할 수 있다.

 

비록 힐베르트와 수학계의 꿈은 끝났지만, 불완전성 정리는 컴퓨터과학의 시발점이 되었다. 튜링기계에서는 튜링기계 자신이 다른 튜링기계의 데이터가 될 수 있다. 이러한 구조는 폰 노이만 구조에 차용되었으며, 이는 현대의 모든 컴퓨터가 채택하고 있는 디자인이다. 폰 노이만 구조에서는 운영 체제라는 거대한 프로그램이 다른 프로그램들을 실행하며, 운영 체제에 의해 실행되는 응용 프로그램들도 다른 프로그램을 입력으로 받아 실행하기도 한다. 컴파일러와 인터프리터가 이러한 응용프로그램에 해당된다. 또한 튜링기계의 테이프는 컴퓨터의 메모리로, 화살표는 입출력장치로, 규칙표는 CPU로 그대로 구현되어 있다. 이러한 점에서 튜링기계가 현대 컴퓨터의 하드웨어/소프트웨어 전반에 영향을 주었다는 사실을 분명히 알 수 있다. 뿐만 아니라 아직까지 기계적인 계산의 정의는 튜링의 정의에서 벗어나지 못했으며, 이로 인해 프로그래밍 언어의 능력을 튜링기계를 기준으로 판단한다. 튜링기계는 컴퓨터과학의 가장 기초가 되는 개념이자 컴퓨터과학 전체를 감싸는 거대한 틀이라고 할 수 있다.

 

참고문헌

수학자, 컴퓨터를 만들다(마틴 데이비스 저, 박정일/장영태 옮김, 지식의풍경)

컴퓨터과학이 여는 세계(이광근 저, 인사이트)

https://blog.zarathu.com/posts/2019-05-20-godelincompleteness/ (괴델의 증명 관련)

https://ropas.snu.ac.kr/~kwang/memo/turing1935.pdf 

(튜링의 증명에 대한 서울대학교 이광근 교수님 칼럼)