Skip to content

Posts Gödel, Escher, Bach Chapter V: Recursive Structures and Processes #
Find similar titles

Chapter V. Recursive Structures and Processes

What is Recursion? #

재귀의 사례들:

  • 이야기 안에 이야기
  • 러시아 인형 안에 러시아 인형
  • 재귀적 정의

Pushing, Popping, and Stacks #

재귀를 전산학 관점에서 봤을 때 몇 가지 중요한 용어들:

  • Push
  • Pop
  • Stack

(Stack 자료구조에 대한 설명 생략)

Stacks in Music #

음악에서 나타나는 재귀의 사례 (생략)

Recursion in Language #

자연 언어에서 나타나는 재귀의 사례들.

세상의 모든 언어는 재귀적인 문법 구조를 갖는다. (Transformational grammar by Noam Chomsky)

Recursive Transition Networks #

Recursive transition network 소개

ORNATE NOUN에 대한 RTN:

#!dot/s
rankdir="TB";
"begin" -> "Article" -> "Adjective" -> "Noun" -> "end";
"begin" -> {"Adjective"; "Noun"};
"Article" -> "Noun";
"Adjective" -> "Adjective";

FANCY NOUN에 대한 RTN:

#!dot/s
rankdir="TB";
"begin" -> "Ornate Noun" -> "end";
"Ornate Noun" -> "Relative Pronoun";
"Relative Pronoun" -> "Verb" -> "Fancy Noun" -> "end";
"Relative Pronoun" -> "Fancy Noun'" -> "Verb'" -> "end";
"Ornate Noun" -> "Preposition" -> "Fancy Noun''" -> "end";

위 RTN에서 여러 종류의 재귀가 나타나는 예시:

"the strange bagels that the purple cow without norns gobbled"

"Bottoming Out" and Heterarchies #

재귀적 정의와 순환적 정의(circular definition)의 핵심적 차이는 재귀적 정의에는 항상 "재귀적이지 않은" 경로가 하나 이상 존재해서 바닥을 찍고 올라올 수 있다는 점(bottoming out).

한편, 재귀가 항상 자기 자신을 참조할 필요는 없음. 예를 들면 A는 B를 참조하고, B는 A를 참조하는 식의 재귀도 가능

Expanding Nodes #

RTN에서 재귀적 참조가 일어나는 부분을 시각적으로 확장하는 예시 (생략)

Diagram G and Recursive Sequences #

Tree 형태의 다이어그램을 제시하고 이 다이어그램의 전개 양상이 피보나치 수열과 같음을 보임.

여러 단계로 중첩된 재귀 함수 H(n):

H(n) = n - H(H(H(n - 1))) for n > 0
H(0) = 0

기타 여러가지 재귀 함수 예시들 생략

A Chaotic Sequence #

혼란스러워 보이는 재귀 함수:

Q(n) = Q(n - Q(n - 1)) + (Qn - Q(n - 2)) for n > 2
Q(1) = Q(2) = 1

피보나치 수열과 비슷한데 몇 칸 뒤를 보아야하는지를 재귀적으로 결정하는 방식.

결과로 나타나는 수열에는 규칙이 없어보임. 수열이 진행될수록 더욱 혼란스러움.

이 수열에도 어떠한 규칙성(regularity)이 있을까? 물론 정의가 있으니 규칙이야 있겠으나, 위 정의와 다른 방식으로, 어쩌면 비재귀적인 방식으로 규칙성을 발견할 수 있을 것인가?

Two Striking Recursive Graphs #

저자가 고체물리를 연구할 때 발견한 몇 가지 재귀적 그래프(Fractal)를 소개. (생략)

Recursion at the Lowest Level of Matter #

양자전자역학에서의 재귀성 및 파인만 다이어그램에 대한 설명. (생략)

Copies and Sameness #

Gödel, Escher, Bach/Introduction: A Musico-Logical Offering에서 음악에서 주제를 여러가지 방식으로 변형하는 사례를 살펴본 바 있는데 이 장에서의 재귀에 대한 논의와 유사.

Escher도 이러한 작품을 많이 만든 바 있음:

  • Fish and Scales (figure 36)
  • Butterflies (figure 37)

같은 그림이 반복되어 나타나며 재귀적으로 큰 그림을 이루는 형태.

그런데 여기에서 "같다"는 것은 무슨 의미일까? 에셔 작품에서 반복되는 형태는 그 모양이 정확히 동일하지는 않지만 우리는 이를 "같다"고 여긴다. 다름 속의 같음(sameness in differentness).

언제 두 대상이 같다고 말할 수 있을까? (When are two things the same?)

이 책에서 반복될 주제 중 하나.

Programming and Recursion: Modularity, Loops, Procedures #

프로그래밍의 핵심 스킬 중 하나는 위와 같은 확장된 의미에서 두 프로세스의 동일성(sameness in differentness)을 인식하고 이를 모듈화하여 하위 과업(subtasks)으로 나누는 기술.

예를 들면 반복문을 사용하여 비슷한 작업 반복하기. 이를테면 임의의 자연수 N이 Prime number인지 테스트하기 위해 2부터 N-1까지 반복하며 나눠보기

반복을 일반화하여 기술하면:

특정한 조건(이를 Loop의 Exit condition이라고 함)이 만족되기 전까지 동일한 단계를 반복하기

어떤 경우에는 반복의 횟수를 미리 알 수 있고 어떠한 경우에는 알 수 없음. 저자는 전자를 a bounded loop, 후자를 a free loop로 분류. 이와 관련해서는 Gödel, Escher, Bach/Chapter XIII: BlooP and FlooP and GlooP에서 상세히 설명

루프의 중첩:

  • 루프를 여러 단계로 중첩하는 것도 가능
  • 예를 들면 1부터 5,000 사이의 모든 Prime number를 나열하기

음악에서도 중첩 루프가 자주 나타남:

  • 동일 스케일이 다른 높이로 반복
  • 동일 스케일이 다른 빠르기/여러 악기로 반복

서브루틴(subroutine) 혹은 프로시저(procedure):

  • 루프보다 더 일반적인 방식은 서브루틴(subroutine) 혹은 프로시저(procedure).
  • 일련의 단계에 이름을 부여
  • Recursive transition network을 다룰 때 이미 경험한 방식
  • 모듈화의 핵심

파라메터(parameters):

  • 맥락에 따라 약간씩 다르게 작동하는 서브루틴을 만들려면 파라메터를 부여하거나 메모리의 특정 영역의 값을 참조하도록 함
  • 더 자세한 내용은 18장

Recursion in Chess Programs #

파라메터가 있는 재귀적 프로시저의 고전적인 예시는 Chess에서 최고의 수(move) 찾기:

  • 나의 최고의 수는 상대가 가장 난처해지는 수
  • 상대가 가장 난처해지는 수가 무엇인지 알려면 상대의 다음번 최고의 수를 알아야 함
  • 상대의 다음번 최고의 수를 알려면 나의 다다음번 최고의 수를 알아야 함
  • (반복)

몇 단계 수를 내다볼지를 알려주는 파라메터가 필요. 재귀의 단계를 내려갈때 마다 이 수가 하나씩 감소. 파라메터가 0이 되면 재귀가 일어나지 않도록.

Look-ahead tree:

  • 위와 같이 미리 수를 내다보는 과정에서 보통 "look-ahead tree"가 생성됨 (그림 38 참고)
  • Tree의 모든 경로를 따라 내려가지 않도록 "안봐도 되는 가지"를 찾는 것이 중요. 사람은 잘 하는데 컴퓨터는 잘 못하는 과업 중 하나
  • (책에서 언급하고 있지는 않지만 진화는 가장 추상적인 수준에서 보자면 여러 경로 중 안봐도 될만환 경로를 쳐내는 방식으로 탐색 공간을 좁히는 알고리즘이다)

저자의 재귀적 말장난:

Hofstadter's Law: It always takes longer than you expect, even when you take into account Hosftadter's Law.

Recursion and Unpredictability #

이번 장에서 설명한 재귀적 과정(recursive processes)과 전(Gödel, Escher, Bach/Chapter III: Figure and Ground)에 설명한 Recursive set 사이의 관계는 Recursively enumerable set:

  • 어떠한 집합이 r.e.라는 것은 곧 특정 시작점(axioms)으로부터 동일한 추론 규칙을 반복적으로 적용함으로써 해당 집합을 만들어낼 수 있음을 의미
  • 이게 바로 재귀의 핵심. 모든 원소를 명시적으로 열거하는 대신 자기 자신에 대한 더 단순한 버전을 반복 적용하는 방식으로 정의하는 것. 예를 들면 Fibonacci number.

재귀적 열거:

  • 고정된 규칙들을 기존 것들에 적용하여 새로운 것들을 얻어내는 과정
  • 예측불가능한(unpredictable) 재귀적 열거도 흔하게 나타남. 아마도 그러한 사례들에는 복잡성의 증가 성향이 내제되어 있는 것으로 보임. 더 진행될수록 예측하기 어려워짐
  • 이러한 특성이 바로 지능의 속성 중 하나가 아닐까?
  • 단순히 재귀적으로 호출만 하는 것이 아니라 재귀적으로 "수정"을 하는 프로시저를 생각해본다면? 이러한 엉킨 재귀(Tangled recursion)이 지능의 핵심일 것

Incoming Links #

Related Books #

Suggested Pages #

Other Posts #

0.0.1_20140628_0