다시 김도형의 홈 페이지로
수행의 추상화(executional abstraction)는 `알고리즘'이라는 개념 전체를 위해 너무나 기초적인 것이기 때문에, 대개 당연한 일로 생각하고 언급하지도 않곤 한다. 그것의 목적은 상이한 계산(computation)을[역주: 여기서 `계산(計算)'이란 특정한 하나의 문제를 푸는 과정을 뭉뚱거려서 지칭한다. 예를 들어서 정렬(sorting) 알고리즘이 있을 때, 특정한 하나의 입력(예컨대, 한 학급 학생들의 시험 성적)이 이 알고리즘에 주어져서 수행되면 하나의 계산이 되는 것이다.] 상호 사상(mapping)시키는 것이다. 혹은 달리 표현하자면, 특정한 하나의 계산을 다른 계산들로 이루어진 큰 집단의 한 구성원으로 생각함으로써 그 의미를 잘 파악하는 방법을 말한다. 이것은 그 집단의 구성원들 간의 차이를 집단 전체의 정의(定義)에 근거하여 추상화시켜[역주: 추상화의 사전적인 의미는 `어떤 특정 범위의 물체나 개념에서 가장 중요하고---무엇이 중요한가는 그들을 둘러싼 공간적, 시간적인 외부 환경에 따라서 다르다---공통적인 속성(屬性)을 추출하는 것' 또는 `주어진 문제에서 특정한 목적에 관련된 필수적인 정보만을 추출하고 기타 정보는 무시하는 관점'이다. 추상화는 `일반화(generalization)'와도 비슷한 뜻으로 쓰이고, 그 반의어는 각각 `구체화(concretization)'와 `개체화(specialization 또는 instantiation)'라고 할 수 있다. 예를 들어, `개'와 `말' 그리고 `고양이'의 집단을 `동물' 또는 `포유류' 또는 `인간과 가까운 동물' 등등으로 추상화시킬 수 있다. 당연한 얘기지만 이 추상화라는 개념은 인간의 지적 성취를 조직화(粗織化)시키는 데 있어서 대단히 중요하고 유용한 것이며 광범위하게 사용되고 있다---우리가 의식을 하든 하지 않든 간에.] 각 구성원에---따라서 우리가 고려하고 있는 그 특정 계산에 대해서도---적용할 수 있는 단정(assertion)을[역주: `단정(斷定)'은 소프트웨어 공학(software engineering)이나 알고리즘 분석(algorithm analysis) 분야에서 자주 등장하는 개념이다. 그럴 때의 뜻은 `알고리즘과 관련해서 자료 설계, 프로그램 작성, 또는 처리 작업 등에 관계되는 내용이나 조건에 대한 가정이나 예상'을 말하고, 주로 프로그램 검증(program verification)에 사용된다. 여기서도 본질적으로는 같은 뜻이지만, 일단 `어떠한 성질을 갖추고 있다거나 특정 조건을 만족한다는 혹은 그럴 것이라는 서술' 정도로 생각하면 되겠다.] 하는 식으로 이루어진다.[역주: 곧 예가 나오겠지만, 어떤 문제를 위한 알고리즘을 설계해야 할 경우, 우리는 먼저 그 문제를 추상화시켜 그것이 보다 일반적인 문제 집단의 한 구성원이 되도록 하여 알고리즘을 설계한다. 어떤 면에서 보면 문제를 더 크게 만들었다고 할 수도 있으나, 그러한 추상화를 통해서만이 유용성과 정합성이 있는 해를 용이하게 구할 수 있다.]
`계산'이 의미하는 바를 제대로 납득하기 위해서, 예컨대 111과 259의 최대 공약수를 `생산(生産)하는'---의도적으로 `계산하는'이란 단어를 피했다---어떤 비계산적(noncomputational) 메커니즘(mechanism)을 생각해 보자. 이 메커니즘은 두 장의 판지가 겹쳐져서 이루어진다. 위의 판지에는 `GCD(111, 259) ='이란 문자가 씌어져 있다. 그 메커니즘이 답을 만들어 내도록 하기 위해서는 위의 판지를 집어서 아래에 있는 판지의 왼편에 놓는다. 아래 판지의 위에는 `37'이라는 문자가 씌어져 있다.
위의 판지 메커니즘은 단순성이라는 큰 장점을 가지고 있으나, 두 가지 결점---하나는 상대적으로 작은 문제이고 다른 한 가지는 더욱 심각한 문제이다---때문에 그 장점이 무색해졌다.[역주: 이 판지 메커니즘의 두 가지 문제점 혹은 단점이 무엇일까? 책을 계속 읽어 나가기 전에 잠시 생각해 보는 것이 좋겠다.] 상대적으로 작은 결점은, 그 메커니즘이 111과 259의 최대 공약수를 만들어 내는데는 사용할 수 있으나 다른 목적으로는 거의 쓸모가 없다는 것이다.[역주: 독자들이 생각한 비교적 작은 문제점이 이것이었는가?] 그러나 보다 심각한 문제점은 우리가 아무리 주의깊게 그 메커니즘의 구조를 조사한다고 하더라도, 그것이 과연 옳은 답을 만들어 내는가에 대한 우리들의 확신은 (그 메커니즘의) 제작자에 대한 믿음에 의존할 수 밖에 없다는 것이다.[역주: 이것이 더 심각한 문제라는 것은 명백하다. 111과 259의 최대 공약수가 37이 맞다고 한다면 그 메커니즘은 비록 그 한 쌍의 숫자들의 경우만 최대 공약수를 구할 수 있지만, 그 답은 옳은 것이고 그 메커니즘은 제대로 동작하는 것이다. 그러나 그 답의 정확성에 대해서 확신을 가질 수 없다면, 아무리 많은 숫자들의 쌍에 대한 최대 공약수를 말해 주는 메커니즘이라 하더라도 무용지물(無用之物)일 것이다. 해역자의 생각으로는 대부분의 사람들은(해역자까지 포함해서) 처음에 아마도 첫번째의 문제점을 심각한 문제점으로 생각했을 법하다. 그리고 또 다른 문제점이라는 것은 생각해 내지 못했을 지도 모르겠다. 만약 그렇다고 한다면, 사소한(따라서 작은) 문제점을 큰 것보다 쉽게 생각해 낸 이유는 무엇일까? 그것은 우리가 기본적으로 이러한 메커니즘이 주어져 있다는 말을 들으면, ``어떻게 만들지?''하는 생각을 잠시 하지만 그 다음엔 그것이 옳게 동작한다는 것을 쉽게 가정해 버리고 정확성에 대한 의문을 잊어 버린다는 것이다. 반면에 다익스트라는 그것을 잊어 버리고 앞으로 나아갈 수 없는 것이다.] 그 제작자는 그 메커니즘의 기본 설계 도중이나, 우리가 가지고 있는 (그 메커니즘) 복사본의 생산 과정에서 실수를 했을 수도 있을 것이다.
위의 비교적 작은 문제점을 극복하기 위해서는 아주 큰 판지로 이루어진 새로운 메커니즘을 생각할 수 있을 것이다. 판지 위에는 수평축 위의 점 x(0 ≤ x ≤ 500)와 수직축 위의 점 y(0 ≤ y ≤ 500)에서 각각 수직선과 수평선을 그음으로 인해서 만들어지는 격자(格子) 무늬가 그려져 있다. 이렇게 해서 만들어지는 격자의 교점 251,001개의 (x, y) 중에서 양의 값만을 좌표로 가지는, 즉 축 위에 있는 점들을[역주: 그 갯수는 x-축 위에 500개, y-축 위에 500개, 그리고 원점을 합하여 1,001개다.] 제외한 나머지 것들 위에 그 점 (x, y)의 최대 공약수 GCD(x, y)가 쓰여져 있는 형태의 메커니즘이다. 우리는 250,000개의 목록을 포함하고 있는 2차원 표를 제안하고 있는 것이다. 유용성이라는 관점에서 보면 이것은 대단한 개선이다. 한 쌍의 숫자들에 대한 최대 공약수를 제공할 수 있는 메커니즘 대신에, 이제 250,000개의 숫자들 쌍 중에서 임의의 것에 대한 최대 공약수를 제공할 수 있는 `메커니즘'을[역주: 여기서 메커니즘을 따옴표로 둘러싼 것은 이러한 형태도 엄연히 `메커니즘'이 될 수 있다는 뜻이다. 현재의 메커니즘은 기계적인(mechanical) 움직임을 보여 주는 부분이 없다. 이에 반해 처음의 메커니즘---판지 두 장으로 이루어진 메커니즘---에는 위의 판지를 들어서 옮겨 아래 판지를 드러내는 기계적인 부분이 있다. 당연한 얘기지만 여기서 사용하는 메커니즘이란 단어는 `추상적인 또는 개념적인 기계'를 나타내므로, 두번째로 제시된 것도 훌륭한 메커니즘이 된다. 만약 기계적인 움직임을 보일 필요가 있다면 그런 형태로 변형시킬 수도 있을 것이다.] 가지게 되었으니 말이다. 훌륭하다. 허나 너무 흥분하지는 말라. 왜냐하면 우리가 두 번째 결점이라고 한 것---``그 메커니즘이 옳은 답을 만든다고 왜 믿어야지?''---은 거꾸로 250,000배나 증폭되어 버렸기 때문이다. 이제 우리는 그 메커니즘의 제작자에 대해 보다 큰,[역주: 250,000배의?] 엄청난 신뢰를 가져야만 한다!
따라서, 또 다른 다음 메커니즘을 생각해 보자. 격자점들이 있는 것과 같은 형태의 판지 위에, 두 개의 축을 따라서 1부터 500까지의 값들이 씌어져 있다. 그 외 다른 숫자들은 없다. 그리고 추가로 다음과 같은 직선들이 그어져 있다:
이 기계를 작동시키기 위해서는, 다음과 같은 지시 사항을 따른다(``다음 규칙에 의거해 게임을 한다''고 생각할 수도 있을 것이다). 두 개의 값 X와 Y의 최대 공약수를 찾고 싶으면, x-좌표값은 X, y-좌표값은 Y인 격자점 위에 조그만 조약돌 같은 것---역시 (이 기계의) 제작자가 공급한---을 놓는다. 그 조약돌이 `해답선' 위에 위치하지 않는 경우, 우리는 먼저 그 판지 위에 다음과 같은 조건을 만족하는 것들 중에 가장 작은, 하나의 가상적인 직각 이등변 삼각형이 있다고 생각한다. 그 삼각형의 직각은 조약돌 위에 겹쳐지고, 하나의 예각(조약돌 아래나 혹은 왼쪽 방향에 있는)의 꼭지점은 두 개의 축 중 하나 위에 놓여진다. 그 다음 조약돌을 움직여서 그 삼각형의 다른 예각의 꼭지점이[역주: 축 위에 있는 예각의 꼭지점이 아닌 다른 예각의 꼭지점을 말한다.] 위치하는 격자점으로 옮긴다. 이러한 조약돌의 위치 변경을 그것이 해답선 위에 올 때까지 반복하는 것이다. 조약돌이 해답선 위에 놓여지면, 그 때의 x-좌표(혹은 y-좌표)가 우리가 원하는 답이다.[역주: 즉 X와 Y의 최대 공약수이다. 독자들도 알겠지만, 이 메커니즘이 바로 유클리드(Euclid)의 최대 공약수를 구하는 알고리즘을 기하학적으로 변형시킨 것이다. 유클리드의 호제법(互除法)이라고 부르는 그 알고리즘이다. `호제'란 단어 뜻 그대로 `서로 번갈아가면서, 빼(제해) 나가는' 방법이다. 오늘날에는 유클리드의 호제법을 사용해서 최대 공약수를 구하는 경우에도, 빨리 답을 구하기 위해서 빼기 대신에 나누기를 사용하는 약간 변형된 형태를 흔히 사용한다(한 번 나누는 것은 젯수를 피젯수로부터 여러 번 빼는 것이기 때문에). 독자들도 중고등학교 시절에 배웠을 것이다.]
이 기계가 바른 답을 만들어 낸다는 것을 우리 스스로가 납득할 수 있도록 해 주는 사항들은 어떤 것일까? 만약 (x, y)가 해답선 위에 있지 않은 249,500개의 점들 중 하나이고 조약돌이 위의 게임(의 규칙)에 따라 다음 한 단계에서 이동될 목표 지점이 (x', y')이라고 한다면, x' = x이고 y' = y - x이던지, x' = x - y이고 y' = y이다. 이런 경우 GCD(x, y) = GCD(x', y')임을 증명하는[역주: 여기서 글씨체를 달리 한 것은 이 새롭게 구성한 메커니즘의 경우는 그 정합성에 대해서 (메커니즘의 제작자에 대한) 감정적인 신뢰가 아닌 논리적인 추론의 문제로 접근할 수 있음을 강조하고자 하는 것이다.] 것은 어렵지 않다. 여기서 중요한 사항은 (이 증명에 사용된 것과) 동일한 논증(論證)이 249,500개의 임의의 점에 적용된다는 것이다.[역주: 말할 필요도 없이 이 점은 매우 중요하다. 만약 해답선 위에 있지 않은 조약돌의 처음 위치가 될 수 있는 249,500개의 각 점에 대해서, 위의 게임 규칙에 의한 그 메커니즘의 작동이 바른 최대 공약수를 구한다는 것을 증명하는 데 극단적으로 249,500번의 상이한 논증이 필요하다고 한다면 심각한 문제일 것이다. 꼭 249,500번이 아니라 문제의 공간 크기에 비례해서 논증에 필요한 노력의 양이 증가한다고 하더라도 현실적으로 그러한 일을 요구하는 메커니즘은 별 쓸모가 없게 될 것이다.] 두번째로는---그리고 역시 어렵지 않은 일이다---x = y인 임의의 점 (x, y)에 대해서(곧, (x, y)는 해답선 위에 있는 500개 지점들 중의 하나이다), GCD(x, y) = x임을 증명할 수 있다. 마찬가지로 여기서 중요한 것은 동일한 논증이 500개의 각 점에 대해서 적용 가능하다는 것이다. 세번째로는---이것 역시 어렵지 않은 일이다---(조약돌이 놓이는) 임의의 처음 위치 (X, Y)에 대해서, 유한한 횟수의 단계 안에 조약돌을 해답선으로 진짜 옮길 수 있음을 증명해야 한다.[역주: 달리 표현하자면 유한한 시간 내에 종료해야 한다는 뜻이다. 모든 알고리즘의 기본 요건이다.] 다시 한 번 주목해야 할 중요한 점은 이것 역시 250,000개의 초기 위치 (X, Y) 중의 어떤 지점에나 동일한 논증이 똑같이 잘 적용된다는 것이다. 격자점들의 갯수와는 (증명의) 길이가 무관한 세 개의 간단한 논증이, 요컨대 수학이 우리를 위해 해 줄 수 있는 것이 무엇인가를 보여 준다! (X, Y) 지점에서 시작한 게임 동안에 조약돌이 있을 수 있는 임의의 위치를 (x, y)라고 표시한다면, (앞에서 나온) 첫 번째 정리 덕분에 우리는 게임하는 동안에 다음 관계
GCD(x, y) = GCD(X, Y)
가 항상 성립함---전문 용어를 빌리자면---`불변으로 유지됨'을 결론 내릴 수 있다. 그리고 두번째 정리는 조약돌의 최종 위치의 x-좌표를 원하는 답으로 해석할 수 있음을 말하고 있다. 세 번째 정리는 그러한 최종 위치가 존재함(즉, 유한한 횟수의 단계 안에 도달함)을 우리에게 말해 준다. 이로써 `우리들의 추상적 기계'라고 부를 수도 있는 것의 분석은 완료된다.
다음 할 일은 제작자로부터 넘겨 받은 그 판지가 정말 흠이 없는 모형인지를 검증하는 것이다. 이 일을 위해서 두 축을 따라서 붙여져 있는 숫자들을 점검하고, 모든 직선들이 바르게 그려져 있는 지를 검사해야만 한다. 그 정사각형 판지의 한 모서리의 길이가 N(앞의 예에서는 500)이라고 하면, 이 일은 N에 비례하는 갯수의 사항들을 검사해야 하므로 약간 귀찮고 거북스럽다. 그래도 가능한 계산의 갯수인 N2보다는 항상 낫다.
또 다른 대안으로서의 기계는 커다란 판지를 이용하는 것이 아니라 0에서 500까지의[역주: 정확하게는 0부터 511까지를 저장할 수 있으나 여기서는 500까지만 필요하다.] 이진수를 저장할 수 있는 9-비트(bit) 크기의 레지스터(register) 두 개를 사용하는 것이다. 그러면 하나의 레지스터는 x-좌표를, 그리고 다른 레지스터는 y-좌표를 저장하도록 사용하여 이 두 레지스터가 `현재의 조약돌 위치'에 대응되도록 할 수 있다. 이렇게 되면 (판지 위에서의 조약돌의) 한 번의 이동은 하나의 레지스터에 들어 있는 내용으로부터 다른 레지스터의 내용을 빼는 것에 해당한다. 그 뺄셈을 사람이 직접 할 수도 있겠으나, 기계가 그것도 대신 해 주면 물론 더 좋을 것이다. 다음으로, 그 기계가 값을 비교하는 일과 빼는 일을 제대로 하고 있는 지를 확인하면 그 답을 신뢰할 수 있을 것이다. 이러한 과정은[역주: 우리가 얻고자 하는 답을 어떤 메커니즘이 옳게 구하고 있는 지를 검증하기 위한 분석 과정을 말한다.] 보다 작은 규모에서도 되풀이된다: 즉 n 자리의 임의의 두 이진수에 대해서, 이진 감산기(二進減算器)에 관련한 식을[역주: 이 식들은 조합 논리 회로(combinational logic circuit)를 설계할 때, 입력과 출력의 진리값(truth value)들 간의 관계를 나타내는 식을 생각하면 될 것이다.] 일단 한 번 유도한 뒤,[역주: 앞의 최대 공약수의 예처럼 그 식의 증명까지 포함한 과정을 여기서는 유도라고 말했다.] 실제 기계가 이 이진 감산기의 흠이 없는 모형인지를 확인한다.
만약 그 기계가 병렬(竝列) 감산기라면, 검사---구성 요소들과 그 상호 작용의 횟수에 비례할 텐데---해야 할 횟수는 n = log2 N에[역주: N은 레지스터에 저장될 가장 큰 수를 나타낸다.] 비례한다. 순차(順次) 기계의 경우, 한 걸음 더 시간을 희생하고 대신 설비를 택한 셈이 될 것이다.[역주: 원문에서는 ``In a serial machine the trading of time against equipment is carried still one step further.''라고 되어 있다. 더할 숫자들의 자릿수가 n인 경우, 병렬 감산기는 n개의 비트들을 각각 동시에 빼는데 반해, 순차 감산기는 낮은 자리로부터 1 비트씩 동일한 감산 회로를 사용하여 빼므로 설비 면에서는 경제적이다. 대신 시간이 훨씬 더 걸리게 된다.]
앞서의 예에서 특히 중요한 부분을 좀 더 확실하게 살펴 보겠다. 적어도 나 스스로 분명히 하기 위해서라도 필요하다.
GCD(111, 259)를 어떻게 계산하는가 하는 하나의 문제를 생각하는 대신에, 우리는 그 문제를 일반화시켜 그것을 GCD(X, Y)를 어떻게 계산할 것인가 하는 보다 큰 범주의 문제 집단 중의 한 특정한 예로 간주했다. 우리가 GCD(111, 259)를 계산하는 문제를 다른 방식으로 일반화시킬 수도 있었음을 지적하는 것은 가치있는 일이다. 그 문제를 다음과 같은 보다 큰 범주에 속하는 일들의 한 특정한 예로 간주할 수도 있었을 것이다: GCD(111, 259), SCM(111, 259),[역주: 익히 알다시피 `smallest common multiple' 즉 최소 공배수를 나타낸다. LCM(least common multiple)이라고도 부른다.] 111 * 259, 111 + 259, 111/259, 111 - 259, 111259, 기원전 259년의 111번째 날이 무슨 요일인가의 계산 등. 이러한 일반화로 만들어진 것은 `111-259-처리기'라고 부를 수 있을 것이고, 그것이 원래 바라던 답을[역주: GCD(111, 259)를 말한다.] 만들어 내도록 하기 위해서는 그 입력으로 ``GCD를 부탁해요.''란 요청을 주어야만 할 것이다! 그러나 그 대신에 우리는 `GCD-계산기'를 제안했고, 원래 원하던 답을 얻기 위해서는 `111, 259'를 입력으로 주어야 했다. 이 둘은 판이하게 다른 기계이다!
달리 표현하면, 어떤 결과를 만들어 내도록 요구 받으면, 대개 그 문제를 일반화시켜 보다 큰 집단의 구체적인 한 예로 생각한다. 그러나 모든 것이 보다 일반적인 것의 특별한 예라고 말하는 것만으로는 소용이 없다![역주: 정말 그렇다. 어떤 것이든지 자기를 포함하는 범주의 특별한 예가 될 것이다. 단순히 그 사실만 말하는 일반화라면 이것은 거의 쓸모가 없는 진술일 뿐이다.] 이러한 접근 방법을 사용하려면 다음 두 가지를 지켜야 한다:
앞의 예의 경우, 나는 `111-259-처리기'보다는 `GCD-계산기'를 확실히 선호하고, 두 가지를 비교해 보면 어떤 특징을 가진 일반화가 `우리의 목적에 도움이 되는'가에 대한 실마리를 알 수 있을 것이다. 우리의 요구에 따라 111과 259의 갖가지 희한한 함수값을 해답으로 만들어 주는 기계는, 그 함수들의 집합이 커짐에 따라 정합성의 검증이 점점 더 어려워진다. 이 점은 우리들의 `GCD-계산기'와는 매우 대조적이다.[역주: 독자들이 염두에 두어야 할 것은, 최대 공약수를 구하는 문제가 주어졌을 때는 GCD-계산기로 일반화시키는 것이 111-259-처리기로 일반화시키는 것보다 바람직하지만, 그것이 곧 후자(後者)와 같은 일반화가 모든 경우에서 쓸모없다는 뜻은 아니라는 점이다. 수학적 함수의 형태를 가지는 경우는 대부분 전자와 같이 매개 변수를 추상화시켜야 할 법하다. 그러나 다른 형태의 문제에서는 반대로 함수를 추상화시켜야 될 경우도 있을 수 있다. 적확(的確)한 예는 아니지만 실생활에서 볼 수 있는 다음과 같은 경우를 생각해 보자. 친밀한 관계의 두 사람(예컨대 부부)이 있다. 이 두 사람이 어떤 특이한 상황에서 어떠한 행동이나 결정을 할 것인지를 알고 싶은 것이 문제라고 하자. 책에 있는 최대 공약수의 예와 비슷하게 만들자면, 주어진 문제는 `특정 상황(특정인 1, 특정인 2)'이다. 일반화의 가능성은 최대 공약수의 예와 마찬가지로 두 가지가 있다. GCD-계산기처럼 `특정 상황(임의의 사람 1, 임의의 사람 2)'로 할 수가 있고, 111-259-처리기처럼 `임의의 상황(특정인 1, 특정인 2)'로 할 수도 있다. 어떤 쪽이 문제 해결에 용이할까? 우리가 그 특정인 두 사람을 잘 알지 못한다면 ``보통 사람들이 그러한 상황에 처하면 어떻게 할까?''를 생각하는 전자의 일반화가 보다 바람직할 법하다. 만약 그 두 사람을 우리가 아주 잘 알고 있다고 한다면 ``저 사람들이라면 이런 상황에서는 이런 행동을, 저런 상황에서는 저런 행동을 틀림없이 할거야.''라고 단정을 보다 확신을 가지고 할 수 있는 후자의 일반화가 바람직해 보인다. 결론은 문제에 따라서 다양한 추상화의 가능성이 있고, 그 중 어느 것을 택할 것인가 하는 점은 본문에 나온 충고를 고려하는 것이다. 또 한 가지 사족을 덧붙인다면, 전자와 절차적 프로그래밍 규범(procedural programming paradigm), 후자와 객체-지향적 프로그래밍 규범(object-oriented programming paradigm)과의 유사점을 생각해 보면 흥미가 있다.]
GCD-계산기가 만약 `미리 주어진' 답들을 포함하고 있는 250,000개 목록의 표의 형태였다면 (111-259-처리기와) 마찬가지의 문제가 있었을 것이다. GCD-계산기의 독특함은 `게임의 규칙들'의 압축된 집합 형태로 주어져서, 그 규칙에 따라 실행하면 답을 만들어 내는 점에 있다.
이 규칙들에 공히 적용되는 하나의 논증만으로 어떠한 게임이든지[역주: 여기서 각 게임은 어떤 초기 위치에 조약돌을 가져다 놓고 앞서의 규칙에 따라 조약돌을 옮기는 일을 말한다.] 그 결과에 대한 중요한 단정의[역주: 예를 들면, 정확한 최대 공약수의 값이 구해질 수 있다는 등의 단정을 생각할 수 있다.] 진위를 증명할 수 있다는 것은 엄청난 장점이다. 대신 지불해야 할 댓가는 이 규칙들을 적용시킬 250,000개의 각 위치에서 답을 `즉시' 얻지는 못한다는 것이다: 매번 규칙들에 의거해 게임을 해야만 한다!
단 하나의 논증만으로 어떤 가능한 게임에 대해서도 결론을 내릴 수 있게 하는 게임의 규칙들을, 그렇게 간단한 형태로 구성할 수 있다는 사실은 250,000개의 격자점들이 체계적으로 배열되어 있다는 것과 밀접한 연관이 있다. 만약 (GCD-기계의) 판지들 위에 체계적인 명명법(nomenclature)이[역주: 뒤에도 나오겠지만 여기서 명명법이란 `임의의 숫자들을 구별하기 위한 식별(시각 혹은 청각으로 식별하는) 기호를 각 숫자에 배정하는 방법'을 말한다. 예컨대, 아라비아 숫자를 사용한 십진수 체계에서는 0부터 9까지 10개의 기본 기호를 바탕으로 하여 1씩 증가하는 값을 가지는 숫자들에 식별 기호를 부여하고, 각 숫자들의 위치에 따라 10의 지수승인 가중치를 곱하는 식이다.] 없이, 무정형(無定形)의, 혼돈스런 점들의 무리만 있었다고 한다면 우리는 아무 일도 할 수 없었을 것이다! 허나 그렇지 않았기 때문에 우리는 조약돌을 반쪽으로 나누어서 하나의 반쪽은 수평축에 놓일 때까지 아래로 이동시키고, 다른 반쪽은 수직축에 위치할 때까지 왼편으로 이동시킬 수 있었을 것이다. 그렇게 되면 250,000개의 가능한 위치를 가지고 있는 한 개의 조약돌 대신에 각각 500개의, 즉 합해서 단지 1,000개의 위치만 가능한 두 개의 반쪽 조약돌로도 앞에 나온 문제를 다룰 수 있게 된다! 250,000개라는 많은 수의 상태들은, 하나의 반쪽 조약돌의 500개 위치 중 임의의 것이 다른 반쪽 조약돌의 500개 위치 중 임의의 것과 엮어질 수 있는 상황에 의해 가능해진 것이다: (그런 상황 하에서는) 나누지 않은 조약돌의 위치의 수가 반쪽 조약돌들의 위치의 수를 서로 곱한 것과 같게 된다. 전문 용어로 말하자면 ``전체 상태 공간(state space)은 변수 x와 y의 상태 공간들의 데카르트 곱(Cartesian product)으로 간주된다.''고 한다.
2차원 상에서 자유롭게 움직일 수 있는 하나의 조약돌을 1차원 상에서만 움직이는 두 개의 반쪽 조약돌로 대치할 수 있음은 앞서 제안된 두 개의 레지스터를 가진 기계에서 이용된 바 있다. 기술적인 관점에서 보아 이것은 매우 매력적이다. 왜냐하면 500개의 서로 다른 경우(`값')를 구분할 수 있는 레지스터들만 만들면, 단지 그런 레지스터 두 개를 결합함으로써 구별되는 상이한 경우의 수는 제곱이 되기 때문이다! 이 곱의 규칙 덕분에 우리는 가능한 전체 상태의 갯수가 엄청나게 크다고 하더라도 각각 적당한 숫자의 가능 상태만 가지는, 역시 적당한 갯수의 성분(component)들을 사용하여 구별할 수 있다. 그러한 성분들을 추가시킴으로써 상태 공간의 크기는 지수적으로 증가한다. 그러나 명심해야 할 것은 고안된 전체 메커니즘의 정합성에 관한 논증이 매우 간단하게 유지되는[역주: 새로운 성분이 추가되어도 추가되기 전과 마찬가지로 정합성의 논증이 간단하게 유지되는.] 경우에만 그럴 수 있을 따름이다. 논증도 역시 지수적으로 커진다면 그런 기계는 설계해 봤자 전혀 소용이 없다!
주의. 위에서 토의한 것의 완전한 실례는 10세기도 더 지난 고안품에서 찾아 볼 수 있다. 십진수 체계가 바로 그것이다! 이것은 정말로 매혹적인 성질을 가지고 있는데, 필요한 자릿수의 갯수는 표현하려고 하는 가장 큰 숫자의 대수(logarithm)에 비례해서 늘어날 뿐이라는 것이다. 이진수 체계도 마찬가지인데, 십진수 체계에서 사람의 손에 다섯개의 손가락이 있다는 것을 무시한 결과로 나오는 것이다.[역주: 별 심각한 뜻이 있는 것은 아니고, 십진수 체계가 인간이 손가락을 10개 가지고 있는 데서 연유했음을 환기시킨 것이다. 따라서 십진수 체계를 인간이 보편적으로 사용하게 된 것은 사실 생태학적 발생에 따른 우연의 결과이다. 그 바탕 원리는 동일하므로, 십진수 체계이든 이진수 체계이든 별 상관이 없음을 부연하고 있는 것이다.]
앞에서 우리는 큰 수로 나타나는 측면들[역주: 앞에서 본 GCD-계산기 내에서 나타나는 여러 측면들 중 큰 수라는 것에 의해서 특징지워지는 것들이 있었다. 그것들을 말한다. 계속해서 설명이 나온다.] 중 하나, 즉 조약돌이 놓일 수 있는 많은 수의 위치(= 가능한 상태)를 다루었다. 마찬가지로 다수가 나타나는 것이 있는데, 규칙에 따라 행하는 다수의 상이한 게임(= 계산)이다. 정확하게 표현하자면 각 초기 위치에 따라 하나씩의 계산이 대응된다. 우리들의 게임 규칙은 어떤 초기 위치에 대해서나 적용할 수 있다는 뜻에서 매우 일반적이다. 그러나 게임의 규칙들에 대한 논증이 간단한 형태로 표현될 수 있어야 하므로 이것은 곧 게임 규칙 자체가 간단해야 함을 의미한다.[역주: 게임의 규칙 자체가 복잡하면 각각의 규칙이 작용하여 일어날 수 있는 상황들이 다양하여 집단적으로 특징짓기는 어려울 것이다. 따라서 그 규칙들이 어떤 목표를 제대로 달성함을 보이는 일은 점점 더 복잡해 질 것이다.] 책의 예에서 이 목표는 다음과 같은 방안에 의해서 달성되었다: ``이것을 하고, 다음에 저것을 하라.''라고 나열하는 대신에, `하나의 단계(step)'를 어떤 경우에 `그 단계'를 수행해야 하는가에 대한 기준과 함께 제시하는 식으로 게임 규칙을 주었다. (실제로는 각 단계는 그 단계가 정의되지 않는 상태에 도달할 때까지 반복되어져야만 한다.) 다시 말해서, 하나의 `부분 규칙(sub-rule)'만을 반복해서 적용함으로써 하나의 게임이 온전히 구성되는 것도 허용된다.
이것은 매우 강력한 장치이다. 하나의 알고리즘은 그 제어하에 일어날 수 있는 계산들의 집단에 대한 설계를 구체화한 것이다. `한 단계'의 조건적 반복 덕분에 그러한 집단에 속하는 계산들은 길이[역주: 수행 시간의 길이를 말한다.] 면에서 크게 다를 수 있다. 이 점은 짧은[역주: `단계들의 수'나 `게임의 규칙들의 수' 측면에서 짧다는 뜻이다.] 알고리즘이 어떻게 상당히 긴 시간 동안 기계를 바쁘도록 할 수 있는 지를 설명해 준다. 거꾸로 보자면, 그 점이 매우 빠른 기계를 우리들이 필요로 하는 이유를 시사한다고 할 수도 있을 것이다.
유클리드가 어깨 너머로 넘겨 보고 있는 동안 이 장을 썼다고 생각해 보면 너무 멋지다.
다시 김도형의 홈 페이지로