수학자, 컴퓨터를 만들다

지은이 / 마틴 데이비스 | 옮긴이 / 박정일, 장영태

수학자, 컴퓨터를 만들다
지은이 : 마틴 데이비스
옮긴이 : 박정일, 장영태
펴낸곳 : 도서출판 지식의 풍경(서울시 마포구 서교동 404-29 모노빌딩 3층)

서문

들어가며
01 라이프니츠의 꿈
대수의 “비밀스런 부분”은 “기호 체계로 이루어져 있습니다. 말하자면 ”기호적 표현을 알맞게 사용하는 기술로 이루어져 있는 것입니다.“ [28p]

라이프니츠는 일반 대수에서 수를 다루는 규칙을 서술하는 방식과 같은 방식으로 논리적 개념을 다루는 규칙을 서술하게 될 대수학, 즉 논리 대수를 제시했다. 그는 임의의 다수 항들의 결합을 나타내는 특별한 새 기호 ⊕를 도입했다. 두 개의 묶음을 한 개의 묶음으로 결합하되, 두 개의 묶음 각각에 있는 모든 항을 포함하는 한 개의 묶음으로 결합하자는 발상이다. 덧셈 부호가 있어서 우리는 이 연산을 일반 덧셈과 같은 것으로 생각하기 쉽지만, -중략- 똑같은 묶음들끼리의 결합을 아무리 되풀이해도 그 똑같은 묶음만 만들어 낼 뿐이다. 물론 수의 덧셈은 아주 다르다. 2+2=4이지 2가 아니듯이. [31~33p]

02 불이 논리를 대수로 표현하다

훗날, 그는 이 시절을 회고하면서, 책을 사는 데 아주 적은 용돈만 쓸 수 있었는데, 수학책이 다른 주제의 책들보다 공부하는 데 더 오랜 시간이 들기 때문에 가장 쓸모 있다는 것을 알게 됐다고 설명했다. [38p]

불은 “살아 있다”, “하마”, 또는 “사람”과 같은 낱말들에 대한 논리적 추론에서 중요한 것은, 문제의 낱말에 의해 서술되는 개체들 모두의 집합 또는 모임, 즉 살아 있는 것들의 집합, 하마들의 집합, 사람들의 집합이라는 점을 깨닫게 되었다. 게다가 그는, 그런 집합들의 대수식에 따라 이런 종류의 추론을 표현할 수 있는 방법을 알게 되었다. 불은 지금까지 숫자나 연산자를 나타내는 데 문자들을 사용해 온 것과 마찬가지로 집합을 나타내는 데 문자를 사용했다. 문자 x와 y가 두 개의 특정한 집합을 나타내는 경우, 불은 x와 y 모두에 속하는 것들의 집합을 xy라고 썼다. [43~44p]

불은 집합에 적용되는 이런 연산이 숫자에 적용되는 곱셉 연산과 어떤 면에서는 같다고 생각했다. 그렇지만, 그는 결정적인 차이를 알아차렸다. 만약 다시 y가 양들의 집합이라면, yy는 무엇일까? 그것은 양과 또……양인 것들의 집합이 분명하다. 그러나 이것은 바로 양들의 집합과 똑같은 것이다. 따라서 yy=y이다. 불이 자신의 전체 논리체계를, x가 하나의 집합을 나타낼 때 식 xx=x는 항상 참이라는 사실에 바탕을 두고 있다고 지적하는 것은 소박한 과장일 뿐이다. [44p]
xy를 x와 y의 교집합이라고 부른다. 우리는 또 x가 한 집합을 대표할 때 식 xx=x는 항상 참이라는 것을 알고 있다. 이것은 불에게 의문을 불러일으켰다. 일반 대수에서, x가 하나의 수를 대표한다면, 식 xx=x가 참일 때는 언제인가? 답은 간단하다. 즉 x가 0 또는 1이고 그 밖의 수가 아닐 때 그 식은 참이다. 이를 통해, 불은 만약 그 값을 0과 1 두 개의 값으로 제한한다면 논리 대수는 일반 대수의 연산과 정확히 일치한다는 원리를 알게 되었다. 그렇지만 이것을 이해하기 위해서는 기호 0과 1을 집합으로 재해석하는 것이 필요했다. 실마리는 일반적인 곱셈 규칙과 관련한, 0과 1의 각각의 속성에서 찾을 수 있다. 0에 어떤 수를 곱해도 0이다. 또, 1에 어떤 수를 곱해도 바로 그 수이다. 기호로 나타내면 다음과 같다. 0*X=0, 1X=X
이제 집합들에 대하여, 0을 아무것도 속하지 않는 집합이라고 해석하면, 0x는 모든 x에 대하여 0과 일치할 것이며, 현대 전문 용어로 0은 공집합이다. 마찬가지로, 1이 고려할 수 있는 모든 대상을 포함한다면, 또는 말하자면 1이 전체 집합이면, 1x는 모든 x에 대하여 x와 일치한다.
일반 대수는 곱셉뿐만 아니라 덧셈과 뺄셈도 다룬다. 그러므로, 만약 불이 특별한 규칙 xx=x로 마치 일반 대수와 같은 논리 대수를 보여 주고자 했다면, +와 –에 대한 해석도 제시해야만 했다. 따라서 x와 y가 두 개의 집합을 나타낼 때, 불은 x에 있거나 y에 있는 모든 것들의 집합, 오늘날 x와 y의 합집합이라고 부르는 집합을 나타내는데 x+y를 취했다. 그러므로 불이 제시한 보기를 들자면, 만약 x가 남자들의 집합이고 y가 여자들의 집합이면, x+y는 모든 남자들과 여자들로 이루어진 집합이다. 또한 불은 x에는 속하지만 y에는 속하지 않는 것들의 집합을 x-y라고 썼다. 만약 x가 모든 사람들의 집합을 나타내고 y가 모든 아이들의 집합을 나타내면, x-y는 성인들의 집합을 나타낼 것이다. 특별히, 1-x는 x에 속하지 않는 것들의 집합이 될 것이므로, 다음과 같은 결론이 나온다.
x+(1-x) = 1
[50~51p]

일반 대수 표기를 사용해서, xx를 x의 2승이라고 쓰자. 그러면 불의 기본 규칙에 따라 x의 2승은 = x 또는 x의 2승 – x = 0 이라고 쓸 수 있다. 이 식은 다음과 같인 일반적인 대수 규칙으로 인수 분해된다.
x(1-x) = 0
정리하면, 어떤 것도 주어진 집합 x에 속하면서 동시에 속하지 않을 수는 없다. 불에게 이것은 흥미로운 결과였고, 자신이 제대로 해 나가고 있다는 확신이 들게 해 주었다. [51~52p]

타당한 추론에서는 어떤 경우든, 결론이라고 부르는 문장들이 참이라는 것은, 전제라고 부르는 다른 문장들이 참이라는 것에서 추론된다.
불은 집합에 쓰이는 대수가 또한 이런 종류의 추론에 쓰이는 대수와 똑같다는 것을 알게 되었다. 그는 명제 X가 참임을 뜻하기 위해 X=1과 같은 식을 사용했다. 마찬가지로 X가 거짓임을 뜻하기 위해 식 X=0을 사용했다. 그러면, “X가 아니다”는 식 X=0ㅇ라고 적을 수 있었다. 또한 “X&Y“는 식 XY=1이라고 적었다. 이렇게 쓸 수 있는 것은 X와 Y가 모두 참일 때만 ”X&Y“가 참이기 때문이다. 한편, 대수적으로는, X=Y=1이면 XY=1이지만, X=0이거나 Y=0이면(또는 둘 다 0이면) XY=0이 된다.
최종적으로, 문장 ”X이면 Y이다“는 아래 식으로 나타낼 수 있다.
X(1-Y) = 0
[56p]

03 프레게, 환희에서 절망으로

불이 다른 명제들 간의 관계들을 표현하는 명제를 2차 명제라고 생각한 반면에, 프레게는 명제들을 연결하는 그와 같은 관계들이 또한 개별 명제들의 구조를 해석하는 데 사용될 수 있다고 보았고, 이 관계들을 자신의 논리학 기초로 삼았다. [72p]

모든x에 대하여는 , 만일 x가 말이면, x는 포유동물이다 라고 표현할 수 있고,
어떤x가 존재한다는, x는 말이고 x는 순종이다.로 표현할 수 있다. [74p]

모든 사람은 어떤 사람을 사랑한다.
어떤 사람은 모든 사람을 사랑한다.
모든 사람은 어떤 사람한테 사랑받는다.
어떤 사람은 모든 사람한테 사랑받는다. [78p]

프레게의 논리학에 있는 몇몇 전제들로 시작하면, 원하는 결론에 도달하기 위한 시도에 프레게의 규칙이 적용될 수 있을 것이다. 그러나 만약 시도가 실패한 경우, 이것이 지적 노력과 끈기를 충분히 쏟아붓지 않아서인지 아니면 단순히 원하는 결론이 주어진 전제들에서 따라 나오지 않아서인지 알 수 있는 아무런 수단도 프레게는 제공하지 못했다. [80~81p]

예를 들어, 수 3은 논리학의 일부로 설명될 수 있다. 어떻게 이런 일이 가능할까? 하나의 자연수는 어떤 집합의 한 속성이며, 다시 말해 그 원소들의 개수이다. 수 3은 다음의 것 모두가 공통으로 가지고 있는 것이다. 즉, 성 삼위일체, 트로이카를 끄는 말들의 집합, (정상적인) 클로버 잎에 달린 잎들의 집합, 문자들의 집합 {a, b, c}. 수 3에 대해 어떤 것도 말하지 않더라도, 누구나 이 집합들 중 어떤 두 개의 집합을 골라도 같은 수의 원소들을 가지고 있다는 것을 알 수 있다. 우리는 그것들을 간단히 대응시킬 수 있다 프레게의 생각은 수 3을 이런 모든 집합들의 모임과 동일화하는 것이었다. 즉 수 3은 바로 원소가 세 개인 모든 집합들의 집합이라는 것이다. 일반적으로, 주어진 집합에 있는 원소들의 수는 주어진 집합과 일대일 대응 될 수 있는 모든 집합들의 모임이라고 정의될 수 있다. [82p]

04 칸토어, 무한대를 통과하다
무한급수에서는, 더 많은 항을 더할수록 점점 가깝게 다가가는 극한값을 확인하게 된다. 이를 급수가 극한값에 수렴한다고 말한다. 여기서는 완결된 무한이 문제 될 여지가 없다. 그 과정의 어느 단계에서도 유한하게 많은 항들이 더해질 뿐이다. [94p]

우리는 그의 추론을 다음과 같이 설명할 수 있다. 즉, 우리는 그 수가 얼마인지는 알지 못하더라도, 어느 한 집합의 원소를 일대일 대응 방식으로 다른 집합의 원소에 대응시킴으로써 두 집합이 똑같은 수의 원소를 가진다고 말할 수 있다. 예를 들어, 어떤 사람이 강당 안에 빈자리도 없고 서 있는 사람도 없는 것을 본다면, (세지 않고도) 강당의 사람들의 수와 좌석 수가 같다고 – 각 좌석과 그 좌석에 앉아 있는 사람들을 대응시키면 되니까 – 결론 내릴 수 있다. 라이프니츠는 만약 무한수 같은 것들이 존재한다면, 위와 똑같은 생각이 그 무한수들에 적용되어야만 한다고 여겼다. 즉, 일대일 대응이 두 무한 집합 사이에 정의될 수 있다면, 두 집합은 같은 수의 원소를 가진다고 결론 내릴 수 있어야 하는 것이다. [94~94p]

분수로 나타낼 수 잇는 수를 유리수라고 부른다. 만약 유리수를 소수로 나타내면, 결국 숫자의 패턴은 반복하기 시작한다. -중략- 소수로 나타낼 수 있는 수는, 결과적으로 반복되거나 말거나 상관없이, 실수라고 부른다. 소수로 표시된 부분이 절대 반복되지 않는 수들을 무리수라고 부른다. [98p]

실수 집합은 자연수 집합과 일대일 방식으로 대응될 수 없고, 무한 집합은 적어도 두 가지 크기를 가진다는 주목할 만한 사실을 데데킨트에게 증명할 수 있었다. -중략- 칸토어는 증명에서 대수적 수는 자연수와 일대일 대응 될 수 있고 실수는 그렇게 대응될 수 없으므로, 실수 집합은 대수적 수의 집합과 다르다고 썼다. 따라서 대수적인 수가 아닌 실수, 그리하여 초월수인 실수가 존재해야만 한다. [99~100p]

기수는 어떤 집합 안에 얼마나 많은 것들이 있는지 알려 줄 때 쓰이며, 서수는 그것들이 특정한 질서 안에서 어떻게 배열되었는지 알려 줄 때 쓰인다. [101p]

순서매김은 어떤 유한 집합에서도 참이다. 즉, 원소의 순서를 매기는 서로 다른 방식들 모두가 똑같은 기본 패턴을 보여 준다. 만약 그 집합이 n개의 원소로 이루어져 있다면, 첫 번째 항, 두 번째 항, …… 그리고 마지막으로 n번째 항이라는 순서 매김으로 나타날 것이다. 칸토어는 무한 집합일 때는 상황이 완전히 다르다고 보았다. 무한 집합은 매우 다른 패턴을 가진 다른 방식으로 순서 매겨질 수 있다. 예를 들어, 자연수 1, 2, 3, …이 모든 짝수가 모든 홀수의 앞에 나오도록 배열된다고 가정하자. 나열된 각 항의 순서를 나타내기 위해 서수를 사용하려고 한다면, 낯익은 유한한 서수는 모조리 짝수를 맡는 데 쓰인다는 것을 알게된다. 칸토어는 이 어려움을 해결하기 위해 초한 서수 사용법을 알아냈다. 그리하여 모든 유한 서수 다음에, 칸토어는 그리스 문자 ω 다음에 ω+1, ω+2, ... 등등이 이어진다. [106p]
대각선 방법은 이름표를 붙였던 모든 집합들과 다른, 어떤 새로운 집합을 얻는 데에 쓰일 수 있다. [110p]

바꾸어 말하면, 1이 M1에 속하지 않는 경우에만 1은 M에 속한다. 또 2가 M2에 속하지 않는 경우에만 2는 M에 속하며, 나머지도 마찬가지이다. 그러므로 M은 M1과 다르고, M2와 다르며, 또 이와 같이 여타의 것과 다른 자연수의 집합이 된다. 여기서 M1, M2, M3...는 수 1, 2, 3... 과 자연수로 이루어진 집합들 사이의 가능한 모든 일대일 대응을 나타내므로, 그와 같은 어떤 대응도 자연수들의 모든 집합들을 포함할 수 없다는 것을 알게 된다. 바꾸어 말하면, 모든 자연수 집합들의 집합의 기수는 N(이상한 그 수학기호)0보다 크다. 실제로, 이 기수가 바로 C, 즉 실수의 집합의 기수임을 증명하는 것은 가능하다. 그러므로 대각선 방법은 실수가 자연수보다 더 많이 있다는 것을 알 수 있는 또 다른 방식을 제공한다. [111~112p]

그때 버트런드 러셀이 등장하여 가장 충격적인 일격을 날렸다. 그는 ‘모든 집합들의 집합이 있을 수 있는가?’ 하는 의문을 품었다. 만약 그런 집합이 있다면, 대각선 방법을 적용할 때 무슨 일이 일어나겠는가? 다시 말해, 임의의 집합들을 꾸린 다음 그 꾸러미들에 이름표를 붙이기 위해 그 임의의 집합들을 꾸린 다음 그 꾸러미들에 이름표를 붙이기 위해 그 임의의 집합들을 사용한다면 어떻게 될까? 물론, 이름표가 붙은 집합들과 전혀 다른 하나의 집합을 얻게 될 것이다. 버트런드 러셀이 자기 자신의 원소가 아닌 모든 집합들의 집합이라는 유명한 역설을 찾아낸 것은 이런 상황을 심사숙고하면서였다. 이것은 3장에서 논한, 러셀이 충격에 빠진 프레게에게 전했던 그 역설이었다. [113p]

05 구원에 나선 힐베르트

세상은 끊임없이 흘러가도, 어떤 것은 변하지 않는다. 수학자들은 종종 다른 것들이 변화할 때 변화하지 않고 그대로인 바로 그런 것을 찾는 일에 관심을 갖는다. 그런 경우에, 수학자들은 일정한 변환 아래에서 불변하는 것을 이야기한다. [123p]

그리하여 힐베르트가 한 일은, 훗날을 위해 산술의 무모순성 문제를 남겨 둔 채, 유클리드 기하학의 무모순성을 산술의 무모순성으로 환원한 것이었다! [128p]

“모든 확정된 수학적 문제는 반드시 정확한 해법으로 풀리기 마련”이라는 확신을 공유하고 있다고 선언했다. [129p]

크로네커가 수학적 실체의 존재를 증명하기 위해서는 문제가 되고 있는 항들을 구성하거나 나타내는 방법을 제공해야 한다고 주장한 반면, 힐베르트에게 존재란 그런 실체의 존재를 가정하는 것이 모순에 이르지 않을 것이라는 증명이 요구될 뿐이었다. [130p]

브로우웨르는 더 나아가 무한 집합을 다룰 때에는 논리학의 기본 법칙, 즉 아리스토텔레스의 (모든 명제는 참이거나 거짓이라고 단적으로 주장하는) 배중률을 사용해선 안 된다고 비난했다. 브로우웨르가 볼 때, 어떤 명제들은 참이라고도 거짓이라고도 말할 수 없다. 이 명제들은 그 명제들에 관해 어떤 식으로든 결정할 수 있는 그 어떤 방법도 현재 알려지지 않은 명제이다. [136p]

이 책에는 프레게의 《개념 표기법》의 기초 논리학, 즉 오늘날 1차 논리학이라고 부르는 것에 대한 두 가지 문제를 담고 있었다. 어떤 점에서는, 두 가지 모두 오랫동안 느끼고는 있었지만 다뤄지지 않은 문제였는데, 논리 체계들은 외부에서 볼 수 있다고 통찰한 사람이 바로 힐베르트였다. 논리 체계들이 표현되고 있는 확고한 형식을 바라볼 수 있게 하는 외부 말이다. 이러한 문제들 중 하나는 1차 논리학이 완전하다는 것을 증명하는 것인데, 이때 1차 논리학이 완전하다 함은 외부에서 볼 때 타당한 어떤 논리식도, 교과서에서 제시된 규칙들만 사용해서 체계 내부에서 도출될 수 있다는 뜻이다. 그 다음 문제는, 힐베르트의 결정문제라고 알려진 것으로서, 1차 논리학의 어떤 논리식이 주어졌을 때, 한정된 수의 명확하고 효과적인 단계들을 거치면서 그 논리식이 타당한지 아닌지를 결정할 방법을 제공하는 것이었다. [144~145p]

힐베르트의 유명한 1900년 목록에 있는 두 번째 문제는 실수들을 다루는 산술의 무모순성에 대한 증명을 요구하는 것이었다. 그 당시, 그러한 증명이 어떤 모습일지 누구도 짐작하지 못했고, 특히 어떻게 순환 논리의 오류를 피할 수 있을지, 즉 그 증명이 입증하고자 한 바로 그 방법들을 증명 과정에서 사용하는 것을 어떻게 피할 수 있을지 아무도 생각하지 못했다. 우리가 앞 장에서 보았듯이, 1920년대 동안 힐베르트는 메타수학 프로그램을 도입했다. 즉, 무모순이라고 증명될 공리들은 어떤 형식 논리 체계로 요약될 것이었다. 또 그 형식 논리 체계 안에서 증명은 단지 유한한 수의 기호들의 배열일 뿐이었다. 그렇다면, 이 체계 안에서 어떤 모순도 유도할 수 없다는 증명은 힐베르트가 유한 방법들이라고 부른 것을 사용하여 실행되어야 할 터인데, 그 방법들은 브로우웨르가 허용하려고 한 것보다 한 층 더 제한적인 방법들이었다. [162p]

06 괴델이 힐베르트 프로그램을 뒤엎어 버리다

그러면, 왜 메타수학은 스스로 형식 논리 체계 내부에서 전개될 수 없을까? 외부에서 보면, 이 체계들은 기호열 사이의 관계를 포함한다. 내부에서는, 이 체계들은 자연수를 포함하는 다양한 수학적 대상에 대한 명제를 표현할 수 있다. 게다가, 기호열들이 자연수로 부호화될 수 있는 방식을 생각하는 것도 오렵지 않다. 그렇다! 그런 부호들을 사용하여 외부를 내부로 가져올 수 있다. 그런 부호 사용을 보여주기 위하여, “사랑에 빠진 사람은 모두 행복하다”는 전제가 어떻게 기호화되는지 다시 살펴보자 –중략- 우리는 예를 들어 다음과 같이 각 기호를 10진 숫자 중 하나로 바꾸는 간단한 부호화 도식을 사용할 수 있다. 지시한 것처럼 기호들을 숫자로 바꾸면, 다음의 부호수를 얻게 된다.
846988579186079328699
기호열에서 그것을 부호화한 숫자로 나아가는 것이 쉽다는 것뿐만 아니라, 역방향으로 진행하는 것도 마찬가지로 쉽다는 것 또한 주목하라. 물론, 기호가 10개보다 더 많을 때는, 다른 부호화를 사용해야 하지만, 이것은 어렵지 않다. 예를 들어, 만약 한 쌍의 십진 숫자로 각 기호를 부호화한다면, 100개에 이르는 기호들을 바꿀 수 있다. 본질적으로 같은 방법들을 그 어떤 형식 논리 체계에도 적용할 수 있기 때문에 그러한 체계들의 다양한 표현들은 자연수를 통해 부호화될 수 있다. [164~165p]

괴델의 증명에서 결정적인 단계는 한 자연수가 PM 안에서 증명 가능한 어떤 한 명제의 부호라는 속성 자체가 PM 안에서 표현 가능하다는 것을 논증하는 것이었다. 이러한 사실을 이용하여 괴델은, 사용되고 있는 특정 부호들을 알고 있는 사람이 보면, PM 안에서 증명될 수 없는 어떤 명제가 있다는 주장을 표현하고 있음을 알 수 있는 PM 안의 명제들을 구성할 수 있었다. 말하자면, 괴델은 명제 A를 구성할 수 있었는데, 이 때 명제 A는, 부호화를 통해 읽으면, 어떤 명제 B가 PM 안에서 증명 가능하지 않다고 주장하는 명제이다. 그런데 부호화의 비밀을 모르는 사람이 A를 보게 되면, 자연수에 대한 복잡하고 수수께끼 같은 명제를 표현하는 기호열로 보일 것이다. 그러나 부호를 통하여 보면, 수수께끼가 사라진다. 즉 A는, 어떤 기호열 B가 PM 안에서 증명 가능하지 않은 어떤 한 명제를 나타낸다는 명제를 표현하고 있다. 대개 A와 B는 서로 다른 명제일 것이다. 괴델은 의문을 품었다. 두 명제가 같을 수 있을까? 실제로 그럴 수 있었고, 괴델은 게오르크 칸토어에게서 배운 수학적 수법, 바로 대각선 방법을 사용하여 이것을 논증할 수 있었다. 이 수법을 써서, ‘증명 불가능하다고 주장되어지는 명제’와 ‘그 주장을 하는 명제’가 동일한 것이 되게끔 사태가 정리될 수 있었다. 달리 말하면, 괴델은 우리가 U라고 부르게 될, 정말로 놀라운 명제를 얻는 방법을 보여 주었다. 그 명제의 특성은 다음과 같다.
·U는 PM 안에서 증명될 수 없는 어떤 특정한 명제가 있다고 말한다.
·그 특정한 명제는 바로 U 자신이다.
·그러므로, U는 다음과 같이 말한다. “U는 PM안에서 증명될 수 없다.”
[166~167p]

가장 기본적인 수준에서, 현대의 컴퓨터는 0과 1의 짧은 문자열을 통해 간단한 기초 연산만 수행할 수 있다. 이른바 고급 프로그래밍 언어의 설계자들은 프로그래머들이 다루고 싶어 하는 매우 복잡한 연산을 응축시킨 언어를 그들에게 제공하는 업무를 맡게 된다. 이런 언어를 사용하여 작성된 프로그램이 컴퓨터로 실행되기 위해서는 기계어로 – 프로그램을 실행하기 위해 필요한 기초 연산의 세부 목록으로- 번역되어야 한다. 이것은 이른바 인터프리터(interpreters) 또는 컴파일러(compilers)라고 부르는 특별한 번역 프로그램에 의해 수행된다.
결정 불가능한 명제의 존재에 대한 괴델의 증명의 핵심은 PM에서의 증명 가능성이 PM 자체에서 표현될 수 있다는 사실이다. [170p]

괴델의 불완전성 정리는, 만약 수학이 PM 같은 특정한 형식 체계로 요약될 수 있는 것으로 제한된다면 힐베르트의 믿음은 헛된 것임을 보여 준다. 주어진 어떠한 특정 형식 체계에 대해서도 그것을 뛰어넘게 될 수학적 문제들이 있다. 다른 한편, 원리적으로, 그러한 각각의 문제는 그 문제를 해결할 수 있게 하는 더 강력한 체계를 낳는다. 혹자는 더 약한 체계에서 결정 불가능한 문제들을 각각 결정 가능하게 하는 훨씬 더 강력한 체계들의 위계들을 상상한다. [175p]

결혼의 행복은 커다란 수수께끼이며, 더 나이 많고 좀 더 현명한 듯 보이는 사람들의 예언도 종종 틀리기 마련이다. 이것이 괴델 부부에 해당하는 경우로서, 두 사람은 오랫동안 행복한 결혼 생활을 누린 것으로 밝혀졌다. [177p]

괴델이 알아낸 자연수에 관한 결정 불가능한 문제는 문제 삼고 있는 형식 체계 내부에서는 결정 불가능했지만, 우리가 보아 왔듯이, 외부에서 봤을 때는 분명히 참이었다. 그러나 연속체 가설을 달랐다. 괴델의 연구는 그것이 참인지 거짓인지 가늠할 수 있는 아무런 단서도 제공하지 못했다. 이때까지 괴델은 편협한 기본 견해들에 방해받지 않으면서, 필요한 수학적 방법들을 무엇이든 사용하며 앞으로 나아갈 수 있었다. 그러나 이제 그는 얻어낸 결과들에서 멈추고 자신이 해 온 연구가 가지는 철학적 의미에 대해 생각해야만 했다. [185p]

만약 제한된 기계 장치가 인간 정신의 모든 힘을 흉내 낼 수 있다면, 괴델 자신의 불완전성 정리는 자연수에 대한 어떤 명제가 참이더라도 결코 인간의 힘으로 증명될 수 없음을, 즉 절대적으로 결정 불가능한 명제임을 보이는 데 이용될 수 있다. 이것은 분명히 힐베르트의 언명과 모순될 터였다. 그러나 괴델에 따르면, 인간이 파악할 수 있는 것을 넘어서는 속성을 지닌 자연수가 객관적으로 존재한다고 가정하는 진술을 이해할 수 있는 관념론적 철학의 어떤 수단이 또한 필요할 것이다. [190p]

07 튜링이 만능 컴퓨터를 상상하다

- 라이프니츠는 인간 이성을 계산으로 환원하는 것을, 그리고 계산을 실행할 강력한 기계 기관을 꿈꿨다. 프레게는 처음으로 인간의 모든 연역적 추론을 그럴듯하게 설명할 수 있는 규칙 체계를 마련했다. 괴델은 1930년에 쓴 박사 학위 논문에서 힐베르트가 2년 전에 낸 문제에 답하면서 프레게의 규칙이 완전하다고 증명했다. 힐베르트는 또한 1차 논리학이라고 불리게 되는 것의 기호법으로 씌어진 몇몇 전제들과 제시된 결론이 주어졌을 때 프레게의 규칙들이 그 결론이 전제들에서 유도되게끔 할 수 있는지를 언제나 결정할 수 있게 해 주는 명백한 계산 절차를 추구했다. 그런 절차들을 찾는 과제는 힐베르트의 Entscheidungsproblem(글자 그대로, “결정 문제”)이라고 알려지게 되었다. 물론, 특정 문제를 풀기 위한 계산 절차 체계는 새로운 것이 아니었다. 실제로 전통적인 수학 교육 과정은 주로 그런 계산 절차들이나, 그렇지 않으면 알고리듬이라고 알려진 것으로 이루어져 왔다. 우리는 수의 덧셈, 뺄셈, 곱셈, 나눗셈에 관한 알고리듬을 배우기 시작함으로써 대수식을 조작하고 방정식을 해결하는 알고리듬으로 나아가는데, 만일 우리가 계속해서 미적분학으로 나아가게 된다면, 라이프니츠가 그 주제에 관해 최초로 개발한 알고리듬을 사용하는 방법을 배우게된다. 그렇지만, 힐베르트는 전례가 없었던 범위의 알고리듬을 요구하고 있었다. 원칙적으로, 그의 결정 문제에 대한 알고리듬에 따라 모든 인간의 연역적 추론은 단순한 계산으로 환원될 것이다. 상당 부분, 그것은 라이프니츠의 꿈을 이루게 될 것이다.
수학자들은 종종 어려운 문제를 두 방향으로 접근하기 좋아한다. 한편으로는, 일반적인 문제의 특수한 경우들로 할 수 있는 것을 하려고 애쓴다. 또 방향을 달리하여, 일반적인 문제를 어떤 특수한 경우들로 환원하려고 한다. 모두 잘 되면, 두 가지 접근은 일반적인 문제에 해답을 마련하면서 중간에서 만난다. 결정 문제에 관한 연구는 정확히 이런 식으로 진행되었고, 실제로, 적용될 알고리듬들이 발견된 특수한 경우들과 일반적인 문제가 환원된 경우들 사이의 간극은, 조금만 더 나아가면 간극을 완전히 제거하고 힐베르트가 찾던 알고리듬을 마련해 줄 것으로 기대할 수 있을 만큼이 폭까지 좁혀졌다. [203~204p]

튜링은 알고리듬이, 마치 요리책에 나오는 조리법처럼, 누구나 정확한 기계적 방식으로 따를 수 있는 일련의 규칙들로 으레 규정된다는 것을 알고 있었다. 그러나 그는 초점을 규칙에서, 사람이 그 규칙을 실행할 때 실제로 하는 행위로 돌렸다. 그는 없어도 되는 세부 사항을 연속적으로 없애는 과정을 통해, 계산의 최종 결과를 바꾸지 않으면서도 사람의 동작을 몇 가지 매우 단순한 기본 동작으로 제한할 수 있음을 보여 줄 수 있었다. 튜링의 다음 단계는 이와 똑같은 기본 동작을 수행할 수 있는 기계로 사람을 대신할 수 있음을 보여 주는 것이었다. 그 다음에, 기본 동작만 수행하는 어떠한 기계도 제시된 결론이 주어진 전제들에서 나오는지를 프레게의 규칙을 사용하여 결정할 수 없다는 증명을 통해, 결정 문제에 관한 어떤 알고리듬도 존재하지 않는다고 결론 내릴 수 있었다. 그는 부산물로 만능 계산 기계의 수학적 모형을 발견했다. [205~206p]
얼마나 많은 기호들을 한 사람이 동시에 다룰 수 있는가? 그리고 하나의 계산을 정확하게 실행하는 데 얼마나 많은 기호들이 실제로 필요한가? 첫 번째 질문에 관해서는, 확실히 사람에 따라 다르겠지만, 어떤 경우에도 그다지 많이 다루지는 못한다. 두 번째 질문에 관해서, 답은 하나이다. 그 이유는, 동시에 몇 가지 기호에 주의를 기울이는 효과는 언제나 그 기호들 각각에 따로따로, 한 번에 하나씩 주의를 기울여서 얻어질 수 있기 때문이다. 더군다가 테이프 위의 특정한 네모칸에서 어느 정도 거리가 떨어진 다른 네모칸으로 주의를 돌리는 효과는 네모칸을 한 칸씩 오른쪽으로 옮기거나 왼쪽으로 옮기는 연속적인 움직임으로 얻을 수 있다. 이 분석을 통해, 어떠한 계산도 다음의 방식으로 진행되는 절차라고 생각할 수 있다는 결론을 얻게 된다.
` 계산은 네모칸이 그려진 종이 테이프 위의 네모칸 안에 기호를 써서 실행된다.
` 각 단게에서 계산을 수행하는 사람은 정확히 이 네모칸들 중 하나에 적힌 기호에 주의를 기울인다.
` 여자의 다음 행동은 이 기호와 여자의 마음 상태에만 달려 있다.
` 앞서 말한 다음 행동에는 여자가 주의를 기울여 온 네모칸에 기호를 쓰는 행위도 포함될 것이고, 그리고 나서 아마도 즉각 왼쪽 아니면 즉각 오른쪽의 네모칸으로 주의를 돌리는 행위도 포함될 것이다.
-중략- 계산을 실행하는 사람의 마음 상태는 기계 내부의 여러 가지 설정값으로 나타난다. 기계는 매 순간마다 정확히 테이프 위의 한 기호, 즉 읽어 들인 기호(scanned symbol)에 반응하도록 설계되어야 한다. 기계의 내부 설정값과 읽어들인 기호에 따라, 기계는 테이프 위에 (읽어 들인 기호를 대신하여) 기호를 적을 것이고 그 다음에 똑같은 네모칸을 계속 읽어 들이거나 아니면 즉각 테이프의 왼쪽이나 오른쪽으로 위치를 옮길 것이다. 계산의 목적에는 기계가 어떻게 구성되는지 또 기계가 무엇으로 만들어졌는지도 문제가 되지 않는다. 오직 중요한 것은 기계가 여러 가지 다른 설정값들(또는 상태들이라고 부른다)을 취할 능력이 있고 각각의 그런 설정값이나 상태에 적합하게 행동한다는 것이다. [209~210p]

특정한 튜링 기계가 존재하는 데 필요한 것은 무엇인가? 우선 첫째로, 기계의 가능한 상태를 모두 보여 주는 목록이 필요하다. 그 다음에는, 각각의 상태들과 테이프 위에서 만나게 될 각각의 기호에 관해, 그 기호를 만났을 때 그 상태에서 일어날 기계의 작동을 지정하는 것이 필요하다. 이 작동은, 되새겨 보자면, 읽어 들이고 있는 네모칸에 있는 기호의 변경, 왼쪽이나 오른쪽으로 한 칸을 옮기기, 가능한 상태의 변경, 이 세 가지로 단순히 이루어지는 것이다. [211p]

튜링 기계는 모두 그 테이프 위에 적힌 수에서 맨 왼쪽에 있는 숫자를 최초에 읽어 들인다고 생각할 수 있다. 이런 수들의 일부에 대해서, 기계는 결국 멈출 것이고, 반면 어떤 수들에 대해서는 영원히 계속 작동할 수도 있을 것이다. 첫 번째 범주에 속하는 자연수의 집합을 그 특정한 튜링 기계의 멈춤 집합(halting set)이라고 부르자. 이제, 만약 우리가 한 튜링 기계의 멈춤 집합이 한 개의 “꾸러미”를 구성한다고 생각하고 그 기계의 부호수를 그 꾸러미의 이름표로 생각하면, 우리는 정확히 대각선 방법을 적용하는 데 쓰일 전형적인 장치, 즉 이름표가 붙은 꾸러미들을 얻는다. 이때 꾸러미의 이름표는 꾸러미에 들어 있는 것과 정확히 같은 종류 – 이 경우는 자연수 – 이다. 우리는 대각선 방법으로 튜링 기계의 그 어떤 멈춤 집합과도 다른, D라고 부르는 자연수 집합을 만들 수 있다. 이제 어떻게 그럴 수 있는지 살펴보자. D는 전적으로 튜링 기계의 부호수로만 이루어질 것이다. 각각의 튜링 기계에 대해서, 그 각각의 부호수는 그 기계의 멈춤 집합에 속하지 않을 경우에, 그리고 오직 그 경우에만 D에 속할 것이다. 그러므로, 만약 어떤 특정한 튜링 기계의 부호수가 그것의 멈춤집합에 속한다면, 그 부호수는 D에 속하지 않는다. 이에 반해, 만약 그 부호수가 그 기계의 멈춤 집합에 속하지 않으면, D에 속한다. 어느 경우에도 D는 우리가 문제 삼고 있는 기계의 멈춤 집합과 똑같은 수의 집합일 수 없다. 이것은 모든 튜링 기계에 해당되기 때문에, 우리는 집합 D가 어떤 튜링 기계의 멈춤 집합도 아니다라고 결론 내릴 수 있다. [221~222p]

그러나 자신이 수행한 작업이 타당한지를 시험하기 위해 생각해 낸 가장 대담하고 영향력이 큰 착상은 보편 기계였다.
튜링 기계 테이프 위에 (통상적인 십진 표기로) 두 개의 자연수가 적혀 있고 두 수 사이에 빈 네모칸이 있다고 생각해 보자. 첫 번째 수를 어떤 튜링 기계의 부호수라고 하고 두 번째 수를 그 기계의 입력값이라고 하자.
이제 부호수가 테이프 위의 첫 번째 수인 튜링 기계가 테이프 위의 두 번째 수를 입력값으로 만났을 때, 그 튜링 기계가 무슨 일을 할지 밝혀내는 업무를 맡은 사람을 상상해 보자. 업무는 간단하다 그 사람은 테이프 위의 첫 번째 수에 의해 부호화된 기계를 구성하는 실제의 5 순서열을 얻으면서 시작할 수 있다. 그러면, 그 사람은 5순서열이 명령하는 어떤 것이든 테이프 위에서 단순히 작업할 수 있다. 그런데 튜링의 분석에 따르면 어떤 분명한 계산 업무도 튜링 기계로 실행할 수 있음을 보여 준다고 주장한 바 있다. 이 생각을 현재의 업무에 적용하면, 다음과 같은 튜링 기계를 상상할 수 있다. 즉, 우리는 테이프 위에 튜링 기계 M의 부호수로 시작하고 뒤에 M의 숫자 입력값이 주어진 경우, 튜링 기계 M이 그와 똑같은 입력값을 만났을 때 수행하게 될 일을 정확히 해 낼 튜링 기계를 상상할 수 있다. [227~228p]

튜링 이전에 통용되었던 일반적인 가정이란 그와 같은 기계를 다루는 데는 세 가지 범주 –기계, 프로그램, 데이터 – 가 완전히 분리된 실체들이라는 것이었다. 기계는 물리적 대상이었고, 오늘날 우리는 그것을 하드웨어라고 부른다. 프로그램은 계산을 하는 데 필요한 설계도로서, 아마 천공 카드나 플러그 판의 케이블 연결선에 구현되는 것이었다. 마지막으로, 데이터는 숫자 입력값이었다. 튜링의 보편 기계는 이 세 가지 범주를 구별하는 것이 착각임을 보여 주었다. 튜링 기계는 처음에는 기계적 부분을 가진 장치, 즉 하드웨어라고 상상하게 된다. 그러나 보편 기계의 테이프 위에 나타나는 기계의 부호는 프로그램으로서 기능하여, 적절한 계산을 하는데 필요한 명령을 보편 기계에 상세히 알려준다. 마지막으로, 각각의 작동 단계에서 보편 기계는 기계 부호의 숫자들(digits)을 그저 작동할 때 더 다루어야 할 데이터라고 여긴다. 이 세 가지 개념 사이의 이런 유동성은 현대의 컴퓨터 실행에서 기본적이다. 현대의 프로그래밍 언어로 작성된 프로그램은 인터프리터나 컴파일러에 대해서는 데이터가 되어, 인터프리터나 컴파일러가 그 프로그램의 명령이 실제로 실행될 수 있도록 그 프로그램을 다룬다. 사실 튜링의 보편 기계는 그 자체로 인터프리터라고 볼 수 있는데, 그 기계는 연속적인 5순서열들이 열거하는 과제를 수행하기 위해 그 5순서열들을 해석하면서 작동하기 때문이다. [228~229p]

이 논문에서, 처치는 이미 알고리듬적으로 해결 불가능한 문제들이 있다는 것을 보여 주었다. 그의 논문에서는 기계를 언급하지 않았지만 두 가지 개념을 지적했는데, 두 개념 모두 계산 가능성, 즉 처치의 표현으로는 ‘효과적인 계산 가능성’이라는 직관적인 관념을 설명해 주는 것으로 제안된 것이었다. 두 가지 개념은 처치와 그의 제자 스티븐 클린이 발전시킨 람다-정의 가능성과, 괴델이 (1934년 봄에 프린스턴고등연구소를 방문하는 동안 했던 강의에서) 소개한 일반 회귀성이었다. 두 가지 개념은 동등한 것이라고 증명되었고, 처치의 해결 불가능한 문제는 사실 두 가지 개념 어느 것에 대해서도 해결 불가능했다. 비록 이 논문에서 처치는 힐베르트의 결정 문제가 이 두 가지 개념에 대하여 그 자체로 해결 불가능하다는 결론을 이끌어 내지는 않았지만, 튜링은 재빨리 계산 가능성이라는 자신의 개념이 람다-정의 가능성과 동등함을 증명했고, 프린스턴에서 얼마 동안 지내 보기로 결심했다. [230p]

기존의 기술에 익숙해지기 위해, 튜링은 전기 기계 계전기를 이용하여, 2진법으로 적힌 수를 곱하는 장치를 실제로 만드느라 고생을 했다. 이를 위해 그는 물리학부 대학원생 기계 작업실에 들락거리며 필요한 계전기를 혼자 만들면서, 그 장치의 여러 부품들을 만들었다. [235p]

08 첫 번째 보편 컴퓨터 만들기

1945년 6월에 폰 노이만은 유명한<에드박에 관한 보고서 1차 초안 First Draft of a Report on the EDVAC>을 작성했는데 이 1차 초안에서 사실상, 곧 만들어질 에드박이 튜링의 보편 기계의 물리적 모형으로 실현될 것이라고 제안하였다. 추상적 장치인 튜링 기계의 테이프처럼, 에드박은 데이터와 부호화된 명령, 두 가지 모두를 담는 저장 능력 – 폰 노이만은 그것을 “기억 장치(memory)”라고 불렀다-을 갖게 될 예정이었다. 실제 문제에 관심을 기울여 보면, 에드박은 단일한 단계에서 각 기초 산술 연산(덧셈, 뺄셈, 곱셈, 나눗셈_을 실행할 수 있는 연산 장치를 가지게 될 예정이었는데, 반면 튜링의 원래 개념에서 이 연산들은 “왼쪽으로 한 칸 옮기기” 같은 그런 원시적인 연산으로 만들어져야 했다. 에니악이 열 개의 십진 숫자들로 표현된 수에 대해 산술 연산을 실행했던 반면, 에드박은 2진법을 채용함으로써 단순함을 지니게 될 예정이었다. 또한 에드박은 논리적 제어를 실행하는 장치를 포함할 예정이었다. 이때 논리적 제어는 기억 장치에서 연산 장치로 한 번에 하나씩 명령이 수행되도록 함으로써 실행된다. 컴퓨터를 구성하는 이런 방식은 폰 노이만 아키텍처라고 알려지게 되었는데, 오늘날의 컴퓨터들은 비록 에드박에 쓰이던 부품들과 아주 다른 부품들로 만들어져 있지만 대부분 여전히 이와 아주 똑같은 기초 계획에 따라 만들어진다. [252p]

- 제 2차 세계 대전 이후에 개발된 컴퓨터들이 초기 자동 계산기들과 근본적인 면에서 다르다는 것은 널리 알려져 있다. 그러나 그 차이의 본질을 이해하는 사람은 그다지 많지 않다. 전후에 만들어진 이 기계들은 처리 과정의 절차가 정확히 지정되기만 하면, 어떤 기호 처리 과정도 수행할 수 있는 만능 보편 장치로 설계되었다. 어떤 처리 과정들은 이용할 수 있는 양보다 더 많은 기억 장치가 필요할 수도 있고, 그저 너무 느려서 실행할 수 없을지도 모른다. 따라서 이 기계들은 튜링의 이상화된 보편 기계와 가까운 것일 수밖에 없다. 그렇긴 해도 이 기계들이 명령과 데이터가 공존할 수 있는 (튜링의 무한한 테이프에 상응하는) 큰 기억 장치를 가졌다는 점은 중요했다. 무엇이 명령이고 무엇이 데이터인지의 경계가 유동적이라고 하는 것은 다른 프로그램을 데이터로 취급하는 프로그램을 개발할 수 있다는 것을 뜻했다. 초기에는, 프로그래머들 대부분이 프로그램 자체를 변경할 수 있었고 실제로 변경한 프로그램을 작성하는 이런 자유를 흔히 누렸다. 오늘날 운영 체계(OS)와 서열화된 프로그래밍 언어들의 세계에서는, 훨씬 더 정교한 응용프로그램들에서 그런 방식들이 열려 있다. 어떤 운영 체계에서, 실행되는 프로그램들(예를 들어, 여러분이 쓰는 워드 프로세서나 전자우편 프로그램)은 그 운영 체계의 입장에서 보면 다루어야 할 데이터이다. [255~256p]

그렇지만, 빠른 전자 컴퓨터에는 빠른 기억 장치가 필요했다. 이것은 기억 장치의 어떤 장소에 저장된 데이터라도 직접 한 번에 접근할 것을 요구했다. 즉 기억 장체는 랜덤 액세스되어야 함을 요구했다. [256p]

불행히도 내장 프로그램이라는 이 용어는 다음과 같은 사실을 흐리게 하는 데 이바지하였다. 즉, 내장 프로그램이라는 측면은 목적 달성을 위한 한 가지 수단일 뿐인 반면, 이런 기계들에서 진정으로 혁명적인 것은 그 기계들이 지닌 보편적이고 만능적인 성격이라는 사실을 흐리게 하는 데 이바지했다. 튜링과 폰 노이만의 관점은 개념적으로 너무나 단순하고 우리의 지성적 풍조의 너무나 깊은 일부가 되어 버려서 그 관점이 얼마나 근본적으로 새로웠는지 이해하기 어렵다. 새롭고 추상적인 생각보다 수은 지연선 같은 새로운 발명품을 더 중요하게 평가하기 쉽다. [257p]

튜링의 ACE는 폰 노이만의 에드박과 아주 다른 종류의 기계였는데, 이런 차이는 두 수학자의 서로 다른 태도와 거의 일치했다. 비록 폰 노이만은 자신의 기계가 진실로 “만능”이기를 바랐지만, 그의 강조점은 수치 계산에 관한 것이었고 에드박(과 나중의 조니악)의 논리적 조직 체계는 이런 방향으로 촉진시키기 위한 것이었다. 튜링은 ACE가 대량의 산술이 필요 없는 많은 일들에 유용하다는 것을 알았기 때문에, ACE는 논문<계산 가능한 수들>의 튜링 기계에 가깝게, 훨씬 더 최소의 방식으로 구성되었다. 산술 연산은 프로그래밍, 즉 하드웨어보다는 소프트웨어로 실행되게 될 터였다. [260p]

가장 기초적인 컴퓨터 연산을 프로그래머가 직접 이용할 수 있게 하는 이른바 마이크로 프로그래밍은 ACE 설계에서 예견 되었음을 알 수 있다. 또한, 우리가 오늘날 사용하는 개인용 컴퓨터는 사실상 칩 속의 보편 컴퓨터인 실리콘 마이크로 프로세서들을 중심으로 제작되는데, 이런 컴퓨터들은 더욱더 정교해져 왔다. 반대편 패러다임인 이른바 RISC(명령어 축소형 컴퓨터) 아키텍처는 많은 컴퓨터 제조사들이 채택했다. 이 아키텍쳐는 칩속의 최소 명령 세트를 사용하고, 필요한 기능을 프로그래밍에 의해 제공받는다. 이것은 또 한 번 ACE 철학과 상당히 일치한다. [261p]

저는 중심 메커니즘을 가진 기계 종류와, 무한한 테이프 위에 담겨 있는 무한한 기억 장치를 생각했습니다. 제가 내린 결론들 중 하나는 이렇습니다. “실제 셈(rule of thumb)”과정이라는 관념과 “기계 과정”이라는 관념은 뜻이 같다는 것입니다. ACE와 같은 기계들은 제가 생각했던 기계 유형의 실용판이라고 여겨질지도 모릅니다. 적어도 매우 밀접한 유사성이 있습니다. ACE와 같은 디지털 계산 기계들은 사실상 보편 기계의 실용 판입니다. [261p]

튜링은 “계산 기계가 인간의 행동들을 흉내 내는 것이 도대체 어느 정도 가능한지” 하는 의문을 계속 제기했다. 이것을 통해 그는 실수하며 학습하도록 프로그램된 계산 기계의 가능성을 제시하게 되었다. “만약 어떤 기계가 절대 오류가 없다고 기대한다면, 그 기계는 또한 지적일 리 없다고... 거의 정확하게 말하는 몇 가지 정리들이 있습니다. ... 그러나 이 정리들은 기계가 무오류인 체하지 않는다면 얼마나 많은 지능이 발휘될지에 대해서는 아무것도 말하지 않습니다.” 이것은 괴델의 불완전성 정리에 대한 간접적인 언급이었는데, 다음 장에서 더 다루게 될 것이다. 튜링은 컴퓨터가 인간보다 더 오류가 없을 것이라고 기대해서는 안 된다고 하는 “컴퓨터에 대한 페어플레이”를 호소했다. 그러면서 시작점으로 체스 게임이 적절한 연습이 될 것이라고 제안하며 강연을 끝맺었다. 이 모든 것은 이런 장치들 중 단 하나도 아직 완성되지 않았을 때의 일이었다! [261~262p]

활동으로서의 컴퓨터 프로그래밍에 관한 폰 노이만의 관점과 튜링의 관점을 대조해 보는 것은 흥미롭다. 폰 노이만은 컴퓨터 프로그래밍을 “코딩(coding)”이라고 불렀고 지적 능력이 거의 필요하지 않은 사무적인 일이라고 생각한다는 점을 분명히 했다. 한 가지 주목할 만한 일화가 있다. 고등연구소의 컴퓨터 시설에서, 사람이 읽기 쉬운 연상 기호로 작성된 컴퓨터 명령들을, 학생들을 이용해 손수 기계어로 번역하는 작업이 이루어졌다. 젊고 유능한 어느 프로그래머가 자동으로 이 변환을 실행할 어셈블러를 작성하자고 제의했다. 폰 노이만은 단순한 사무적인 일을 하기 위해 과학적 수단을 쓰는 것은 낭비라며 화를 내며 반응했다고 한다. 튜링은 자신의 ACE 보고서에서, 컴퓨터 프로그래밍 과정은 “매우 매혹적일 것이다. 단조롭고 힘든 일을 하는 사람이 될 그 어떤 실질적인 위험도 필요 없다. 왜냐하면 다소 기계적인 공정은 모두 기계에게 맡겨질 것이기 때문이다”라고 말했다. [265~266p]

그러다가, 드디어, 앨런 튜링의 이름은 《타임Time》(1999년 3월 29일자 기사)이 선정한 20세기의 가장 위대한 스무 명의 과학자와 사상가의 명단에 올랐다. [266p]

문제는, 어느 컴퓨터 기능이 하드웨어에 의해 제공되어야 하고 또 어느 기능이 소프트웨어에 의해 제공되어야 하는지라는 물음과 같은 더 일반적인 맥락에서 가장 잘 이해할 수 있다. 튜링은 상대적으로 간단한 기계를 제안했는데, 그 기계의 많은 부분은 소프트웨어가 맡도록 맡겨졌고, 그것을 보완하기 위해, 프로그래머가 기계의 기본 운영을 매우 실질적으로 제어하도록 했다. 이것은 특히 수치 계산보다는 오히려 논리적 계산을 수행하기 위한 프로그램을 쓰는 데 유리했을 것이다. [269~270p]

1938년 10월에, 앨런은 월트 디즈니의 《백설 공주와 일곱 난쟁이》를 보았다. “그는 사악한 마녀가 사과를 줄에 매달아서 끓는 독주에 담그면서,
독주에 사과를 담그면
잠결 같은 죽음이 온몸에 퍼지겠지
하며 중얼거리는 장면에 사로잡혀 버렸다.“ 그는 이 시구를 몇 번이고 읊으면서 즐거워했던 것 같다.
1954년 6월 7일, 앨런 튜링은 청산가리 용액에 담가 놓았던 사과 반쪽을 베어 문 채 숨을 거두었다. [272p]

09 라이프니츠의 꿈을 넘어서

1950년에, 앨런 튜링은 고전적인 논문,<계산 기계와 지성Computing Machinery and Intelligence>을 발표했다. 그는 이 논문에서 말을 주고받고 있는 상대가 사람인지 컴퓨터인지 분간할 수 없을 만큼 유창한 대화를 정말로 진행할 수 있는 컴퓨터 프로그램이 20세기가 끝나기 전까지 나오게 될 것이라고 예언했다. 그 예언은 빗나갔다. [278p]

설은 우리에게 딥 블루가 “의미 없는 기호 묶음들을 갖고 있다”고 말한다. 자, 만약 당신이 딥 블루가 작동하고 있을 때 안쪽을 살펴볼 수 있다면, 당신은 의미 있든 없든 어떤 기호도 보지 못할 것이다. 회로 수준에서 보자면, 전자들은 여기저기 돌아다니고 있다. 마찬가지로 카스파로프가 시합하고 있을 때 당신이 그의 머릿속을 살펴본다면, 어떤 체스 말도 보지 못하고, 불꽃이 튀는 뉴런들을 보게 될 것이다. 우리의 두뇌가 우리가 생각하는 바를 기호 정보로 다루기 위해 조직되는 방식은 여전히 어렴풋이 이해될 뿐이다. [262p]

로저 펜로즈는 우주 기하학에 관한 흥미 있는 연구를 해 온 유명한 수학자이자 수리 물리학자로서, 인간이 가진 정신의 기능이 기본적으로 알고리듬적인지에 대해 의문을 품어 왔다. 괴델의 불완전성 정리를 빌려서, 펜로즈는 분명히 아니오라고 응답했다. 괴델의 불완전성 정리를 표현하는 한 가지 방법은 다음과 같다.
자연수들에 대해 참인 진술을 연달아 내놓는 알고리듬이 주어진다면, 우리는 그 알고리듬으로 생성되지 않는, 자연수들에 대해 참인 또 다른 진술 – 그것을 괴델 문장이라고 부르자 –을 언제나 얻을 수 있다. [285p]
오늘날 너무 자주, 과학자들에게 생활과 연구에 필요한 제원을 제공하는 사람들은 신속하게 결과를 제공할 것 같은 방향으로 과학자들을 이끌려고 애쓴다. [288p]

에필로그
또한 괴델의 불완전성 정리가 “모든 일반 수학은 형식 논리 체계로 요약될 수 있다”는 힐베르트와 러셀의 생각과, “언어 내부에서 언어에 대해서 말하는 문제”에 관한 비트겐슈타인의 강조가 결합된 것을 토대로 가능했을 것이라는 저자의 암시는 흥미롭다. [325p]