지금까지 정리

인류는 인간 지능의 자동화를 꿈꾸고 있었다. 그래서 이를 실현시키기 위해서 노력하는 이들이 있었다.

그러나 이 세력과는 별개로 수학과 논리의 진리를 탐구하는 이들도 있었다. 이들은 수학적 지식을 증명하여 생산하는 일이 몇 개의 단순한 규칙들의 조합을 통해서 이뤄진다고 추측하였다. 그리고 이 추측(수리명제 자동판별 문제)을 증명하고자 노력했다.

이 추측은 힐베르트가 수학자들에게 처음 제시하였는데, 괴델이란 사람이 불가능하다고 증명해버렸다.(괴델의 분완전성 정리) 그리고 이를 본 젊은 수학자가 있었으니, 그가 바로 튜링이다.

튜링은 자신만의 방법으로 해당 정리를 재증명하고자 했다. 그의 방식은 대략적으로 다음과 같다.

수리명제 자동판별 문제의 핵심은 기계적인 방식으로 수리명제들을 증명할 수 있는지의 여부이다. 그래서 튜링은 기계적인 방식을 정의하였다. 그러나 이 정의는 어떤 특정한 기계 또는 기계들의 집합에 종속적이어선 안되고, 보편성을 가져야만 했다. 그래야만 ‘기계적’이란 칭호를 붙일 수 있기 때문이다. 따라서 그는 보편적인 기계적 방식에 대해서 정의한다. 그리고 그 기계적 방식을 수행하는 기계를 튜링 머신이라고 이름을 붙였다. 그리고 튜링 머신을 이용하여 괴델의 불완전성 정리를 재증명하고자 했다.

만약에 수리명제 자동판별 문제를 해결하는 기계적 방식으로서, 해당 튜링 머신이 존재한다고 하자. 그렇다면 이 세상 모든 문제를 해당 튜링 머신은 해결할 수 있을 것이다. 그 한 예로 멈춤 문제라는 것을 해결하는 튜링 머신도 있다고 해보자.

멈춤 문제란, 어떤 문제를 해결하기 위해서 튜링 머신이 일을 할텐데, 그 일을 무한히 할지 아니면 유한한 시간 안에 해결하고 기계가 멈출 지 판단하는 기계이다.

만약 멈춤 문제를 해결하는 튜링 머신이 존재한다면, 튜링 머신의 수는 자연수의 개수를 넘어버린다. 튜링 머신은 그 구성요소들을 n진법으로 표현할 수 있기에 자연수에 대응된다. 그리고 이런 방식의 대응으로 인해서 튜링 머신의 수가 자연수의 개수만큼 있다고 추론할 수도 있다. 따라서 귀류법에 의해서 멈춤 문제를 해결하는 튜링 머신은 존재할 수 없다. 그리고 대우증명법에 의해서 수리명제 자동판별 문제를 해결하는 튜링 머신도 존재하지 않는다.

이러한 증명을 하면서 튜링은 보편만능기계라는 것을 사용했었다. 보편 만능 기계란 자연수로서 표현된 튜링 기계를 입력 받을 수 있고, 그 기계를 흉내낼 수 있는 특수한 튜링 기계를 말한다. 이 보편 만능 기계가 현대의 컴퓨터의 청사진이다.

튜링 머신의 입력 테이프는 메모리에 대응되고, 규칙표는 cpu, 기계의 상태는 cpu 레지스터값, 문자를 읽고 쓰는 기계는 메모리 입출력 장치로 구현되었다.

(사실 입출력 기계 그 자체를 메모리 입출력이라고 강의에서 말씀하셨지만, 나는 더 자세히 쪼개야 한다고 생각한다.)

이렇게 컴퓨터의 청사진은 등장하게 되었다. 이러한 청사진이 등장하기까지는 수학과 논리의 세력은 400년 동안 지식을 축적했었다. 이런 축적이 이뤄지고 나서야 드디어 컴퓨터의 개념적 설계도가 등장한 것이다. 그리고 최종적으로 인간 지능의 자동화란 꿈에 더 가까워진 것이다.

그런데 처음에 말했듯이 인간 지능의 자동화를 꿈꾸는 다른 세력들도 있었다. 그러나 튜링 머신으로 인해 그 세력들이 제시한 방법은 모두 그 위엄을 잃어버렸다. 튜링 머신보다 성능이 나빴기 때문이다.

이제는 개념적으로 구상된 컴퓨터의 설계를 실제로 구현하는 지식들을 집중해보자. 개념적 컴퓨터의 청사진인 튜링 머신이 등장하기까지 400년과 동시에 100년 정도 실제 구현을 위한 기술들이 따로 축적되었다. 그러나 아주 신비롭게도 이 축적은 거의 같은 시기에 이뤄지고 있었다.

대략적으로 구현을 위한 기술은 다음과 같다. 불 대수, 스위치 회로 등이다.

불이란 학자는 생각의 법칙에 대해서 논문을 발표했다. 사람들의 생각이 대략적으로 and, or, not이란 법칙에 의해서 조합되고, 이 조합된 결과물을 다시 조합해서 보다 더 복잡한 생각에 이른다는 것이다. 그래서 그의 법칙에 의해서 사람들의 생각을 어떤 규칙을 이용하여 표현할 수 있게 되었다.

그리고 이 규칙을 이용하면, 서로 그 구성은 다르지만 결과는 같은 생각들을 만들어낼 수 있었다. 그리고 이러한 규칙들을 불 대수라고 이름 붙였다.

스위치 회로 기술은 전기적 신호를 제어하는 회로 기술이었다. 그러나 그때 당시에는 어떤 규칙을 도입하지 않고, 엔지니어의 경험 또는 기예적인 차원에서 다뤄지고 있었다. 즉, 주먹구구식이었다.

이런 상황에서 클로드 새넌이란 학자는 불 대수와 스위치 회로가 완전히 동일하게 다룰 수 있음을 발표하였다. 그리하여 사람들의 생각을 실제적인 물리적 회로로 표현할 수 있는 길이 생긴 것이다.