Programming and my thoughts

제 블로그의 다른 포스팅은 지난 일로 접어두더라도...

이 포스팅은 꼭 다시 가져오고 싶었습니다.

너무나도 감명깊게 읽었던 책이었거든요.


저자 : 마틴 데이비스

역자 : 박정일


수학자, 컴퓨터를 만들다


http://book.naver.com/bookdb/book_detail.nhn?bid=1512893


이 책은 현재 절판되어 서점에서 구매할 수 없습니다.

참 재미나고 유용한 책인데... ㅠㅠ

제 블로그 포스팅 하나로 중요한 내용을 최대한 압축해 보도록 하겠습니다.


네... 이 책은 수학자들의 이야기입니다.

특히 컴퓨터와 프로그래밍 언어의 발명에 영향을 미친 위대한 수학자들의 이야기입니다.


수학 : ★★★☆☆

난이도 : ★★☆☆☆

인문학적 사유 : ★★★★☆


이런 성격의 책입니다.

수학책은 분명한데... 컴퓨터 자체가 논리학에서 시작되었으므로...

복잡한 수식이나 공식은 많지않아 난이도는 높지않습니다.

오히려 인문학적인 성격이 강하다고 생각합니다.


라이프니츠, 부울, 프레게, 칸토어, 힐베르트, 괴델, 튜링

요 일곱 수학자들의 이야기입니다.


한가지 주목할 것은...

일곱 수학자들이 컴퓨터를 만들기위해 고군분투한 것은 아니라는 점입니다.

이들은 여기서 소개한 내용외에도 학술적, 철학적으로 무수히 많은 업적을 남긴 인물들입니다.

그 업적들 가운데 결과적으로 컴퓨터의 발명을 이끄는데에 도움을 준 것들을 여기에서 소개하고자 합니다.


1. 라이프니츠 (고트프리트 폰 라이프니츠)

1646. 07. 01. ~ 1716. 11. 14.


라이프니츠

- 이진법을 생각하다.


이 세상의 모든 숫자들을 표현할 수 있는 효과적인 방법이 없을까?

0과 1만 가지고 세상 모든 숫자들을 표현할 수 있을 것이다 !


10 = 1010

11 = 1011

12 = 1100


지금보면 당연한 사실이지만, 

라이프니츠는 무려 400여년전에 이진법을 고안했고 많은 학술적 자료에서 자신의 이진법을 이용했습니다.


리니지, 월드 오브 워크래프트(WOW)는 컴퓨터로 만든 온라인 게임입니다.

컴퓨터안의 세계는 0과 1로 모든 것을 표현할 수 있으므로...

오래전 라이프니츠의 생각은 과연 옳았습니다.


여담으로... 

라이프니츠는 이외에도 미적분학을 만들었고, (...)

2016년 노벨물리학상의 주요 주제인 위상기하학을 수백년이나 앞서 생각하고 연구했던 천재로 알려져 있습니다.

너무 오래전의 인물이라 쉽게 와닿지 않지만, 대단한 천재임에는 틀림없습니다.


2. 조지 부울

1815. 11. 02 ~ 1864. 12. 08



부울도 현대의 컴퓨터 구조를 만드는데 한 몫 했습니다.

부울대수라고 전자계산기구조에서 사용되는 AND, OR 게이트를 생각해냈지요.

명제를 일종의 논리적인 기호를 사용하여 표현해냈습니다.


모든 사람은 죽는다

소크라테스는 사람이다 

그러므로 소크라테스는 죽는다


사람은 죽는다

소크라테스는 사람이다

소크라테스는 죽는다


사람 : A

죽는다 : B

소크라테스 : C


A → B

C → A

C → B


여기서 발전하여 아래와 같은 개념이 탄생했습니다.

부울

- 기호를 사용하여 명제를 표현할 수 있다. (부울대수)


X 이면 Y 이다.


이것은 다시 말해서, X=1 이면 Y=1 이다.

이것을 최종적으로 다시 표현하면, X(1-Y)=0 이다.


마지막 식을 생각해 봅시다.

X=1 이면 1-Y=0 이 되고 여기서 Y=1 이 됩니다. 정확하지요.


X(1-Y)=0 이라는 말은

X 이면서 Y가 아닌것(1-Y)은 거짓이다는 말과 같습니다.


이 말은 XY=1 과도 같지요. X=1이면 Y=1이 됩니다.


정말 명쾌한 논리가 아닐 수 없습니다.

부울은 논리적인 기호만을 사용하여 명제를 표현하는 것에 성공했습니다.

이것을 부울대수라고 합니다.


위와 같은 진리표는 우리가 일상 생활을 할 때에도 정말 많이 사용합니다.


3. 고틀로프 프레게

1848 ~ 1925



프레게는 기호논리학을 만들었습니다.

프레게

- 기호를 사용하여 논리를 표현할 수 있다. (기호논리학)


1. (∃x)(∀y)Lxy

2. (∀y)(∃x)Lxy

3. (∃y)(∀x)Lxy

4. (∀x)(∃y)Lxy


위에서부터 순서대로...


1. 어떤 사람은 모든 사람을 사랑한다.

박애주의자, All people are loved by somebody.


2. 모든 사람은 어떤 사람한테 사랑받는다.

누구나 사랑을 받는다, Every person is loved by somebody.


3. 어떤 사람은 모든 사람한테 사랑받는다.

슈퍼스타, All people love somebody.


4. 모든 사람은 어떤 사람을 사랑한다.

누구나 사랑을 한다, Every person loves somebody.


주의할 것은... All 과 Every 를 구분할 줄 알아야합니다.

이것을 구분하지못할 때 논리적 오류를 범할 수 있습니다.


이런 것이 기호논리학 입니다.

부울이 수학에 기초한 논리표현법을 생각해냈다면

프레게는 자신만의 기호를 사용하여 논리를 좀 더 체계적으로 표현하는 방법을 만들어냈습니다.



말씀드린 바와 같이 기호논리학입니다.

컴퓨터공학과에서 논리학이라는 수업을 들으면 한 학기동안 이것만 가지고 수업을 합니다. (ㄷㄷㄷ)

한 학기동안 열심히 공부했으나... 10년이 지나니 하나도 기억이 나지않는다.


핵심은 양화사(수량사)(Quantifier)를 이용하여 논리에 대한 수량표현이 가능하다는 것입니다. (1개 혹은 2개 같은 구체적 수량까지...)

구체적인 수량표현을 할 경우, 기호식의 길이가 정말 길어지지만... 그래도 대단한 발견임에는 틀림없습니다.


4. 게오르그 칸토어

1845 ~ 1918



칸토어!! 드디어 등장했습니다.

컴퓨터의 등장을 도운 일곱 수학자들중 제 개인적으로는 가장 인상적인 업적을 남긴 인물로 평하고 싶습니다.

일곱 수학자 모두가 대단한 사람임에는 틀림없지만... 칸토어는 컴퓨터의 실수 체계를 완성하는데에 결정적인 역할을 했다고 생각합니다.


10년만에 칸토어의 대각선 논법을 들여다봤는데... 여전히 혼돈의 카오스더군요.

공부해도 모르겠으니 역시 학교다닐 때 공부안하길 잘했다 (?)

칸토어

- 무한집합중에서도 더 큰 무한집합이 있다.


위 명제는 칸토어가 증명한 것으로써 "참" 입니다.

구체적으로는... 자연수 집합보다 실수 집합이 더 크다는 사실을 증명했습니다.


칸토어의 대각선 논법을 짧게, 그리고 아주 쉽게 설명하겠습니다.

그래서 이진법으로 설명합니다.


1. 자연수 집합이 있습니다. { 1, 2, 3, 4, 5 ... }

2. 0 과 1 사이의 실수 집합이 있습니다. 쉬운 이해를 위해 이것은 이진법으로 표현하고자 합니다. { 0.001, 0.010, 0.100, 0.101, ... }


이제 우리는 집합 1 과 집합 2 를 일대일 대응관계를 만들 것입니다.

좌측에는 집합 1 의 원소를, 우측에는 집합 2 의 원소를 씁니다.

둘 사이에는 어떤 수학적 관계도 없으며... 단순히 일대응 대응관계만이 존재합니다.


1 : 0.1010

2 : 0.1111

3 : 0.0001

4 : 0.0010


여기까지만 해보겠습니다.

이제 여기서 우측의 이진수 자릿수 하나씩을 행마다 대각선 방향으로 취해보겠습니다.


1 : 0.1010

2 : 0.1111

3 : 0.0001

4 : 0.0010


이렇게 취한 이진수들을 하나의 숫자로 표현합니다.


0.1100


그 다음에, 각 자리의 이진수들을 뒤집습니다.


0.0011


자... 0.0011 이라는 새로운 이진수 숫자를 만들었습니다.

그러나, 좌측의 자연수는 현재 1, 2, 3, 4 까지밖에 없지요.


이 전개를 무한대로 확장해서 생각해보더라도...

칸토어의 대각선 논법으로 얻은 실수는 항상 좌측의 자연수에는 없게됩니다.


0.0011 이라는 이진수 숫자를 얻어낸 방법 자체가 (대각선 논법) 

좌측의 자연수 집합에 없는 수를 구하기위한 방법이기 때문입니다.

따라서 우측의 실수 집합의 수는 항상 좌측의 자연수 집합보다는 크게됩니다.


* 좌측의 자연수도 단순히 1씩 증가시키면 같은 논리로 자연수 집합이 커보이지만... 

이 논법의 출발점은... 좌/우측에 이미 각각 무한대의 자연수 집합/무한대의 실수 집합이 있다는 것을 생각해야 합니다.


결국 이 생각을 정리하면...

무한집합중에서도 더 큰 무한집합이 있다는 말이 됩니다.


컴퓨터가 정확한 실수 연산을 할 수 없는 이유를 비슷하게 생각해볼 수 있습니다.


종이에 숫자를 적는다고 가정해보면... 종이가 아무리 커도 적을 수 없는 숫자가 존재합니다. ( 예 : 1/3 = 0.33333333 ... 무한소수 )

종이를 메모리라고 생각하고, 숫자를 실수라고 생각해봅시다.

메모리가 아무리 커도, 이 메모리로 표현할 수 없는 실수가 존재하는 것과 같습니다.

* 요약 : 네 컴퓨터 메모리로는 이 게임은 못돌린다.


따라서 컴퓨터를 이용하여 실수 연산을 할 때에는 

유효자릿수를 정해놓고 한다든지, 제한적인 설정이 필요하게 됩니다.

이후에 칸토어는 이 생각을 확장하여 연속체 가설을 제안하였고, 이것을 증명하는데에 일생을 매진하였으나, 결국 실패했습니다.

* 연속체 가설 : 쉽게 말하면... 자연수 집합보다는 크고 실수 집합보다는 작은 무한 집합이 있을까?

후대에 쿠르드 괴델(참이라고 가정하면 모순이 없다)과 폴 코언(거짓이라고 가정하면 모순이 없다)에 의해... 

이것이 참인지 거짓인지 알 수 없다는 것이 증명되었습니다.


1. 쿠르드 괴델 : 참이라고 가정해도, 현존하는 수학적 공리들에 위배되는 것이 없다.

2. 폴 코언 : 거짓이라고 가정해도, 현존하는 수학적 공리들에 위배되는 것이 없다.


* 공리?

공리(公理, 영어: axiom)는 어떤 이론체계에서 가장 기초적인 근거가 되는 명제(命題)입니다.

예) a=b 이면, a+c = b+c이다.


이제 무한의 세계는 여기까지만 쳐다보도록 하겠습니다.

더 궁금하면 MBC 무한도전을 보세요 (?)


5. 다비트 힐베르트

1862. 01. 23 ~ 1943. 02. 14



19세기부터는 학술적으로 정말 대단한 인물들이 많았습니다.

힐베르트도 그 중 한명입니다.

힐베르트

- 수학과 논리학을 결합시키다. (메타수학)


힐베르트는 메타수학을 만들었습니다.

메타수학이라는 용어는 생소할 수 있는데... 그 내용은 간단합니다.


1 + 1 = 2 라는게 있습니다. 이건 우리가 쉽게 이해할 수 있죠 !


1 → 102

+ → 103

= → 711

2 → 622


이라고 합시다.

그러면 1 + 1 = 2 는 이렇게도 표현할 수 있겠죠.


102103102711622


로또 추첨번호도 아닌 이 무슨 해괴한 숫자인가 싶지만은... 자세히 보면 1 + 1 = 2 를 다른 방법으로 표현한 것입니다.

부호화된 수식을 사용해서 새로운 수학체계를 만들 수 있다는 사실을 알 수 있습니다.

컴퓨터 컴파일러를 설계할 때에도 당연히 생각하는 부분입니다.


컴퓨터는 0과 1밖에 모르지만,

0과 1만 가지고서 세상의 모든 복잡한 수식을 척척 풀어냅니다.


그 출발점에는 힐베르트가 있었다는 사실을 기억해야 하겠네요 ㅎㅎ


- 진리로서의 수학이 있을까? (힐베르트 프로그램)


힐베르트는 1922년에 힐베르트 프로그램이라는 것을 발표합니다.

이것에 대해 이해하기 위해서는 20세기초 인류의 시대적 열망과 분위기를 살펴볼 필요가 있습니다.

당시 인류는 종교적인 사유에서 벗어나 수학과 과학을 통해 보편타당한 진리를 탐구하고자 하는 열망이 깊었습니다.

진리는 변하지 않거든요.

진리는 어디에 숨어있는가에 대한 질문에 대한 해답을 찾기위해 당시 수학과 물리학에 기대를 걸고 있었죠.

인류는 종교가 아닌 이성을 통해 진리를 탐구하고자 했습니다.


힐베르트 프로그램은 그렇게 주목을 받게됩니다.


힐베르트 프로그램의 모든 내용을 기술하기에는 저도 역부족이라...

간단하게 요약하겠습니다.


힐베르트는 수학적 공리가 되기위해서는 세가지 조건이 필요하다고 말했습니다.


1. 무모순성 (Consistency)

하나의 공리계를 가지고 임의의 명제 P와 그 부정인 ∼P를 동시에 증명할 수 없습니다.

기호로 간단히 표현하면 P ∩ ∼P = ∅ 입니다.


2. 완전성 (Completeness)

어떤 공리계가 완전하다는 것은 

그 공리계를 가지고 임의의 명제 P와 그 부정인 ∼P 둘 중 하나는 반드시 증명할 수 있다는 뜻입니다.

기호로 간단히 표현하면 P ∪ ∼P = U 가 됩니다.


3. 독립성 (Independency)

공리 체계를 구성하는 각각의 공리들은 독립적이어야 합니다.

체계의 나머지 공리들로 증명되는 정리는 공리가 아니라고 합니다.


힐베르트는 위 세가지 조건을 충족하여 만든 제대로 된 자연수 공리 체계를 가지고 있다면...

체계 자체는 아무런 문제가 없고 모순도 없으며, 모든 수학적 명제를 증명할 수 있다고 주장했습니다.


힐베르트 프로그램이 컴퓨터의 발명에 어떤 기여를 했는지는...

이후 괴델과 튜링까지 살펴봐야 이해할 수 있을 것입니다.

그러나, 힐베르트 프로그램은 몇년뒤 25세의 괴델에 의해 무너지게 됩니다.


6. 쿠르드 괴델

1906. 04. 28 – 1978. 01. 14



괴델이 어떤 사람인지는 아래 사진 한 장으로 요약됩니다.



그는 아인슈타인의 절친한 친구였습니다.

서로가 뛰어난 학술적 조언자이기도 했고, 아인슈타인이 퇴근길에 괴델과 함께 다녔다는 일화는 유명하죠.

괴델은 오스트리아 출신이나 1940년에 나치를 피해 미국으로 이민을 갔고, 아인슈타인과 함께 일했습니다. 

이후에 미국 시민권을 취득할 때에는 아인슈타인이 큰 도움을 주기도 했습니다.

불세출의 수학자, 과학자로서 대단히 많은 업적을 남겼지만, 대표적으로 25살에 남긴 불완전성 정리가 가장 유명합니다.

나는 25세에 어디에서 무엇을 하였는가? 말년 병장으로 곧 사회인이 되기위해 머리를 기르고 있었다

괴델

- 컴퓨터가 할 수 없는 일도 있다. (불완전성 정리)


제1불완전성 정리 : 적어도 하나의 자연수 이론이 포함된 형식적 체계 안에는 결정 불가능한 공식, 즉 그 자체로 증명이 불가능한 공식이 존재한다.


제2불완전성 정리 : 적어도 하나의 자연수 이론이 포함된 형식적 체계의 무모순성은 해당 체계안에서는 증명될 수 없다.


어머나 이게 도대체 무슨 말이냐 ?? 지금부터는 사람의 언어로 기술해봅시다.


A 라는 어떤 수학적인 영역이 있습니다.

A 영역안에서는 이 공간 자체에 모순이 없다면...

A 영역안에서는 모순된 결론은 절대로 나오지않도록 설계되어 있습니다.


이것이 힐베르트 프로그램이었습니다.

하지만 괴델은 겨우 25세의 나이에 힐베르트 프로그램을 무너뜨립니다.


"X 라는 명제는 A 영역에서는 증명불가능하다"


괴델은 A 영역내에서는 A 영역 자체에 모순이 없다는 사실을 증명할 수 없다는 사실을 밝혀냈습니다.


>> 이것을 우주적인 영역으로 확장하면...


우리 우주 안의 모든 것은 증명할 수 있어도, 이 우주자체가 증명될 수 있는지는(모순이 없는지) 알 수 없다는 것입니다.


이렇게 힐베르트 프로그램의 작은 우주는 무너지게 됩니다.

이 정도가 교양으로써 이해할만한 수준이고,

본격적인 수리논리학의 세계로 들어가면 일반인이 이해하기는 힘듭니다.


>> 거대한 우주에서 벗어나 다시 원론적으로 생각해보면...


A 영역 밖에서 보면 X 는 당연히 참이 된다.

하지만 A 영역안에서는 X 가 참이 된다는 사실을 증명할 수는 없다.


증명은 복잡하니 생략하더라도... 이것이 사실이라는 것을 괴델이 증명한 것입니다.


>> 이제... 이것을 컴퓨터의 세계로 확장해봅시다.


컴퓨터 밖에서는 X 라는 문제를 풀 수 있다.

하지만, 컴퓨터 안에서는 X 라는 문제를 풀 수 없다.


괴델의 발견이 대단한 이유는 다음과 같습니다.


컴퓨터(기계, 로봇 포함)가 할 수 없는 일도 있다.


는 사실을 밝혀낸 것입니다.

7. 앨런 튜링

1912. 06. 23 ~ 1954. 06. 07



마지막 수학자 앨런 튜링입니다.



튜링은 2차대전중 독일군의 이니그마 암호를 해독하는데 결정적인 역할을 했습니다.

이후 튜링이 제안한 튜링 머신은 현대 컴퓨터 프로그래밍을 실제로 구현한 사례가 됩니다.

최초의 튜링 머신은 컴퓨터의 실현 가능성에 대한 명제를 증명하기위해 제안되었다고 합니다.

튜링

- 쓸 수 있는 컴퓨터 프로그램을 제안하다. (튜링 머신)


튜링은 제가 위에서 설명한 다른 수학자들이 만든 이론적 토대를 기초로하여

튜링머신을 만들었습니다.


튜링머신에 대해 간단히 설명해보겠습니다.


94383 이라는 숫자가 있고 이것이 홀수인지 판별하는 튜링머신입니다.

끝없이 긴 테이프가 있고 이 테이프에 94383이 기록되어 튜링머신으로 들어갑니다.


튜링머신은 "시작" 이라는 상태를 가지고 출발합니다.

처음에 튜링머신은 9를 봅니다.

이것이 홀수이기에 튜링머신은 상태를 "홀수" 로 바꿉니다.

다음에 튜링머신은 4를 봅니다. (다음 테이프)

이것이 짝수이기에 튜링머신은 상태를 "짝수" 로 바꿉니다.

다음에 튜링머신은 3을 봅니다. (다음 테이프)

이것이 홀수이기에 튜링머신은 상태를 "홀수" 로 바꿉니다.

다음에 튜링머신은 8을 봅니다. (다음 테이프)

이것이 짝수이기에 튜링머신은 상태를 "짝수" 로 바꿉니다.

다음에 튜링머신은 3을 봅니다. (다음 테이프)

이것이 홀수이기에 튜링머신은 상태를 "홀수" 로 바꿉니다.

다음에 튜링머신은 빈테이프를 봅니다. (다음 테이프)

테이프가 비어있기에 튜링머신은 계산이 끝난 것임을 알고

94383 에 이어지는 다음 빈 테이프에 마지막 상태가 "홀수" 였으므로 1을 기록합니다.

그리고 상태를 "끝" 으로 바꿉니다.


여기서는 테이프가 단방향으로 움직였는데 양방향으로 왔다갔다 하는 식의 조작도 가능합니다.


이것이 튜링머신의 기본입니다.

튜링머신을 제안한 튜링은 튜링머신으로 해결불가능한 문제도 있다는 사실도 증명했습니다.

조금 복잡하고 까다로운 관계로 여기서는 넘어가겠습니다 ^^


이제 수학자들의 이야기가 끝이 났습니다.


여기에 소개된 수학자들은 대부분 상당히 비극적인 최후를 맞이했거나, 말년이 외롭거나 쓸쓸했습니다.

또한, 일부는 살아생전에는 큰 주목을 받지못하기도 했습니다.

이것은 역사속에서 알려진 수많은 천재적 예술가, 과학자들도 비슷하긴 합니다.


1. 라이프니츠는 생전에 다른 사람들에게 존경받을만한 됨됨이가 되지못해, 그의 장례식에는 그의 하인들밖에 없었다고 합니다.


2. 프레게의 수업은 얼마나 재미가 없었는지, 대학에서 그의 수업이 열리면 수강생이 2,3 명에 불과한 경우도 있었다고... 심지어 당대 수학자들도 프레게의 기호논리학에 관심이 없었습니다.


3. 칸토어는 40세부터 대학과 정신병원을 오가는 생활을 시작했으며, 정신병원에서 숨을 거둡니다. 그의 스승인 크로네커는 제자인 칸토어의 주장을 극렬하게 비판했습니다. 칸토어는 말년에 들어서야 크로네커와 화해하고 업적을 인정받게 됩니다.


4. 괴델은 말년에 심한 건강염려증과 피해망상증에 시달려... 누군가 자신을 독살하려 한다고 생각하고, 부인이 만들어 준 음식 외에는 아무것도 먹지않았고, 식음을 전폐하다가 결국 굶어죽습니다. 사망당시 그의 몸무게가 30kg 도 되지않았다고 합니다.


5. 튜링은 동성애자였습니다. 20세기 초중반은 인류학적으로 봤을 때... 이성의 시대로, 이분법적 사고가 인류를 지배하던 시기였습니다. 정치적으로는 좌/우가 극렬하게 대치하던 시기였죠. 극과 극만 있고, 중간은 없었습니다. 당시 동성애자와 같은 성소수자가 위치할 곳은 없었죠. 그는 동성애자라는 이유로 범법자가 되었고, 화학적 거세를 당하고 호르몬 치료를 받다가... 결국 튜링은 가장 여성스러운 방법으로 세상을 떠나겠다며 음독자살하게 됩니다.


참 안타까운 사례가 많지요? 씁쓸합니다 ㅠㅠ

이런 수많은 수학자들의 노력이 있었기에 지금의 컴퓨터, 스마트폰이 존재하는 것이니 참 감사한 일이 아닐 수 없습니다.


일곱 수학자들에 대한 방대한 지식을 압축해서 전달하여, 긴 포스팅이 되었습니다.

이렇게 긴 독서노트를 남겼으니... 이제는 잊지않으리라 하고 다짐을 해봅니다 -..-

김광석의 잊어야 한다는 마음으로

10년전에는 잘 몰랐던 내용들이... 지금 다시보니 더 모르는 것은 우리 뇌의 신비... 허허


현대 컴퓨터는 폰 노이만 컴퓨터라고 부를 정도로 폰 노이만이 컴퓨터에 기여한 부분이 대단히 큰데...

그에 대해서는 또다른 기회에 한 번 포스팅을 준비해보겠습니다.