기계적 절차와 수학

괴델 : John Casti. Werner De Pauli 지음, 박정일 옮김, 몸과 마음, 2002 (원서 : Gödel : A Life of Logic, 2000), page 123~148

1. 마술 기계와 바쁜 해리

2. 튜링 기계

3. 바쁜 해리 놀이

4. 튜링 기계 게임

5. 멈춤문제

6. 진리는 증명보다 더 이상한 것이다

다음과 같은 두 논변을 살펴보기로 하자.

논변 A

모든 사람은 사랑하는 사람 (a lover) 을 사랑한다.
철수는 자신을 사랑하지 않는다.
그러므로 철수는 영희를 사랑하지 않는다.

논변 B

모든 사람은 사랑하는 사람이거나 어떤 사람은 사랑하는 사람이 아니다.
만일 모든 사람이 사랑하는 사람이라면, 갑돌이는 확실히 사랑하는 사람이다.
만일 모든 사람이 사랑하는 사람인 것은 아니라면, 최소한 사랑하지 않는 (nonlover) 이 한 사람 존재한다. 그녀를 병란이라고 하자.
그러므로 만일 병란이 사랑하는 사람이라면, 모든 사람은 사랑하는 사람이다.

인간의 성향에서 종종 확인될 수 있는 모호한 사고와 논리적 모순을 감안할 때, 두 추론의 연쇄가 모두 논리적으로 옳다는 것을 알게 되면 아마도 우리는 대부분 좀 놀라게 될 것이다. 만일 우리에게 어떤 논리기계가 있어서 그 안에 이런 종류의 진술들을 집어 넣고 손잡이를 돌려서, 그 논변이 논리적으로 타당한지 여부를 그 기계가 확정적으로 우리에게 말해준다면 이 얼마나 멋진 일이겠는가. 이러한 기계를 논리학자들은 결정절차라고 한다. 바로 이러한 절차에 대한 연구가 1930 년대에 영국의 수학자 앨런 튜링 (Alan Turing) 으로 하여금 계산의 기초를 탐구하도록 촉발시킨 계기가 되었다. 이 이야기를 쉽게 풀어나가기 위해서 논리적으로 옳다는 것 - 예를 들면 논변 A 와 B 는 모두 논리적으로 옳은 것이다 - 과 참이라는 것 - 즉 실제세계의 철수가 실제세계의 영희를 사랑하지 않는다는 것은 참이다 - 간의 차이에 관한 기본적인 생각들에 초점을 맞춰보자.

논리학과 수학에서 진리로 나아가는 길은 오늘날 형식체계라고 하는 것들로 포장되어 있다. 우리는 2 장에서 그러한 대상들의 본질을 살펴보았다. 기본적으로, 하나의 형식체계는 추상적 기호들의 알파벳, 그러한 기호들을 문법적으로 '옳은' 기호열로 배열하는 방법에 대한 문법, 다른 기호열에서 도출되지 않으면서도 문법적으로 옳다고 받아들이는 기호열인 공리들의 집합, 그리고 존재하는 옳다고 받아들이는 기호열인 공리들의 집합, 그리고 존재하는 기호열에서 문법적으로 옳은 새로운 기호열을 만들어내는 방법을 우리에게 말해주는 논리적 추론규칙들로 이루어진다.

이제 잘 형성된 진술 A 가 우리에게 주어졌다고 하고, 그것이 그 체계의 공리들에서 따라나오는 논리적으로 옳은 귀결인지의 여부를 묻는다고 하자. 만일 유한한 진술들의 사슬 가 존재한다면 A 는 그 체계에서 증명가능하다고 말한다. 이때 각각의 Mi 는 그 체계의 공리들 중 하나이거나 추론 규칙들 중 하나를 통해 이전의 M 에서 얻어지는 것이어야 한다. 그러한 증명열이 존재하는 잘 형성된 진술들을 그 형식체계의 정리라고 한다. 우리는 앞에서 몇 가지 예를 살펴보았다. 이 지점에서는 관련된 생각을 되짚어보기 위해서 장기놀이의 예를 들어보겠다.

잠시 생각해 보면, 장기놀이는 실제로는 흑돌과 백돌이라는 추상적 기호들의 집합과 장기판의 사각형들이라는 추상적 기호들의 집합간의 관계다. 간단히 말하면 그 놀이의 본질에 관한 한, 이 기호들의 물질적 구현에 대해 중요한 것은 아무것도 존재하지 않는다. 예컨대 우리는 장기 돌을 표현하기 위해 다양하게 그 어떤 기호들의 집합이든 부여할 수 있고, 장기판의 사각형들을 표현하기 위해 다른 기호들의 집합 (이를테면 양의 정수 1, 2, ……, 64 의 집합) 을 사용할 수 있다. 이러한 체계의 문법은 그렇게 되면 어떤 기호들의 열 (진술들) 이 잘 형성되었는지 (즉 장기판에서 돌들의 타당한 조합을 표현하는지) 를 규정할 것이다 (예를 들면 흑 주교 (bishop) 는 백 사각형 위에 놓일 수 없다). 이렇게 문법적으로 옳은 문장들은 장기놀이의 각각의 단계에서 가능한 사태들을 표현한다. 게다가 이 형식체계의 추론규칙들은 잘 형성된 하나의 기호열을 다른 것으로 변형할 수 있는 다양한 방식일 뿐이다. 다른 말로 하면 추론규칙들은 장기놀이의 각 단계에서 허용 가능한 수를 표현한다. 마지막으로 장기놀이의 유일한 공리는 놀이를 시작할 때 장기판에 장기 돌이 놓여 있는 방식에 대응하는 기호열이다.

따라서 우리는 장기 돌과 장기판의 실제세계가 오직 추상적 기호들, 추론 규칙들, 그리고 공리들만으로 이루어진 형식적 세계형태로 번역될 수 있다는 것을 알 게 된다. 이 점은 유한한 수의 낱말들로 기술될 수 있는 여타의 모든 실제세계에도 그대로 적용된다. 우리는 이 점을 나중에 상세하게 살펴보게 될 것이다.

여기에서 완전히 다른 두 세계가 섞였다는 것을 다시 한 번 강조하지 않을 수 없다. 두 세계란 순수하게 구문론적인 형식체계의 세계와 수학적 대상들 및 그 속성들로 이루어진 유의미한 세계다. 이 세계에 각각 진리의 개념이 존재한다. 전자의 예로 우리는 형식체계의 정리들을 들 수 있고, 후자에 대해서는 '2 + 5 = 7' 과 '한 평면에서의 삼각형 내각의 합은 180 도다' 와 같이 수학적 영역에서 실제로 옳은 진술들을 들 수 있다. 제 1 장에서 살펴본 바와 같이, 두 세계 사이의 관련성은 형식체계의 요소들을 수학적 구조의 대상들과 연산들로 해석하는 것에 놓여 있다. 일단 이러한 사전이 작성되고 그와 관련된 해석이 확립되면, 우리는 수학적 구조의 참인 사실들과 형식체계의 정리들 간에 완벽한 일 대 일 대응이 존재할 것이라는 희망을 품을 수도 있다.

우리는 모든 진리가 각각 어떤 하나의 정리로 번역되고 또 역으로도 그렇게 되는 형식체계를 다루고자 한다. 그러한 체계는 완전한 체계라고 일컬어진다. 우리는 기호들의 세계와 수학적 사실들의 세계 사이의 이러한 이상적인 관계가 어느 정도로 가능하게 될지 간략하게 고찰할 것이다. 하지만 잠시 형식체계를 다루면서 계산기계와 형식체계의 안팎을 좀더 자세히 들여다보기로 하자.

튜링으로 하여금 지금은 튜링 기계라고 이름붙인 이론적인 기계장치를 고안하도록 한 것이 바로 결정문제이다. 결정문제는 다음과 같다. 모든 형식체계 F 에 대해, F 에서 문법적으로 옳은 모든 기호열을 각각 '결정' 하는 유한하게 기술이 가능한 형식체계 F 를 찾는 것은 가능한가? 느슨하게 말하면 우리는 형식체계 F 에서 주어진 잘 형성된 기호열에 대해서 그것이 정리인지 아닌지를 우리에게 말해줄 수 있는 어떤 체계적인 절차가 존재하는지 여부를 묻고 있는 것이다.

튜링은 결정문제를 해결하기 위해서 현대 계산이론에서 관건인 튜링 기계를 만들어냈다. 계산이론의 맥락 내에서 수행된 결정문제에 대한 튜링의 해결책이 수리논리학에서 괴델의 결과와 추상적으로 동일하다는 것이 밝혀졌다. 그러면 이제 튜링이 결정문제를 어떻게 혁신적으로 해결했는지 살펴보기로 하자.

1. 마술 기계와 바쁜 해리

계산이란 무엇인가? 참으로 기묘하게도 수천 년 동안 인간이 계산해왔음에도 겉으로 보기에 간단한 이 질문에 대해 어떤 적절한 과학적 대답도 1935 년까지는 나오지 못했다. 그 해에 튜링은 케임브리지 대학의 학생이었고, 어떤 수리논리학 강의를 듣고 있었다. 강의의 중심적인 주제는 이를테면 러셀과 화이트헤드의 유명한 (또는 악명 높은) 저작인 『수학 원리』의 언어에서 만들 수 있는 가능한 모든 수에 관한 진술의 참 또는 거짓을 확정해줄 유한한 규칙들의 집합 - 기계적 절차 - 이 존재할 수 있느냐는 문제였다. 간단히 말하면 이 물음은 우리가 수에 관한 어떤 진술을 입력시키면 유한한 시간이 지난 후에 그 진술에 대해서 참 또는 거짓이라는 판정을 산출하는 그러한 기계가 존재하느냐는 것이었다.

이 유명한 결정문제를 해결하기 위해서 그러한 기게적 절차, 즉 효과적 절차를 지닌다는 것이 무엇을 의미할지를 숙고한 끝에 튜링은 수학적 유형의 컴퓨터를 개발했다. 하나의 계산을 수행한다는 것이 무엇을 의미하느냐 하는 문제는 바로 추상적인 기계장치, 즉 튜링 기계가 최초로 완벽하게 답변해 주었다.

튜링은 인간이 계산을 수행할 때 실제로 행하는 것을 살펴보는 평범한 방법을 채택하였다. 본질을 추려내면, 계산이란 규칙들의 집합을 따르는 기계적인 방식이라는 것이 밝혀진다. 예를 들어 2 의 제곱근을 계산하고자 한다면, 우리는 로 수렴하는 수들의 집합 를 만들어낼 다음과 같은 규칙을 사용할 수 있다 : . 최초의 근사치를 이를테면 로 시작하면, 이 규칙에 따라 더 근사치인 , , 가 계속 산출된다. 단지 세 단계만 거쳐도 우리는 네 자리가 일치하는 원하는 답을 얻는다. 여기에서 이렇게 2 의 제곱근을 계산하는 데 쓰이는 이른바 뉴턴 - 랩슨 (Newton-Raphson) 방법에서 중요한 것은 급속한 수렴률이 아니라, 그 절차가 원하는 값을 찾는 순수하게 기계적인 단계적 절차 (전문적으로는 알고리듬) 라는 것이다.

그러한 절차에서 모든 단계가 완전하게 그리고 명시적으로 규정된다는 사실에서 튜링은 계산기계를 구성하는 일이 가능할 것이라고 믿었다. 일단 알고리듬과 출발점이 그 기계에 주어지면, 일련의 결과에 대한 계산은 도중에 인간의 어떤 판단이나 간섭도 개입하지 않는 순전히 기계적인 문제가 된다. 그러나 그렇게 되기 위해서는 이러한 계산 임무를 수행하는 특수한 유형의 기계가 필요할 것이다. 아무 기계장치나 그렇게 할 수 있는 것은 아니다. 튜링이라는 천재가 보여준 것은 그가 발명한 아주 원초적인 유형의 추상적인 계산기계가 실제로 상상 가능한 가장 일반적인 유형의 계산기라는 것이다. 사실 지금까지 실제 생활에 쓰이는 모든 계산기는 튜링이 꿈꾸던 기계를 단지 물질적으로 구현한 하나의 특수한 경우에 지나지 않는다. 이 점은 기계의 한계를 이해하는 데 아주 중요하기 때문에 좀더 상세하게 고찰하는 것이 필요하다.

2. 튜링 기계

튜링 기계는 두 가지 구성 요소로 이루어진다. 첫째, 정사각형으로 칸을 매긴 무한히 긴 테이프. 이때 각각의 정사각형에는 일련의 유한한 기호들 중 하나가 포함되어 있다. 둘째, 계산 절차의 각 단계에서 어떤 유한한 수의 상태들이나 조합들 중 하나에 있을 수 있는 검사 헤드. 그 헤드는 테이프에 있는 정사각형들을 읽을 수 있고 각각의 정사각형 위에 기호를 하나 쓸 수 있다. 튜링 기계의 작동은 알고리듬, 또는 이른바 프로그램이 제어한다. 프로그램은 유한한 수의 지시사항들로 이루어지는데, 각각의 지시사항은 다음과 같은 가능한 작동들을 조합한 것이다. 헤드의 현재 상태를 바꾸거나 유지하라. 현재의 정사각형 위에 새로운 기호를 인쇄하거나 이전의 기호를 그대로 유지하라. 왼쪽이나 오른쪽으로 정사각형 하나를 이동하라. 멈춰라. 단순 가능한 작동들은 일곱 개뿐이다. 전체 상황은 그림 1 에 묘사되었는데, 여기에서 튜링 기계는 내적 상태로서 A 로부터 L 까지 12 개를 지니고 있다. 가능한 일곱 개의 작동들 중에서 헤드가 어떤 단계에서 어떤 것을 취하느냐 하는 점은 헤드의 현재 상태에 의해, 그리고 헤드가 현재 검사하는 정사각형에서 무엇을 읽는지에 의해 결정된다. 그러나 이렇듯 추상적인 용어로 계속 말하는 것보다는 차라리 그러한 장치가 어떻게 작동하는지를 살펴보기 위해 예를 드는 것이 더 좋을 것이다. 우리에게 세 개의 내적 상태 A, B, C 를 지닌 어떤 튜링 기계가 있다고 가정하고, 또, 그 테이프 위에 쓰일 수 있는 기호가 오직 두 개의 정수 0 과 1 뿐이라고 가정하자. 이제 우리가 두 정수의 덧셈을 수행하기 위해 이 기계를 사용한다고 가정하자. 분명하게 하기 위해서, 우리는 정수 n 을 테이프에 n 개의 1 들이 잇달아 적힌 기호열로 나타낼 것이다. 표 1 에 나오는 프로그램은 이러한 3 - 상태 튜링 기계를 사용해서 두 정수의 덧셈을 하기 위한 것이다.

그림 1  12-상태 튜링 기계

표 1  덧셈에 대한 튜링 기계 프로그램

독자들은 다음과 같은 방식으로 그 표의 항목들을 해석해야 한다. 첫 번째 항목은 헤드가 인쇄해야 하는 기호이고, 두 번째 항목은 헤드가 움직여야 하는 방향 즉 오른쪽 (R) 이나 왼쪽 (L) 이며, 마지막 항목은 헤드가 다음에 움직여가는 상태다. 이 기계는 헤드가 상태 C 로 가자마자 멈춘다는 것에 주목하라. 수 2 와 5 를 더하는 특수한 경우 이 기계가 어떻게 작동하는지를 보도록 하자.

우리의 관심은 이 기계를 사용하여 2 와 5 를 더하는 데 있으므로, 우리는 모두 빈칸으로 이루어진 (모두 0 인) 입력 테이프에 두 개의 1 과 다섯 개의 1 을 위치시키는데, 그것들이 서로 다른 수라는 것을 표시하기 위해 그것들 사이에 0 을 놓는다. 그렇게 되면 이 기계는 다음과 같은 입력 테이프를 읽으면서 시작한다.

규약에 따라, 헤드가 상태 A 에서 출발해서 왼쪽에서 0 이 아닌 첫 번째 기호를 읽는다고 가정하자. 이 기호는 1 이다. 그러면 이 프로그램은 기계에게 정사각형에 1 을 인쇄하고 오른쪽으로 가라고 말하는데, 이때 내적 상태 A 는 그대로 유지된다. 헤드가 여전히 상태 A 에서 현재의 기호 1 을 읽으면 기계는 이전 단계를 반복하고 오른쪽으로 정사각형 하나를 더 이동한다. 이제 상황이 바뀌어 헤드는 0 을 읽는다. 프로그램은 기계에게 1 을 인쇄하고 오른쪽으로 이동해서 상태 B 로 바꾸라고 말한다. 프로그램의 나머지 단계들을 완성하는 일은 독자의 몫이다. 그러면 독자들은 기계가 마지막으로 멈출 때의 테이프는 2 와 5 를 분리시킨 0 이 제거되었다는 점을 제외하면 이전의 입력 테이프와 다를 바가 없다는 것을 알 수 있다 (즉 테이프는 바라던 대로 일렬로 된 일곱 개의 1 을 지니게 될 것이다).

튜링의 생각에 담긴 혁명적인 함축을 살펴보기 전에, 튜링 기계가 물질적인 장치라는 일상적 의미의 기계가 아니라는 점을 분명하게 강조해야 한다. 오히려 튜링 기계는 프로그램에 의해 완전하게 규정되는 '명목상의 계산기 (paper computer)' 다. 따라서 우리가 앞으로 기계라는 용어를 쓸 때, 독자는 하드웨어라는 생각을 모두 지워버리고, 프로그램 또는 알고리듬 (즉 소프트웨어) 으로 해석해야 한다. 기계라는 용어에 대한 이러한 남용이 무한한 저장 테이프라는 튜링의 생각에 은연중에 들어 있는 것이지만, 가능한 한 분명하게 그렇게 구분하는 것은 중요하다. 튜링 기계 = 프로그램.

이 책을 쓰기 위해 사용되는 가정용 컴퓨터를 비롯해서 현대의 계산장치는 몇몇 내적 상태와 아주 제한된 검사 헤드 작동방식을 지닌 어떤 튜링 기계보다도 계산력에서는 더욱 더 복잡하고 큰 것으로 보인다. 그럼에도 이것은 사실과 다르다. 튜링이라는 천재가 인식한 것은 어떤 계산기계에서 수행 가능한 어떤 알고리듬도 (즉 어떤 프로그램도) - 이상적이든 그렇지 않든 - 그의 기계, 이름하여 보편 튜링 기계 (간단히 UTM) 의 어떤 특정한 형태로 수행될 수 있다는 것이다. 따라서 하드웨어에 의존하는 컴퓨터의 속도를 제외한다면, 가정용 기계가 할 수 있으면서 UTM 으로 할 수 없는 어떤 계산도 존재하지 않는다.

튜링은 UTM 을 규정하기 위해서 문제가 되는 입력자료뿐만 아니라 프로그램 자체도 0 과 1 의 열로 코드화할 수 있다는 것을 깨달았다. 결과적으로 우리는 프로그램을 또 다른 종류의 입력자료로 여길 수 있다. 다시 말해 프로그램이 처리하려는 자료들과 함께 그 프로그램을 테이프에 쓸 수 있는 것이다. 표 2 는 이렇게 코드화하는 여러 방식들 중 하나가 제시되고 있다.

이러한 근원적인 통찰과 더불어, 튜링은 어떤 다른 프로그램 P 의 작동을 흉내낼 수 있는 프로그램을 구성했는데, 이때 P 는 이 프로그램의 입력의 한 부분으로 주어진다 (달리 말하면, 그는 UTM 을 만들어냈다). UTM 의 조작은 더할 나위 없이 단순하다.

우리에게 프로그램 P 가 규정한 특정 튜링 기계가 있다고 가정하자. 튜링 기계는 그것의 프로그램에 의해 완전히 결정되기 때문에, 우리에게 필요한 모든 것은 프로그램 P 를 입력자료들과 함께 UTM 에 입력시키는 것이다. 그러면 UTM 은 자료들이 주어질 때 P 의 작동을 흉내낼 것이다. 원래의 기계에서 프로그램 P 를 작동시키는 것과 튜링 기계 P 인 것처럼 UTM 을 흉내내게 하는 것 사이에는 어떤 인식 가능한 차이도 없을 것이다.

이론적인 관점에서 보면 튜링 기계에서 중요한 것은 그것이 형식적인 수학적 대상을 표현한다는 것이다. 튜링 기계의 발명과 더불어, 우리는 최초로 어떤 것을 계산한다는 것이 무엇을 의미하는지에 대해 잘 정의된 개념을 지니게 되었던 것이다. 그러나 그렇게 되면 다음과 같은 물음이 생겨난다. 우리는 정확하게 무엇을 계산할 수 있는가? 특히 각각의 모든 수를 계산할 수 있는 어떤 적절한 튜링 기계가 있는가? 아니라면 계산의 한계를 영원히 넘어서는 수들이 존재하는가? 튜링은 자신의 선구적인 1936 년 논문에서 이러한 계산 가능성의 문제를 언급했는데, 여기에서 그는 튜링 기계를 이러한 근본적인 물음들에 대답하는 한 가지 방법으로 도입했다.

무엇보다 먼저, 하나의 수가 계산 가능하다는 것이 무엇을 의미하는지를 분명하게 해야 할 것이다. 간단히 말해 모두 0 만 있는 테이프로 멈추는 튜링 기계가 있는 경우, 정수 n 은 계산 가능하다고 말한다. 실수를 계산하는 경우에는 대부분의 실수가 무한한 수의 자릿수들로 이루어졌기 때문에 좀더 교묘한 수법이 필요하다. 우리는 하나의 실수의 자릿수들을 차례로 연속해서 인쇄할 수 있는 튜링 기계가 있는 경우 그 실수는 계산 가능하다고 말한다. 물론 이 경우에 그 기계는 일반적으로 영원히 작동한다. 이러한 정의를 염두에 두고서 수를 계산하는 우리 능력의 한계를 살펴보자.

읽기 헤드가 있을 수 있는 n 개의 가능 상태와 테이프에 쓸 수 있는 두 개의 가능한 기호들을 지니는 튜링 기계에 대해서, 정확하게 (4n + 4)²ⁿ 개의 서로 다른 프로그램들이 가능하다는 것은 간단한 풀이로 알 수 있다. 이는 n-상태 기계가 기껏해야 이만큼의 수들을 계산할 수 있다는 것을 의미한다. n 이 n = 1, 2, 3, .... 의 값들을 취한다고 하면, 우리는 튜링 기계들이 기껏해야 가산적인 수들의 집합 - 즉 그 원소들이 양의 정수들의 어떤 한 부분집합과 일 대 일 대응될 수 있는 집합 - 을 계산할 수 있다고 결론내린다. 반면에 실수들은 비가산적으로 많다. 따라서 우리는 대부분의 실수들이 계산 가능하지 않다는 꽤 놀라운 결과에 이르게 된다.

이러한 셈 논변은 어느 정도 간접적인 것임에도 계산 불가능한 수들이 있다는 것을 보여주는 한 가지 방법이다. 튜링은 칸토르의 대각선 논변이라고 알려진 것에 토대를 둔 더 직접적인 절차를 사용했다. 이것은 다음과 같이 전개된다. 다음과 같은 이름들의 나열을 고려해 보자 : Smith, Otway, Arquette, Bethel, Bellman, Imhoff. 이제 첫 번째 이름의 첫 번째 문자를 취하고서 알파벳순으로 그 문자 다음에 나오는 문자를 취하라. 그러면 T 가 나온다. 그 다음에 두 번째 이름의 두 번째 문자에 대해서 똑 같은 조작을 하라. 그러면 u 가 나온다. 마찬가지로 세 번째 이름의 세 번째 문자에 대해서, 또 나머지도 이와 같이 계속하라. 그러면 그 결과는 'Turing' 이다. Turing 이라는 이름이 원래의 목록에 나올 수 없다는 것은 틀림없다. 왜냐하면 그 이름은 그 목록의 각각의 이름과 최소한 하나의 문자에서 다르기 때문이다.

계산 불가능한 수가 있다는 것을 보이는 튜링의 논변도 이와 같은 추론방식을 따르고 있다. 모든 계산 가능한 수들을 열거한다고 가정하자. 또한 이 수들은 소수 전개에 의해 씌어졌다고 가정하자 (그러한 목록은 무한하게 길 것이지만 말이다). 이제 우리는 첫 번째 수의 첫 번째 자리수, 두 번째 수의 두 번째 자릿수, 그리고 일반적으로, k 번째 수의 k 번째 자릿수를 거기에 1 을 더한 수로 바꾼다 (만일 그 자릿수가 9 라면 0 으로 바꾸어야 한다 = 역주). 이러한 방식으로 우리는 어떤 새로운 수를 만들어낸다. 이 수는 원래의 목록에 있을 수 없다. 왜냐하면 이 수는 그 목록에 나오는 모든 수와 각각 최소한 하나의 자릿수가 다르기 때문이다. 그런데 정의에 의해 그 목록은 모든 계산 가능한 수들을 포함한다. 따라서 이 새로운 수는 계산 불가능해야만 한다.

앞에서 제시된 논변에서, 우리는 계산 불가능한 수들이 산술이라는 큰 새장에 있는 희한한 것이 아니라는 것을 알게 된다. 이와는 정반대로 사실상 규칙이기보다는 예외인 것이 계산 가능한 수들이다. 이 놀라운 사실은 우리가 개인적이고 전문적인 일상생활에서 다루는 모든 수들이 - 이것들은 본성상 계산 가능해야 하는데 - 가능한 모든 수들의 집합의 아주 작은 부분집합에 지나지 않는다는 것을 보여준다. 엄청나게 많은 수가 어떤 계산기계의 규칙을 따를지라도 도달할 수 없는 그런 영역에 놓여 있다. 그러면 이제 계산 불가능한 특정한 수에 대한 재미있는 예를 하나 살펴보기로 하자.

3. 바쁜 해리 놀이

당신에게 전부 0 으로 채운 입력 테이프가 주어진다고 가정하자. 목표는 첫째, 프로그램이 궁극적으로 멈추고 둘째, 프로그램이 멈추기 전에 테이프에 가능한 한 많은 1 을 인쇄하는 그러한 n-상태 튜링 기계에 대한 프로그램을 작성하는 것이다. 명백하게도, 인쇄될 수 있는 1 들의 수는 그 기계에서 이용 가능한 상태들의 수 n 의 함수다. 만일 n = 1 이라면, 인쇄될 수 있는 1 들의 최대 수가 1 이라는 점은 마찬가지로 분명하다. 이는 그 프로그램이 영원히 작동될 수 없다는 조건에서 따라나오는 결과다. 만일 n = 2 라면, 그 기계가 멈추기 전에 인쇄할 수 있는 1 들의 최대 수가 4 라는 것을 증명할 수 있다. 멈추기 전에 최대 수의 1 들을 인쇄하는 프로그램을 n-상태 바쁜 해리라고 한다. 표 3 에서는 3-상태 바쁜 해리에 대한 프로그램이 제시되었으며, 그림 2 는 어떻게 이 프로그램이 멈추기 전에 여섯 개의 1 들을 테이프에 인쇄할 수 있는지를 보여준다 (주의 : 테이프 검사 헤드의 위치는 그림에서 굵은 글씨로 표시되어 있다).

표 2  3-상태 바쁜 해리

그림 2  3-상태 바쁜 해리의 작동

이제 계산 불가능한 수에 대해 살펴보자. BB(n) 을 n-상태 바쁜 해리 프로그램이 쓴 1 들의 수라고 정의하자. 따라서 바쁜 해리 함수 BB(n) 은 멈추는 어떤 프로그램이 n-상태 튜링 기계의 테이프에 쓸 수 있는 1 들의 큰 개수다. 우리는 이미 BB(1) = 1, BB(2) = 4, 그리고 BB(3) = 6 이라는 것을 보았다. n 의 작은 값들에 대한 이러한 결과들로부터, 당신은 함수 BB(n) 은 n 이 점점 더 커짐에 따라 특별히 흥미로운 어떤 속성들도 지니지 않으리라고 생각할지도 모른다. 그러나 어떤 책을 표지나 제목으로 판단할 수 없는 것과 마찬가지로, 당신은 독립변수의 몇몇 값들에 대해 함수값이 주어질 때 그것만으로는 그 함수를 판단 내릴 수 없다. 사실상 상세하게 검토하면 다음을 알 수 있다.

여기에서 수 4096 은 줄임표가 있는 곳에서 166 번 나온다! 따라서 12-상태 튜링 기계에 대한 바쁜 해리 함수의 값을 계산하면서 우리는 그야말로 엄청나게 큰 수에 재빨리 도달하게 되는 것이다. 충분히 큰 n 의 값에 대해서, BB(n) 의 값은 독립변수의 값이 n 인 그 어떤 계산 가능한 함수의 값보다도 크다는 것이 판명된다. 달리 말하면 바쁜 해리 함수 BB(n) 은 계산 불가능하다. 이제 효과적으로 계산 불가능한 수의 구체적인 예를 들기 위해 어떤 큰 수  n 의 상태들을 지니는 튜링 기계를 취해보라. 그 다음에 n 의 값에 대한 바쁜 해리 함수의 값을 물어보라. 계산 불가능한 수라는 것이 결국 그 대답이다. 이제 어떤 것이 존재한다는 것과 그것을 계산할 수 있다는 것 간의 차이를 살펴보기 위해 다른 놀이를 살펴보자.

4. 튜링 기계 게임

놀이 참여자가 두 사람이라 하고 각각 A 와 B 라고 하자. 이 참여자들은 번갈아가면서 다음과 같이 양의 정수들을 선택한다.

단계 1 : 참여자 A 는 어떤 수 n 을 선택한다.

단계 2 : n 을 알고서, 참여자 B 는 어떤 수 m 을 선택한다.

단계 3 : m 을 알고서, 참여자 A 는 어떤 수 k 를 선택한다.

참여자 A 는 만일 모두 0 만 있는 테이프에서 출발할 때 정확하게 m + k 단계에서 멈추는 n-상태 튜링 기게가 있다면 이긴다. 그렇지 않으면 B 가 이긴다. 이것이 유한한 시간 동안만 지속되는 놀이라는 점은 아주 분명하다. 일단 참여자들이 그들의 정수들을 선택했다면, 우리에게 필요한 모든 것은 n 상태를 지니는 (4n + 4)²ⁿ 개의 튜링 기계들을 열거한 후 승자를 결정하기 위해 정확하게 m + k 개의 단계에 대해 각각의 튜링 기계를 작동하는 것이다.

고정된 유한한 시간 동안 지속되는 게임이 모두 결정된다는 것 - 이때 '결정된다' 는 것은 참여자 중 한 사람에게 이기는 전략이 존재한다는 뜻이다 - 은 게임 이론으로부터 잘 알려진 사실이다. 이 놀이의 경우에 이기는 전략이 존재하는 사람은 B 이다. 그럼에도 튜링 기계 게임은 결코 사소한 놀이가 아니다. 왜냐하면 어느 쪽 참여자도 그 게임을 이기기 위한 알고리듬 (계산 가능한 전략) 이 없기 때문이다. 이 사실을 증명하기 위해서는 바쁜 해리 함수의 값들보다도 더 빨리 커지는 값들을 지니는 어떤 함수를 계산하는 일이 그 어떤 이기는 전략에도 포함된다는 점을 보여주어야 한다. 그런데 우리는 BB(n) 이 계산 불가능하다는 것을 이미 알고 있다. 따라서 새로운 함수 또한 계산 불가능해야만 한다. 이 증명에 대해 더 상세한 내용을 알고 싶으면 참고문헌을 참조하기 바란다.

5. 멈춤문제

계산 가능성에 대한 우리의 정의와 위의 바쁜 해리의 예에서, 계산 절차가 종료될 때까지는 어떤 것도 완전히 계산된 것이 아니라는 점은 분명하다. 이 점은 실수에 대해서도 마찬가지인데, 여기에서는 어떤 유한한 계산을 통해서도 일반적으로 우리가 계산하려고 하는 수의 어떤 근사치만 산출될 뿐이다. 이렇듯 단순한 고찰만으로도 우리는 계산이론에서 핵심적인 다음의 물음에 도달한다. 유한한 수의 단계 후에 특정한 프로그램이 멈출 것이라고 우리에게 미리 말해줄 수 있는 어떤 일반적인 절차 (알고리듬) 가 있는가? 달리 말하면, 어떤 주어진 튜링 기계 프로그램 P 와 입력 자료들의 집합 I 에 대해서, P 와 I 를 받아들인 다음에 자료 I 를 처리할 때 P 가 유한한 수의 단계 후에 멈출 것인지의 여부를 우리에게 말해줄 수 있는 어떤 단일한 프로그램이 있는가? 이때 우리가 문제삼는 것이 모든 경우에 작동할 어떤 단일한 프로그램이라는 것을 주목하라. 바로 이것이 그 유명한 멈춤문제다.

그 문제가 결코 사소하지 않다는 것을 보기 위해서, 튜링 기계 테이프를 읽어 나가면서 최초의 1 에 도달할 때 멈추는 프로그램 P 가 우리에게 주어진다고 가정하자. 요컨대 그 프로그램은 다음과 같이 말한다. "계속해서 읽다가 1 에 도달하면 멈춰라." 이 경우 입력자료들이 전부 1 로만 이루어졌다면 그 프로그램은 첫 번째 단계 후에 멈출 것이다. 반면 만일 입력자료들이 모두 0 이라면, 그 프로그램은 결코 멈추지 않을 것이다. 물론 이러한 상황에서는 입력 테이프를 처리할 때 그 프로그램이 멈출 것인지 여부를 결정하는 명확한 절차가 우리에게 주어진다. 즉 입력 테이프가 1 을 하나라도 포함하고 있다면 그 프로그램은 멈출 것이고, 그렇지 않다면 그 프로그램은 영원히 작동할 것이다. 여기에서 우리는 이렇듯 매우 기본적인 프로그램에 의해 처리되는 모든 자료집합에 적용할 수 있는 멈춤 규칙의 한 예를 확인하고 있다.

불행하게도 실제 컴퓨터 프로그램은 대부분 위의 예보다 엄청나게 더 복잡하다. 그래서 그 프로그램이 작업해 나갈 때 어떤 값을 계산할 것인지는 프로그램에 대한 단순한 검사로는 결코 분명하지 않다. 사실상 만일 우리가 그 프로그램이 각 단계에서 무엇을 계산할 것인지를 알고 있다면 우리는 그 프로그램을 가동할 필요가 없을 것이다. 더구나 실제 프로그램에 대한 멈춤 규칙은 대개 "만일 이런저건 조건을 만족하는 그러그러한 값이 나오면 멈춰라. 그렇지 않으면 계속해서 계산하라" 와 같이 말하는, 앞에서 제시된 것과 종류가 같은 암묵적인 규칙이다. 멈춤문제에서 핵심적인 것은 프로그램의 멈춤 조건이 만족될 것이냐의 여부를 미리 말해주기 위해 그 프로그램과 입력자료들에 적용될 수 있는 어떤 효과적인 절차가 존재하느냐 하는 물음이다. 1936 년에 튜링은 이 문제를 일거에 부정적으로 해결했다. 즉 주어진 프로그램 P 와 입력자료 집합 I 에 대해서, P 가 입력 I 를 처리하는 것을 끝낼지의 여부를 말해주는 어떤 일반적인 방법도 없다는 것이다.

튜링 기계라는 개념은 결국 계산이라는 생각을 견고한 수학적 토대 위에 올려놓았으며, 우리로 하여금 효과적 절차라는 모호하고 직관적인 생각에서 알고리듬이라는 정확하고 수학적으로 잘 정의된 개념으로 나아가게 했다. 사실상 튜링의 연구는 미국의 논리학자 처치의 연구와 함께 이른바 튜링-처치 논제의 기초를 이룬다.

튜링-처치 논제 (The Turing-Church Thesis) 의 핵심적인 내용은 계산될 수 있는 수가 어떤 것이든 어떤 적절한 튜링 기계에 의해 계산될 수 있다는 주장이다. 이 주장을 정리라고 하지 않고 논제라고 하는 까닭은 그 주장이 실제로 증명을 허용하는 것이 아니기 때문이다. 오히려 그것은 본성상 정의이며, 또는 계산하기라는 우리의 비형식적 개념과 튜링 기계라는 형식적 개념을 동일시해야 한다는 제안이다.

이 점을 더 분명하게 파악하기 위해서, 튜링 기계와 타자기 간의 유비를 끌어들여보자. 타자기 또한 기본적인 장치이며, 이것으로 우리는 크기가 무한한 종이 위에 기호들의 열을 인쇄할 수 있다. 또한 타자기는 그것이 있을 수 있는 유한한 수의 상태들만을 지닌다. 즉 대문자, 소문자, 빨간 잉크 리본 또는 검은 잉크 리본, 서로 다른 기호들 등등이 그것이다. 이러한 한계가 있음에도 모든 타자기는 『캔터베리 이야기 (The Canterbury Tale)』『이상한 나라의 앨리스 (Alice in Wonderland』 나 여타 기호들의 열을 타이프하는 데 이용될 수 있다. 물론 그 기계가 무엇을 할지를 말해주는 데에는 초서 (Chaucer) 나 루이스 캐롤이 필요할 수도 있다. 그러나 없어도 된다. 이와 비슷하게, 어려운 계산문제를 어떻게 해결할지를 튜링 기계에게 말해줄 아주 숙련된 프로그래머가 필요할지도 모른다. 그러나 튜링-처치 논제는 어떤 계산을 수행함으로서 해결 가능한 모든 유형의 문제를 해결하는 데에는 그 기본 모델 - 튜링 기계 - 로 충분하다고 말한다.

아마도 명민한 독자라면 계산을 수행하면서 튜링 기계가 취하는 작동과, 전제에서 결론으로 나아가는 연역 논변을 만들 때 우리가 따르는 단계들 간에 놀라운 유사성이 있다는 점은 알아차렸을 것이다. 튜링은 형식적 논리체계와 튜링 기계 간의 동등성을 보여주었다. 간단히 말해 무제한적인 기억용량이 있는 디지털 컴퓨터 C 에 대해서, 우리는 C 의 가능한 출력들이 F 의 가능한 정리들과 일치하고 또는 역으로도 그렇게 일치하는 형식체계 F 를 발견할 수 있다. 이러한 동등성을 사용해서 튜링은 컴퓨터 - 이론 용어로 서술된 결정문제를 앞에서 살펴본 멈춤문제로 재진술했다. 그리고 두 개의 무제들이 논리적으로 동등하기 때문에, 멈춤문제가 해결될 수 없다는 사실은 결정문제 또한 해결 불가능하다는 것을 함축한다. 그렇게 되면 우리는 다시 일련의 규칙을 따름으로써 사물의 핵심에 나아가려는 시도에서 단단한 장벽과 마주친다. 이 점을 더 확실하게 역설하기 위해 튜링의 멈춤 정리와 괴델의 불완전성 정리를 146 쪽에 제시했는데, 이를 통해 우리는 두 결과가 동등하다는 것을 분명하게 확인할 수 있다.

1930 년대 후반에 튜링이 선구적인 연구를 했음에도, 진리의 실제세계 개념과 증명의 형식체계 개념 사이에는 어떤 유의미한 차이도 존재하지 않는다는 생각에 최후의 일격을 가한 것은 실제로 몇 년 앞선 괴델의 저작이었다. 이제 괴델이 무엇을 했는지, 그리고 규칙을 따름으로써 세계를 이해하려는 희망에 대해 그것이 무엇을 의미하는지를 논의해보기로 하자.

6. 진리는 증명보다 더 이상한 것이다

수학자이자 과학 이야기 작가인 루디 러커 (Rudy Rucker) 는 『무한과 마음 (Infinity and the Mind)』이라는 책에서 로마에 있는 한 교회를 방문한 일을 이야기했는데, 그 교회 밖에는 거대한 돌 원반이 세워져 있다고 한다. 이 원반에는 텁수룩하게 수염을 기른 사람의 얼굴이 조각되어 있는데, 그의 좁고 긴 입은 허리 높이에 있다. 전설에 따르면, 신이 말씀하시기를, 누구든지 한 손을 그 입에 집어 넣고 거짓말을 하는 자는 다시는 그 손을 빼낼 수 없을 것이라고 했다. 러커는 교회에 가서 자기 손을 그 입에 집어 넣고 다음과 같이 말했다. "나는 나의 손을 다시는 빼낼 수 없을 것이다." 말할 것도 없이 러커는 사지가 멀쩡한 채 로마를 떠났다. 이 이야기에는 가능한 모든 실제세계의 진리들을 산출할 수 있는 '보편 진리 기계' 를 만들어내는 일이 불가능할 수밖에 없는 논리적인 근거가 잘 나타나 있다.

그러한 보편 진리 기계, 즉 UTM 이 실제로 존재한다고 가정하자 [우리는 이 가정적인 기계장치에 대한 약자 UTM 을 보편 튜링 기계에 대한 약자 (UTM) 와 동일하게 사용했는데, 그 까닭은 나중에 밝혀질 것이다]. 이제 다음의 진술 S 를 그 기계에 집어넣는다고 하자 : "UTM 은 결코 이 진술을 인쇄하지 않을 것이다." 만일 UTM 이 S 를 인쇄한다면 S 는 거짓이 될 것이고, 따라서 UTM 은 거짓 진술을 인쇄해낸 셈이다. 그런데 이는 불가능하다. 왜냐하면 가정에 따르면 UTM 은 오직 참 진술만을 인쇄하기로 되어 있기 때문이다. 그러므로 UTM 은 결코 S 를 인쇄하지 않을 것이며, 이는 S 가 사실상 참 진술이라는 것을 함축한다. 그러나 UTM 이 결코 인쇄하지 않을 어떤 참 진술이 있다면, 이는 그 기계가 보편적이라는 사실 (즉 그것이 모든 참 진술을 인쇄할 것이라는 사실) 과 모순된다. 명민한 독자라면 자기 지시 문장 S 가 이 책의 제 2 장에서 논의된 그 유명한 에피메니데스 역설의 또 다른 형태라는 것을 알아차렸을 것이다.

앞의 논변의 핵심적인 귀결은 진리는 유한하게 기술 가능하지 않다는 것이다. 가능한 모든 실제세계의 진리들을 산출하는 데 충분한 어떤 규칙들의 집합도 존재하지 않는다는 것은 아주 놀라운 일이 아닐 것이다. 결국 규칙들 자체는 그것들이 기술하려는 세계 내에 있으며, 따라서 무한한 모든 가능한 실제세계 진리들을 산출하게 할 유한한 규칙들의 집합을 요구하는 것은 당신의 구두끈을 잡아당김으로써 당신 자신을 들어올리려는 것과 같을 것이다. 그렇지만 놀라운 것은 바로 이 한계가 훨씬 더 작고 훨씬 덜 무질서한 정수들의 세계에서도 성립한다는 것을 괴델이 증명했다는 사실이다.

처음 언뜻 보면 괴델의 결과가 지니는 이러한 함축은 '생각하는 기계' 라는 생각에 조종을 울린 것처럼 보인다. 결국 만일 인간의 정신이 알 수는 있지만 계산기게에 의해 접근할 수 없는 진리들이 존재한다면, 우리는 어떻게 인간의 인지적 절차들을 복제할 수 있는 기계 '지능' 을 만들어내는 일을 바랄 수 있단 말인가? 그러나 문제는 보기와는 달리 결코 단순하지 않다. 다음 장에서 우리는 그 이유를 살펴볼 것이다.