Skip to content

Posts Gödel, Escher, Bach Chapter III: Figure and Ground #
Find similar titles

Chapter III. Figure and Ground

Primes vs. Composites #

MU-system, pq-System에서 살펴본 바와 같이 활자 조작(typographical manipulations)을 통해 개념을 담아낼 수 있다.

더 복잡한 개념에 대해서도 가능할까? 이를테면 소수(Prime number)만을 열거하는 규칙을 위와 같은 시스템으로 나타낼 수 있을까? (예를 들어 P---는 정리이고 P----는 정리가 아님)

그 전에 "활자 조작"이란 정확히 무얼 말하나?

  1. Reading and recognizing any of a finite set of symbols;
  2. Writing down any symbol belonging to that set;
  3. Copying any of those symbols from one place to another;
  4. Erasing any of those symbols;
  5. Checking to see whether one symbol is the same as another;
  6. Kepping and using a list of previously generated theorems.

The list is a little redundant, but no matter. What is important is that it clearly involves only triial abilities, each of them far less than the ability to distinguish primes from nonprimes.

The tq-System #

소수에 대한 형식 체계를 다루기 전에 관련된 좀 더 단순한 시스템을 소개하겠음. 더하기가 아닌 곱하기를 나타내는 시스템인 tq-System.

  • Axiom Schema: xt-qx is an axiom, whenever x is a hyphen-string.
  • Rule of Inference: Suppose that x, y and z are all hyphen-strings. And suppose that xtyqz is an old theorem. Then xty-qzx is a new theorem.

Capturing Compositeness #

이제 tq-System을 확장하여 합성수 개념을 Cx 형태로 표현하는 형식 체계를 도입해보자:

  • Rule: Suppose x, y, and z are hyphen-strings. If x-ty-qz is a theorem, then Cz is a theorem.

즉, 1보다 큰 두 수(x-, y-)의 곱으로 표현되는 모든 수는 합성수.

Illegally Characterizing Primes #

소수 개념을 Px 형태로 표현하는 잘못된 방법:

  • Rule: Suppose x is a hyphen-string. If Cx is not a theorem, then Px is a theorem.

즉, 합성수가 아니면 소수라는 뜻.

하지만 무언가가 정리가 아닌지 확인하는 것은 "간단한 활자 조작" 범주에 들어가지 않으므로 이는 적절한 형식화가 아님.

시스템에 따라 "정리가 아닌 것"의 목록을 나열하는 것이 쉬울 수도 있고 어려울 수도 있음.

Figure and Ground #

정리를 나열하는 방식의 정의하는 것과(positively defined) 정리인 것을 뺀 나머지라는 식으로 정의하는 것(negatively defined)의 차이는 예술에서의 배경과 전경 구분과 유사.

전경을 그린 결과 배경이 부산물로 나타나는 종류의 그림을 "cursively drawable"이라고 정의.

배경이 그 자체로 전경 역할도 하는 종류의 그림을 "recursively drawable"이라고 정의.

Figure and Ground in Music #

J. S. Bach의 음악들은 이런 의미에서 대체로 "recursive"

Recursively Enumerable Sets vs. Recursive Sets #

There exist format systems whose negative space (set of non-theorems) is not the positive space (set of theorems) of any formal system.

(책에서 아직 왜 그런지에 대해서는 설명되지 않았음)

위 표현을 더 기술적으로 정확하게 하면 아래와 같음:

There exist Recursively enumerable sets which are not Recursive sets.

이는 곧 어떤 형식 체계에는 결정 절차가 존재하지 않음을 의미. 왜?

  • 어떤 형식 체계에 대하여 결정 절차가 존재한다면 해당 형식 체계의 알파벳을 조합한 모든 문자열을 나열함으로써 정리와 비정리를 열거할 수 있음
  • 하지만 (아직 설명하지 않은 이유로 인해) 어떤 형식 체계는 비정리를 나열할 수 없음. 즉 어떤 형식 체계는 recursive 하지 않고 recursively enumerable 하기만 함
  • 따라서 어떤 형식 체계에는 결정 절차가 없음을 의미함

Primes as Figure Rather than Ground #

소수를 열거하는 형식 체계 정의하기

우선 does not divide (DND) 개념을 정의:

  • Axiom Schema: xyDNDx where x and y are hyphen-strings. (x+y does not divide x)
  • Rule: If xDNDy is a theorem, then so is xDNDxy. (if x does not divide y, then x does not divide x+y)

다음으로, 이에 기반하여 "어떤 수 Z는 어떤 수 X 이하의 어떤 수로도 나누어지지 않는다" 개념을 정의(the number Z is divisor-free up to X):

  • Rule: If --DNDz is a theorem, so is zDF--. (2 does not divide z, z is divisor-free up to 2)
  • Rule: If zDFx is a theorem and also x-DNDz is a theorem, then zDFx- is a theorem. (If z is divisor-free up to x, and if x+1 does not divide z, then z is divisor-free up to x+1)

마지막으로 자기 자신보다 1 작은 모든 수에 대해 divisor-free인 수를 소수로 정의하면 끝:

  • Rule: If z-DFz is a theorem, then Pz- is a theorem. (If z+1 is divisor-free up to z, then z+1 is a prime.

2는 소수이므로 공리로 지정하고 시작:

  • Axiom: P-- (2 is a prime)

여기에서 가장 중요한 것은 시스템의 단조성(monotonicity) 혹은 단방향성(unidirectionality). 즉, 가장 작은 수에서 시작해서 하나씩 올라가는 규칙만 존재.

이러한 성질이 부재가 다음의 원인:

Incoming Links #

Related Books #

Suggested Pages #

Other Posts #

0.0.1_20140628_0