Skip to content

Posts Gödel, Escher, Bach Chapter I: The MU-puzzle #
Find similar titles

Chapter I: The MU-puzzle

Formal Systems #

Formal system과 그 사례인 MU-system 소개

Theorems, Axioms, Rules #

용어 정의:

  • Theorems: 정리. 공리에서 시작하여 규칙을 재귀적으로 적용하여 얻어진 문자열들
  • Axioms: 공리. 시작부터 주어진 문자열
  • Rules: 생산 규칙(rules of production) 또는 추론 규칙(rules of inference). 정리 혹은 공리에 적용하여 새로운 정리를 만들어내기 위해 쓰임

Inside and Outside the System #

인간에겐 시스템 밖에서 생각하는 능력이 있음:

  • 생성된 정리들에서 어떤 패턴을 찾아내기
  • 규칙으로부터 패턴을 유추하기. 예를 들어 MU-system에는 제일 앞에 있는 M을 제거할 수 있는 규칙이 없고 MI가 공리로 주어지므로, 이 시스템의 모든 정리는 M으로 시작함

인간과 기계의 차이 중 하나:

  • 정리를 재귀적으로 나열하다가 U를 유도하면 멈추는 프로그램을 작성하기. 안멈춤
  • 인간에게 시키면? 시스템 밖 사고를 통해 U를 얻을 수 없다는 사실을 알아내고 멈춤

주의할 점:

  • 컴퓨터는 체계 밖 사고를 통해 멈출 수 없다는 주장을 하는 것이 아니라
  • 인간은 체계 밖 사고를 안할 수 없다는 주장
  • 컴퓨터도 인간과 마찬가지로 U를 그만찾고 멈추게 만들 수 있을 것
    • 단 모든 알고리즘에 대해서 그렇게 하는 것은 불가능. Halting problem 참고
    • 인간은? 가능한지 불가능한지 모름. 나(강규영)는 불가능하다고 믿음

Jumping out of the System #

컴퓨터도 시스템 밖으로 벗어날 수 있을까?

  • 체스를 두다가 질 것 같으면 포기하는 프로그램
  • "시스템"을 어떻게 정의하느냐에 따라 다를 것:
    • "체스를 두는 것"이 시스템이라면 가능
    • "프로그래밍된 내용을 따르는 것"이 시스템이라면 불가능

M-Mode, I-Mode, U-Mode #

Mechanical mode (시스템 내), Intelligent mode (시스템 밖), Un-mode를 구분하기. Un-mode에 대해서는 나중에 소개.

Decision Procedures #

규칙을 두 종류로 나눌 수 있음: 길게 늘이는 규칙(lengthening rules), 짧게 줄이는 규칙(shortening rules)

온갖 순서로 규칙들을 적용해볼 수 있겠지만 MU가 유도될 수 있다는 보장은 없음.

정리가 아닌 것들을 배제하는 규칙:

  • M으로 시작되지 않으므로 U가 생성될 수 있다는 점은 이미 발견
  • 하지만 MU에 대해서는 그런 단순한 방법으로 정리에서 배제하기 어려움
  • 즉, 첫글자 테스트는 정리가 아닌 문자열들을 "일부" 배제할 수 있으나 모두 배제하는 것은 아님.

정리인지 아닌지를 어떻게 검증할 것인가? 즉, 검증이란 무엇인가?

한 가지 검증 방법:

  • 무한한 시간동안 주어진 규칙을 체계적으로 나열하여 모든 정리를 순서대로 열거(enumerate)하는 지니가 있다고 상상해보자
  • 원하는 문자열이 나왔으면 해당 문자열은 정리
  • 그렇지 않으면 해당 문자열은 정리가 아님

이때 가장 중요한 것은 "유한한" 시간 내에 결과를 얻을 수 있는지 여부. 만약 위 절차가 유한한 시간 내에 "예/아니오" 결과를 낼 수 있다면 위 절차는 MU-system에 대한 Decision procedure.

Decision procedure이 정의:

  • 어떤 Formal system에 대하여, 특정 문자열이 정리인지 아닌지를 유한한 시간 내에 답할 수 있는 절차

Decision procedure가 있다면 해당 시스템을 매우 구체적으로 특징지을 수 있음(characterize).

규칙과 공리도 암묵적으로 시스템의 특징을 어느 정도 알려주지만 충분히 구체적이지 않음.

MU-system의 공리와 규칙은 단순하지만 이 시스템을 특징짓기는 어려움.

Incoming Links #

Related Books #

Suggested Pages #

Other Posts #

0.0.1_20140628_0