[원리] 수학자, 컴퓨터를 만들다

 

수학자, 컴퓨터를 만들다.

-       마틴 데이비스 지음

 

 

<<

어떤 것이 계산 가능할까? 계산 가능하다는 건 무엇일까?

컴퓨터 프로그램을 처음 알았을 때부터, 처음에는 어떻게 프로그램

아이디어를 떠올렸을까? 이런 의문이 있었다.

 

‘수학자, 컴퓨터를 만들다.’를 보았을 때 이런 의문에 답을 해줄지 않을까

했었는데, 생각보다 재미있었고, 또한 혼란하게 만들었으며, 책을 몇번이나

읽게 만들었다. 하지만 몇가지 의문 해결은 또 다른 의문을 남기고

머리가 좋지 못함이 한스러웠다.

>>

 

ㅁ 라이프니츠

- 인간 이성을 계산으로 환원하는 것, 그리고 계산을 실행할 걍력한 기계를 꿈꾼다.

 

ㅁ 프레게

- 인간의 모든 연역적 추론을 그럴듯하게 설명할 수 있는 규칙 체계를 마련

 

ㅁ 괴델

- 프레게의 규칙이 완전하다고 증명

 

ㅁ 힐베르트

- 1차 논리학이라고 불리게 되는 것의 기호법으로 씌어진 몇몇 전제들과 제시된 결론이 주어졌을 때 프레게의 규칙들이 그 결론이 전제들에서 유도되게끔 할 수 있는지를 언제나 결정할 수 있게 해 주는 명백한 계산 절차를 추구했다.(힐베르트의 결정 문제) 기존 수학들도 계산절차와 알고리즘으로 이루어져 있으나, 힐베르트는 전례가 없었던 범위의 알고리즘을 요구하고 있었다. 원칙적으로 그의 결정 문제에 대한 알고리즘에 따라 모든 인간의 연력적 추론은 단순한 계산으로 환원될 것이다.

 

 

ㅁ 라이프니츠

인간이 생각하는 것을 정학하게 나타내는 알파벳과 이런 기호를 다루는 데 알맞은 연산도구를 발견하려는 생각을 했다. 그는 산술과 대수에서 쓰는 특별한 문자들, 확학과 천문학에서 쓰는 기호들, 그리고 자신이 도입한 미분과 적분 계산 기호들 모두가 참으로 적절한 기호법이 얼마나 결정적으로 중요할 수 있는지를 보여 주는 범례들이라고 확신했다. 라이프니츠는 그런 문자체계를 기호 체계라고 불렀다. 아무 뜻이 담겨 있지 않은 알파벳 기호들과 달리, 지금 언급된 보기들은 그가 생각하기에 각각의 기호가 자연스럽고 적절한 방식으로 어떤 분명한 생각을 나타내는 실제 기호 체계였다. 이제 필요한 것은, 라이프니츠가 주장한 대로 보편 기호 체계, 즉 실제 세계의 기로 체계일 뿐만 아니라 인간의 모든 사고 범위를 포괄하는 기호의 체계였다.

 

 라이프니츠는 추론 계산법을 만들었다. 다음은 그 일부이다.

------------------------------------------------------------------------------------

정의 3. A 가 L에 속하거나, L 이 A 를 포함한다는 것은, A 를 비롯한 다수의 항들이 합쳐진 것과 일치하게 L 이 만들어질 수 있다고 말하는  것과 같다. B○+N=L 에 속하고 B 와 N 이 함께 L 을 합성하가나 구성한다는 것을 의미한다. 이것은 휠씬 더 많은 항들에 대해서도 똑같이 적용될 수 있다.

공리1. B○+N=N○+B

공준. A 와 B 같은 어떤 다수의 항들이 더해져 단일한 항 A○+B 를 구성할 수 있다.

공리2. A○+A=A

명제5. 만약 A 가 B 에 속하고 A=C 이면, C 는 B 에 속한다.

       명제 A 가 B 에 속한다에서 A 에 C 를 대입하면 C 는 B 에 속한다가 나오기 때문에.

명제6. 만약 C 가 B 에 속하고 A = B 이면, C 는 A 에 속한다.

       명제 C 가 B 에 속한다엣 B 에 A 를 대입하면 C 는 A 에 속한다가 나오기 때문에.

명제7. A 는 A 에 속한다.

       (정의 3 에 따라) A 는 A○+A에 속하기 때문에 그러므로 (명제9에 따라) A 는 A 에 속한다.

명제20. 만약 A 가 M 에 속하고 B 가 N 에 속하면, A○+B 는 M○+N 에 속한다.

-------------------------------------------------------------------------------------

 

 

 

ㅁ 불의 논리대수

 일반대수에서 x가 하나의 수를 패표한다면, 식 xx=x 가 참일때는 x 가 0 또는 1 이고, 그 밖의 수가 아닐때 참이다. 이것을 통해 불은 만약 그 값을 0과 1 구 개의 값으로 제한한다면 논리 대수는 일반 대수의 연산과 정확히 일치한다는 원리를 알게 되었다.

 

 이것을 기호 0,1을 집합으로 해석하게 되었다.

0에 어떤 수를 곱해도 0 이다. 1에 어떤 수를 곱해도 바로 그 수이다.

0x=-0,  1x=x

0을 아무것도 속하지 않는 집합으로 해석하면, 0x응 모든 x에 대하여 0과 일치할 것이다.

 

일반대수와 같이 덧셈,뺄셈도 다룬다. x,y가 두개의 집합을 나타날때 

x에 있거나 y에 있는 모든 것들의 집합(합집합) x+y

x에 속하지만 y에는 속하지 않는 것들의 집합 x-y

1-x 는 x에 속하지 않는 것들의 집합

x + (1 - x) = 1

xx를 x²이라고 하면 기본 규칙에 따라 x²=x 또는 x-x²=0 이된다.

다음과 같이 인수분해되는데

x(1-x)=0

이것은 어떤 것도 주어진 집합 x에 속하면서 동시에 속하지 않을 수는 없다.

는 결과를 나타냈다.

 

(불의 인용-아리스토텔레스의 형이상학)

그것은 아리스토텔레스가 모든 철학의 근본적인 공리하고 표사했던 "모순율"이다.

"어떤 특성이 어떤 물질에 속하면서 속하지 않는 것은 불가능하다. ....

이것은 모든 원리 중 가장 확실하다. ...........

그런 까닭에 논증하는 사람들은 이것을 궁극적 판단으로 간주한다. 그것은

본래 다른 모든 공리들의 근원이기 때문이다.

 

불의 다른 예

전제:

1. 어떤 것이 있다.

2. 만약 어떤 것이 있다면, 어떤 것은 항사 있거나, 아니면 지금 있는 것들은 무에서 생겨났다.

3. 만약 어떤 것이 있다면, 그것은 자신의 본성에 따라 필연적으로 존재하건나, 아니면 다른 존재의 의지에 의해 존재한다.

4. 만약 그것이 자신의 본성에 따라 필연적으로 존재한다면, 어떤 것은 항상 있었다.

5. 만약 그것이 다른 존재의 의지에 의해 존재한다면, 지금 있는 것들이 무에서 생겨났다는 가정은 거짓이다.

 

1. x = 어떤 것이 있다.

2. y = 어떤 것이 있다.

3. z = 지금 있는 것들은 무에서 생겨났다.

4. p = 이것은 자신의 본성(즉, 위에서 말한 어떤 것)에 따라 필연적으로 존재한다.

5. q = 이것은 다른 존재의 의지에 의해 존재한다.

 

1. 1 - x = 0

2. x { y z + ( 1 - y ) ( 1 - z ) } = 0

3. x { p q + ( 1 - p ) ( 1 - q ) } = 0

4. p ( 1 - y ) = 0

5. q z = 0 

 

조지 불의 위대한 성취는 논리적 연역이 수학의 한 갈래로 발전할  수 있다는 것을 완전히 증명한 것이었다.

비록 아리스토텔레스의 선구적 연구 이후에 논리학에서 몇 가지 발전이 (특히 헬레니즘 시대의 스토아학파에 의해

그리고 유럽에서 12세기 스콜라 철학자들에 의해) 이루어졌지만, 불은 아리스토텔레스가 2천면 전에 남긴 주제의

본질적인 측면을 찾아냈다.

 

ㅁ 프레게

프레게의 개념 표기법

1879년 소책자(부재:개념 표기법, 산술적으로 묘산된 순수 사유의 형식 언어"

- '아마도 논리학에서 이제까지 저술된 단일 저작 중 가장 중요한 것'으로 간주 됨. 

- 프레게는 자신의 논리학을 토대로 하여, 수학의 다른 분야들과 마찬가지로 대수를 상부 구조로 세우려고 했기 때문에

  혼란이 일어나는 것을 막기 위해 논리적 관계를 나타내는 자신이 만든 특수한 기호들을 도입하는 것이 중요하다고

  여겼다.

- 명제들을 연결하는  그와 같은 관계들이 또한 개별 명제들의 구조를 해석하는 데 사용될 수 있다고 보았다.

   이 관계들을 자신의 논리학 기초로 삼았다. 이것은 현대 논리학의 기초를 형성하고 있다.

 

1) 모든 말들은 포유동물이다.

-> 만약 x 가 말이면, x는 포유동물이다.

2) 어떤 말들은 순종이다.

-> x는 말이고, x는 순종이다.

1)은 모든 x에 대해 참이라고 함.

2)는 어떤 x에 대한 주장

모든 ~에대해서는 ∀, 어떤 ~에 대해서는 ∃로 쓴다.

1)->(∀x)(만일 x가 말이면, x는 포유동물이다.) - 보편 양화사(universioal quantifier)

2)->(∃x)(x는 말이고, x는 순종이다.) - 존재 양화사(existential quantifier)

 

논리적 관계

만일 ~ 이면 ~ 이다. -> ⊃

~ 이고 ~ 이다. -> ∧

 

1) (∀x)(말(x) ⊃ 포유동물(x))

2) (∃x)(말(x) ∧ 순종(x))

 

더 간략히 하면

1) (∀x)(b(x) ⊃ m(x))

2) (∃x)(b(x) ∧ p(x))

 

￢ ~ 아니다

∨ ~ 또는 ~

∧ ~이고 ~이다

⊃ 만일 ~이면 ~ 이다

∀ 모든

∃ 어떤

 

모든 실패한 학생들은 어리석거나 게으르다.

x는 실패한 학생이다.  F(x)

x는 어리석다.            S(x)

x는 게으르다.            L(x)

 

(∀x)(F(x) ⊃ S(x) ∨ L(x))

프레게가 단지 논리학의 수학적 처리법만 발전시킨 것이 아니라 실제로 새로운 언어도 창조

라이프니츠의 보편언어 개념을 지침으로 함.

 

불의 논리학은 일반 수학적 방법들을 사용하여 발전시킨 또 하나의 수학 분야일 뿐이었다.

이것은 논리적 추론의 사용을 포함한다. 그러나 논리를 전개하기 위해 논리를 사용하는

것에는 순환하는 무엇인가가 있다. 프레게는 이것을 받아들일 수 없었다.

 

  그의 의도는 어떻게 수학의 모든 분야가 논리학에 토대를 둘 수 있는지 보이는 것이었다.

논리를 사용하지 않고 자신의 논리를 전개하는 어떤 방식을 찾아야만 했다.

 

그 방법은 개념 표기법을 문법 또는 구문론이라는 엄격하게 정밀한 규칙을 가진 인공 언어로

발전시키는 것이었다. 이를 통해 논리적 추론을 기호들이 배열된 방식에만 관련 있는 순수하게

기계적인 조작, 이른바 추론 규칙으로 나타내는 것이 가능하게 되었다. 그것은 또한 정밀한

구문론 으로 짜여진 형식 인공 언어의 첫 번째 예였다. 이런 관점에서 볼 때, 개념 포기법은

오늘날 일반적으로 사용되는 모든 컴퓨터 프로그래밍 언어의 선조였다.

 

프레게의 논리학은 수학과, 컴퓨터학과, 철학과 등에서 하는 논리학 강의 과정에서 표준

논리학이 되었다. 그것은 엄청난 내용의 연구를 위한 기초가 되었고 간접적으로 앨런 튜링이

만능 컴퓨터에 대한 착상을 정식화하도록 해 주었다.

 

프레게의 논리학은 처음으로 수리 논리학의 정확한 체계가 적어도 원칙적으로는 수학자들이

일반적으로 사용하는 모든 추론을 포괄하게 되었다.

 

프레게의 논리학에 있는 몇몇 전제들로 시작하면 원하는 결론에 도달하기 위한 시도에

프레게의 규칙이 적용될 수 있을 것이다. 그러나 만약 시도가 실패할 수 있는지를

제공하지 못했다.

 

러셀의 역설

러셀은 프레겡게 모든 일반적 집합들의 집한 E를 제시했다. E는 일반적인가 예외적인가?

그것은 둘 중 하나여야 한다. 그러나 어느 쪽도 아닌 것 같다. E는 일반적일 수 있는가?

만약 그렇다면, E는 모든 일반적 집합들의 집합이므로, 자기 자신에 속하게 될 것이다.

그렇게 되면 집합 E는 예외적인 집합이 되어 버린다. 그러면 E는 예외적이어야 한다.

따라서 집합 E가 일반적 집합들의 집합이므로, 자기 자신에 속하지 않아야 할 것이다.

그러나 그렇게 되면 집합 E는 일반적 집합이 되어 버린다. 오느 쪽 길을 택해도 모순에

빠져 버린다.

 

ㅁ 칸토어

-

 

ㅁ 힐베르트

 

 

ㅁ 계산 과정에 대한 튜링의 분석

 튜링은 알고리즘이 마치 요리책에 나오는 조리법처럼, 누구나 정확한 기계적 방식으로

따를 수 있는 일련의 규칙들로 으레 규정된다는 것을 알고 있었다. 그는 초점을 규칙에서

, 사람이 그 규칙을 실행할 때 실제로 하는 행위로 돌렸다.

사람의 동작을 몇 가지 매우 단순한 기본 동작으로 제한할 수 있을 보여 줄 수 있었다.

 

     4231

X  77

-------

  29617

296170

 -------

325787

 

를 계산한다고 할 때, 사람이 계산을 하는 것은 어떻게 하는 것일까?

4

2

3

1

X

7

7

=

2

9

6

1

7

+

2

9

6

1

7

0

=

3

2

5

7

8

7

 

 

위와 같이 네모칸이 그려진 종이 테이프를 따라서 작업하는 모습을 상상할 수 있다.

 

계산을 실행하는 사람은 다음의 제약들을 받으면서 작업을 수행한다.

-       계산의 각 단계에서는 오직 적은 수의 기호들만 주목받는다.

-       그와 같은 각 단계에서 일어나는 행동은 주목받는 특정한 기호들과 계산을 실행하는 사람의 현재 마음 상태에만 달려 있다.

 

어떤 계산도 다음의 방식으로 진행되는 절차하고 생각할 수 있다는 결론을 얻게 된다.

-       계산은 네모칸이 그려진 종이 테이프 위의 네모칸 안에 기호를 써서 실행된다.

-       각 단계에서 계산을 수행하는 사람은 정확히 이 네모칸들 중 하나에 적힌 기호에 주의를 기울인다.

-       여자의 다음 행동은 이 기호와 사람의 마음 상태에만 달려 있다.

-       앞서 말한 다음 행동에는 여자가 주의를 기울여 온 네모칸에 기호를 쓰는 행위도 포함될 것이고, 그리고 나서 아마도 즉각 왼쪽 아니면 즉각 오른쪽의 네모칸으로  주의를 돌리는 행위도 포함될 것이다.

 

특정한 튜링 기계가 존재하는 데 필요한 것은 무엇인가?

-       기계의 가능한 상태를 모두 보여 주는 목록이 필요한다.

-       각각의 상태들과 테이프 위에서 만나게 될 각각의 기호에 관해, 그 기호를 만났을 때 그 상태에서 일어날 기계의 작동을 지정하는 것이 필요하다.

 

이를 정리하면

-       기계가 상태 R에서 테이프 위의 기호 a를 읽어 들일 경우, 기계는 a를 b로 바꾸고, 오른쪽으로 한 칸 옮긴 다음, 상태를 S로 바꾼다.

 

 

라는 서술을 공식

R a:b -> S

로 기호화할 수 있다.

 

완쪽으로 한 칸 옮기라는 서술은

R a:b <- S

 

좌우로 움직이지 않고 테이프 위에서 기호를 바꾸하는 거술은

R a:b ★ S

 

이렇게 공식 하나를 열거하는 데 다섯 개의 기호를 쓰기 때문에 보통 5순서열(quintuples)이라고 한다. 이와 같이 5순서열의 목록이 제공된다면 어떤 특정한 투링 기계라도 시현될 수 있다.

 

이런 부호들을 십진 숫자열로 바꾼다. 처음과 끝이 8이고 중간이 0~9의 숫자열을 그리고 다른 기호에 대한 숫자열을 만든다.

기호	표현	기호	표현
0 1 2 3 4 5 6 7 8 9	8008 8018 8028 8038 8048 8058 8068 8078 8088 8098	□ → ← ★ : ;	8558 616 626 636 646 77

 

 

Q 1:1 -> Q ; Q 2:2 <- Q

998018 646 8018 616 99 77 998028 646 8028

이런식으로 기호를 숫자열로 변환다.

<<어디서 많이 본듯한 모양이 되었는데, 2진수로 되어 있는 기계어 코드를 10진수로 바꾼 모습과 비슷하다>>