인포메이션 #14 무작위성의 감각

 

제 12 장 무작위성의 감각

죄악의 상태에 빠져
 

그녀가 말했다.
"갈수록 패턴을 파악하기가
어려워져, 안 그래?" 
마이클 커닝엄(2005)

 
 
열한 살짜리 뉴욕 소년 체이틴은 <괴델의 증명>이라는 멋진 책을 발견하게 된다. 이 책은 조지 불로부터 시작된 논리학의 르네상스를 다루었다. 기호 그리고 심지어 정수의 형식으로 수학에 대한 진술을 인코딩하는 '사상'과정, 수학에 '대한' 따라서 수학을 '넘어서는' 체계화된 언어인 메타수학 개념을 다루었던 것이다. 형식적 수학은 결코 자기모순으로부터 자유로울 수 없다는 괴델의 "놀랍고 우울한" 증명을 단순하지만 엄밀하게 해설하고 있는 지은이들을 따라가던 소년은 흥분에 휩싸였다.
 
당시 수학의 대부분은 괴델의 증명을 거들떠보지도 않았다. 이 증명을 다소 부차적인 것으로 보았다. 계속해서 발견하고 정리를 증명하는 수학자들의 유용한 연구에 하등 도움이 안 된다고 본 것이다. 하지만 철학적으로 사고하던 사람들은 괴델의 증명에 적잖은 충격을 받았으며, 그중 하나가 존 폰 노이만이었다.
 

괴델의 증명은 매우 심각한 개념적 위기로, 수학적 증명을 정확하게 하는 엄밀하고 적절한 방식을 다룬다. 수학의 절대적 엄밀함이라는 이전의 개념에서 볼 때 이런 일이 벌어질 수 있다는 사실이 놀랍다. 기적이라고는 일어날 것 같지 않은 요즘 같은 후대에 이런 일이 벌어진다는 것이 더욱 놀랍다. 그럼에도 이런 일이 벌어진 것이다.

 
'왜일까?' 체이틴은 궁금했다. 괴델의 불완전성과 양자물리학의 새로운 원칙으로서 다소 비슷한 냄새를 풍기는 불확실성을 연결할 수 있을지 궁금했던 것이다. 괴델의 불완전성은 하이젠베르크의 불확실성과 관련이 있을까? 이 질문을 괴델 본인에게 한 적이 있다고 말했다. 괴델은 휠러의 질문에 대답하지 않았다. 이렇게 휠러 역시 체이틴에게 답변하지 않은 것이다.
 
튜링의 연산 불가능성 증명을 접한 체이틴은 틀림없이 이 증명이 실마리가 될 것이라고 생각했다. 또한 섀넌과 위버가 쓴 <통신의 수학적 이론>을 읽은 체이틴은 엔트로피의 재공식화에 충격을 받았다. 별안간 체이틴의 머리에 떠오른 생각이 있었다. 공통된 요소는 무작위성이었다. 섀넌은 무작위성을 고집스럽게 정보와 연결시켰다. 물리학자들은 원자의 내부에서 무작위성을 발견했다.
 
무작위, 단순한 단어일 뿐 아니라 누구나 그 뜻을 안다. 누구나 안다는 것은 말하자면 아무도 모른다는 뜻이다. 무직위를 놓고 철학자와 수학자들은 끝없이 씨름했다. 휠러는 이런 이야기를 자주했다. "확률은 시간처럼 인간이 만들어낸 개념이며, 따라서 확률에 수반되는 모호성은 인간이 책임을 져야 한다." 어떤 특정한 순간 프랑스의 인구가 홀수인지 짝수인지는 무작위적이지만, 프랑스의 인구 자체는 확실히 무작위적이지 '않다'. 존 메이너드 케인스는 무작위성에 반대되는 것 세 가지를 선택해 무작위성 문제를 다룬다. 세 가지는 바로 지식, 인과성, 계획이었다. 이미 알려진 것이나 인과관계로 결정되는 것, 혹은 계획에 따라 조직되는 것은 무작위적일 수 없었다.
 
카오스를 이해했던 푸앵카레는 떨어지는 빗방울 같은 현상들도 그 원인은 물리적으로 결정되지만 너무나 많고 복잡해서 예측할 수 없는 무작위성의 사례라고 보았다. 물리학에서(혹은 자연적 과정들이 예측할 수 없는 것으로 보이는 모든 분야에서) 명백한 무작위성은 잡음일 수도 있고, 매우 복잡한 역학에서 기인할 수도 있다.
 
무지는 주관적이다. 무지는 관찰자의 속성이다. 무작위성은 (만약 존재한다면) 사물 자체의 속성일 것이다. 인간을 배제하면 사건, 선택, 분포, 게임, 혹은 가장 간단하게 수는 무작위적이라고 말하고 싶을 것이다.
 
난수 개념은 어려운 문제들로 가득하다. '특정한' 난수라는 것이 존재할 수 있을까? '확실한' 난수는 있을까? 다음의 수는 거의 틀림없이 무작위적이다.
 

10097325337652013586346735487680959091173929274945 .....의 10승

 
랜드 연구소는 전자식 룰렛 휠로 구현한 펄스 발생기를 이용하여 이 수를 생성했다. 이 과정은 수년이 걸렸다. 숫자들의 첫 번째 묶음을 검증하던 통계학자들은 상당한 편향을 발견했다. 어떤 수, 수의 집단 혹은 수의 패턴이 너무 자주 또는 너무 드물게 나타났던 것이다.
 
과학자들은 통계적으로 타당한 실험을 기획하거나 복잡계의 현실적인 모델을 구축하려면 업무상 대량의 난수가 필요했다. 몬테카를로 시뮬레이션이라는 새로운 방법론은 무작위적 샘플링을 활용하여 분석적으로 풀 수 없는 현상에 대한 모델을 만들었다. 몬테카를로 시뮬레이션은 원자탄 프로젝트를 맡은 폰 노이만 연구팀이 중성자 확산의 계산에 필요한 난수를 생성하기 위해 엄청나게 노력한 끝에 만든 것이었다. 폰 노이만은 결정론적 알고리즘과 유한한 저장 용량을 가진 기계식 컴퓨터는 절대 진정한 난수를 생성할 수 없다는 사실을 깨달았다. 폰 노이만은 '의사난수'에 만족해야 했다. 의사난수는 결정론적으로 생성됐지만 무작위적인 것처럼 움직였다.
 
무작위성은 질서라는 측면에서 정의할 수 있다. 말하자면 무작위성은 잘서가 없는 것이다. 아래에 있는 짧은 수열처럼 질서 정연한 수열은 "무작위적"이라고 볼 수 없다.
 

00000

 
하지만 이 수열은 유명한 100만 개의 무작위적인 난수에서 특별 출연을 한다. 확률로 따지면 이 수열을 예상할 수 있다. 100만 개의 난수 중에는 이런 수열도 있다.
 

010101

 
이 수열 역시 패턴이 있는 것처럼 보인다.
 
숫자라는 짚더미에서 패턴이라는 바늘을 찾아내려면 똑똑한 관찰자의 작업이 필요하다. 우주 긴 무작위적 수열이 주어지면, 어딘가에는 가능한 모든 짧은 하위 수열이 나타날 것이다. 그중 하나는 은행 금고를 여는 비밀번호일 것이다. 다른 하나는 인코딩된 셰익스피어의 완전한 작품일 것이다. 하지만 이것들은 아무짝에도 쓸모가 없다. 왜냐하면 알아보는 사람이 아무도 없기 때문이다.
 
어쩌면 00000과 010101 같은 수가 특별한 맥락에서는 무작위적이라고 말할 수 있을지도 모른다. 공정한 동전을 아주 오랫동안 던지면 특정한 시점에는 앞면이 10번 연속으로 나오기 마련이다. 이렇기 때문에 인간이 기계의 도움을 받고도 난수를 생성하는 데 서툰 것이다. 무작위성을 예측하고 인식하는 일 모두에서 인간의 직관은 쓸모없다는 것을 연구자들이 입증한 바 있다. 인간은 무심결에 패턴을 향해 흘러간다.
 
 
수는 정보이다. 다음은 50자리 이진수열 두 개이다.
 

A : 01010101010101010101010101010101010101010101010101
B : 10001010111110101110100110101000011000100111101111

 
만약 앨리스(A)와 봅(B)이 모두 동전 던지기로 이 수열들을 생성했다고 말한다면, 앨리스의 말을 믿을 사람은 아무도 없을 것이다. 이 두 수열은 분명 동일하게 무작위적이지 않다. 고전 확률론에서 보면 B가 A보다 더 무작위적이라고 주장할 확실한 근거는 없다. 무작위적 과정은 두 수열을 모두 '생성할 수 있기' 때문이다. 확률은 전체에 대한 것이지, 개별 사건에 대한 것이 아니다. 확률론은 사건을 통계적으로 취급한다. 따라서 "그 사건이 일어날 가능성은 얼마나 될까?"라는 식의 질문을 좋아하지 않는다. 사건이 일어났다면, 일어난 것이다.
 
섀넌이라면 이 수열을 메시지로 보았을 것이다. "각 수열은 '얼마나 많은 정보'를 담고 있는가?" 두 수열 모두 50비트의 정보를 담고 있다. 자릿수로 요금을 부과하는 전신수는 메시지들의 길이를 재고 앨리스와 봅에게 같은 청구서를 줬을 것이다.
 
하지만 다른 한편으로 두 메시지는 많이 달라 보인다. 메시지 A는 금세 지루해진다. 일단 패턴을 알게 되면, 이후 반복되는 것에서는 새로운 정보가 없다. 메시지 B에서 모든 비트는 다른 모든 비트만큼 가치가 있다. 섀넌은 정보이론을 처음 확립하면서 메시지를 통계적으로 다루었다. 메시지를 모든 가능한 메시지 전체에서 선택된 것으로 본 것이다. 
 
하지만 섀넌은 동시에 메시지 내의 잉여성, 즉 메시지를 압축할 수 있게 만드는 패턴, 규칙성, 질서도 고려했다. 메시지의 규칙성이 클수록 예측성이 높아진다. 예측성이 높을수록 잉여성은 커진다. 잉여성이 클수록 포함하는 정보는 줄어드는 것이다.
 
전신수는 메시지 A를 손쉽게 보낼 수 있다. "'01'을 25번 반복"이라는 식의 메시지를 보내면 된다. 메시지가 길어도 패턴이 일정하면 키 조작 횟수가 크게 줄어든다. 패턴이 명확하면, 나머지 기호들은 무료로 보낼 수 있다. 메시지 B를 보내는 전신수는 모든 기호가 완전히 예상 밖의 것이기 때문에 기호를 모두 보내려면 힘들게 계속 일해야 한다. 모든 기호에는 1비트가 필요하다. '얼마나 무작위적인가'와 '정보가 얼마나 담겨 있는가'는 같은 질문이다. 이 질문의 답은 하나이다.
 
체이틴은 튜링기계를 생각했다. 무한한 테이프를 따라 앞뒤로 왔다 갔다 하면서 기호를 읽고 쓰는 튜링기계는 이른바 명쾌한 추상화의 극치였다. 현실세계의 모든 혼란스러움, 삐걱대는 톱니바퀴 장치와 까다론운 전기, 그리고 속도 문제에서 자유로운 튜링기계는 이상적인 컴퓨터였다.
 
튜링기계를 최대한 단순화시킨 섀넌은 범용 컴퓨터를 두 개의 내부 상태state만으로 구축할 수 있음을 증명한다. 0과 1이라는 단 두 개의 기호 혹은 공백과 비공백만으로 범용 컴퓨터를 만들 수 있음을 증명한 것이다.
 
"오가는 동작"으로 정보는 테이프의 칸 사이를 옮겨가며, 칸들은 "송신기" 및 "제어기"의 역할을 한다.
 
튜링이 진정으로 다루고자 했던 것은 연산 '불가능'한 수였다. 연산 불가능한 수와 무작위적인 수를 연관 지을 수 있을까?
 
다음의 수를 보자.
 

C : 3.1415926535897932384626433832795028841971693993751.....

 
이 수는 무작위적으로 보인다. 통계적으로 각 수는 기대 빈도(10번에 한번)에 따라 나타난다. 두 자릿수(100번에 한 번), 세 자릿수도 마찬가지이다. 통계학자라면 누구나 "정규적"이라고 말할 것이다. 다음에 나오는 수는 언제나 의외이다. 이렇게 가면 결국에는 셰익스피어의 작품도 그 안에 있을 것이다. 하지만 어떤 사람은 이 수를 우리에게 익숙한 수, 파이로 인식할 것이다. 따라서 이 수는 결국 무작위적이지 않다.
 
그렇다면 우리는 왜 파이가 무작위적이지 않다고 말하는 것일까? 체이틴은 분명하게 답한다. 수가 계산 가능하다면, 즉 확정된 컴퓨터 프로그램으로 이 수를 생성할 수 있다면 무작위적이지 않다. 따라서 연산 가능성은 무작위성의 기준이다.
 
우리는 어떤 수가 다른 수보다 더 무작위적이라고, 말하자면 패턴이나 질서가 적다고 말하고 싶어 한다. 체이틴은 패턴과 질서가 연산 가능성을 표현한다고 말했다. 알고리즘은 패턴을 생성한다. 따라서 우리는 '알고리즘의 크기'를 통해 연산 가능성을 가늠할 수 있다. 주어진 수에 대해 우리는 "이 수를 생성할 가장 짧은 프로그램의 길이는 무엇인가?"라고 물을 수 있다. 튜링기계의 언어를 활용하면 이 질문은 비트로 측정되는 명확한 답을 가질 수 있다.
 
무작위성을 알고리즘으로 정의한 체이틴의 방식을 보면 정보를 알고리즘으로 정의할 수 있다. 알고리즘의 크기는 주어진 기호열이 얼마나 많은 정보를 담는지 말해준다.
 
패턴을 보는 것, 카오스 속에서 질서를 찾는 것은 과학자들의 일이기도 하다. 열여덟 살의 체이틴은 이것이 우연이 아니라고 생각했다. 알고리즘적 정보이론을 과학 자체의 과정에 적용하면서 첫 논문을 마무리하던 체이틴은 이렇게 제안한다. "매초 광선을 방출하거나 방출하지 않는 닫힌계를 관찰하고 있는 과학자를 생각해보자."
 

0이 '광선이 방출되지 않았음'을 나타내고, 1이 '광선이 방출됐음'을 나타낸다면 과학자는 0과 1의 수열로 관찰 내용을 정리할 수 있다. 이를테면 이런 수열이 나온다고 하자.
0110101110 .....
그리고 수천 비트가 더 이어질 수 있다. 이후 과학자는 어떤 종류의 패턴이나 법칙을 관찰하기를 바라면서 수열을 분석한다. 이는 무슨 의미가 있을까? 0과 1의 수열은 단지 표를 보고 한 번에 전체 수열을 쓰는 것보다 더 나은 계산 방법이 없다면 패턴이 없다고 보는 것이 타당하다.

 
하지만 알고리즘, 즉 수열보다 훨씬 짧은 컴퓨터 프로그램으로 같은 수열을 생성하는 방법을 발견한다면 과학자는 이 사건들이 확실히 무작위적이지 않음을 알 것이다. 과학자는 하나의 이론을 발견했다고 말할 것이다. 많은 사실들의 집합을 설명하고 아직 일어나지 않은 사건을 예측할 수 있게 해주는 단순한 이론, 이는 과학이 항상 추구하는 바이다. 이것이 유명한 오캄의 면도날이다.
 
체이틴은 논문을 출판하려고 했지만, 소련에서 비슷한 논문이 나왔다는 소문을 접한 한 심사위원의 말을 듣게 된다. 안드레이 니콜라예비치 콜모고로프가 쓴 <'정보량' 개념의 정의에 대한 세 가지 접근법>이라는 논문이다. 이 논문은 서구 수학자들에게 알려지기까지 오랜 시간이 걸렸다. 
 
"매 순간 '하찮은' 것과 불가능한 것 사이에는 아주 미세한 차이밖에 없다. 이 미세한 차이 안에서 수학적 발견이 이뤄진다." 콜모고로프가 일기에 쓴 말이다. 정보를 정량적으로 보는 새로운 관점에서 콜모고로프는 확률론 문제, 즉 무작위성의 문제를 해결할 실마리를 찾는다. 어떤 주어진 "유한한 대상" 안에 얼마나 많은 정보가 담겨 있을까? 그 대상은 수(일련의 수)일 수도 있고, 메시지일 수도 있으며, 데이터 집합일 수도 있다.
 
콜모고로프는 조합론적 접근법, 확률론적 접근법, 알고리즘적 접근법이라는 세 가지 접근법을 설명한다. 첫 번째와 두 번째는 섀넌의 접근법을 다듬은 것이었다. 이 두 가지 접근법은 대상들의 총체 안에서 하나의 대상이 갖는 확률에 초점을 맞췄다. 이를테면 가능한 메시지 집합에서 어떤 특정 메시지가 선택될 확률에 초점을 맞춘 것이다. 
 

콜모고로프는 대상이 단지 문자체계 안에서의 기호 하나나 교회 유리창 안의 손전등 같은 것이 아니라, 유전적 유기체나 예술품처럼 크고 복잡한 것이라면 어떻게 될 것인지 궁금했다. 톨스토이의 <전쟁과 평화>에 담긴 정보량은 어떻게 측정할까? 콜모고로프의 질문을 보자. "이 소설을 합리적인 방식으로 '모든 가능한 소설'의 집합에 포함시키고, 나아가 이 집합에서 특정한 확률 분포를 고려하여, 가령 뻐꾸기의 유전적 정보량을 측정할 수 있을까?

 

정보를 측정하는 세 번째 접근법인 알고리즘적 접근법은 가능한 대상의 총체에서 출발해야 하는 난점을 없앴다. 이 접근법은 대상 자체에 초점을 맞췄다. 콜모고로프는 측정하고자 하는 대상을 위해 새로운 단어를 제안한다. 바로 '복잡성complexity'이다. 이에 따르면 수나 메시지 혹은 데이터 집합의 복잡성은 단순성과 질서의 반대이다. 다시 말하지만 정보에 해당한다. 대상이 단순할수록 담고 있는 정보도 적다. 복잡성이 높을수록 담고 있는 정보도 많다. 아울러 콜모고로프는 체이틴과 마찬가지로 알고리즘을 토대로 복잡성을 계산함으로써 이 개념을 확고한 수학적 토대 위에 놓았다. 어떤 대상의 복잡성은 이 대상을 생성하는 데 필요한 가장 작은 컴퓨터 프로그램의 크기이다. 짧은 알고리즘으로 생성할 수 있는 대상은 복잡성이 낮다. 반면 전체 비트가 대상 자체만큼이나 긴 알고리즘이 필요한 대상은 복잡성이 가장 높다.

 

단순한 대상은 아주 적은 비트로 생성, 연산, 기술할 수 있다. 복잡한 대상은 많은 비트의 알고리즘이 필요하다. 이렇게 설명하면 너무 뻔해 보인다. 하지만 이 사실은 그때까지 수학적으로 해석되지 못했다.

 

'단순한' 대상과 '복잡한' 대상 사이의 직관적인 차이는 오래전부터 분명하게 인식됐다. 이런 차이를 형식화하는 데는 확실히 어려움이 따른다. 하나의 언어로 단순하게 기술할 수 있는 대상이 다른 언어로는 단순하게 기술할 수 없어, 기술하는 데 어떤 방식을 써야 할지 분명하지 않은 것이다.

 

이 어려움은 컴퓨터 언어를 활용함으로써 해결됐다. 어떤 대상의 콜모고로프 복잡성은 그 대상을 생성하는 데 필요한 가장 짧은 알고리즘의 비트 단위 크기이다. 이는 또한 정보량이기도 하다. 아울러 무작위성의 정도이기도 하다. 콜모고로프의 말은 이렇다. "무작위성은 '무작위적'이라는 개념의 새로운 이해방식으로, 규칙성의 부재라는 자연스러운 가정에 부합한다." 정보, 무작위성, 복잡성, 이 세 가지는 근본적으로 동일하다. 

 

콜모고로프가 보기에 이런 개념은 확률론뿐만 아니라 물리학에도 속했다. 질서 정연한 결정체나 혼란스러운 기체 상자의 복잡성은 기체나 결정체의 상태를 기술하는 데 필요한 가장 짧은 알고리즘으로 측정 할 수 있다. 다시 한 번 엔트로피가 핵심이었다.

 

소용돌이와 회오리의 분포를 예측하는 방정식을 만들었고, 또한 고전적 뉴턴 물리학으로는 엄청나게 다루기 힘들었던 또 다른 문제인 행성 궤도의 섭동을 연구했다. 콜모고로프는 1970년대에 일어난 카오스 이론 르네상스의 토대를 놓고 있었다. 카오스 이론은 엔트로피와 정보 차원에 따라 동역학계를 분석했다. 이제는 동역학계가 정보를 생성한다는 말을 이해할 수 있었다. 동역학계를 예측할 수 없다면, 이는 엄청난 정보를 생성한다는 말이었다.

 

 

이제 역설들이 돌아왔다. 0은 흥미로운 수이다. 모든 작은 수는 흥미롭다고 해도 무리가 없어 보인다. 흥미롭지 않은 수는 어떤 것일까? 아마 무작위적인 수일 것이다. 

 

제아무리 라마누잔의지성이라도 인간 지식의 총합처럼 유한하기 때문에 흥미로운 수의 목록은 어디선가 끝나야 한다. 분명히 딱히 얘기할 만한 특별한 점이 없는 수가 있다. 그 수가 어디에 있든 간에 거기에 역설이 있다. 흥미롭게도 우리는 그 수를 "흥미롭지 않은 가장 작은 수"로 기술할 수 있다.  이것이 바로 러셀이 <수학 원리>에서 이야기한 베리의 역설이다. 어떤 수가 흥미로운 이유는 그 수를 명명하는 방법에 있다. 

 

체이틴과 콜모고로프는 알고리즘적 정보이론을 만들면서 베리의 역설을 되살렸다. 알고리즘은 수를 명명한다. 체이틴의 말을 들어보자. "베리의 역설은 원래 영어에 대해 이야기하지만, 이는 너무 모호하다. 나는 대신 컴퓨터 프로그래밍 언어를 선택한다." 당연히 체이틴이 선택한 것은 범용 튜링기계의 언어였다.

 

흥미로운 수인지 어떤지를 묻는 것은 수가 무작위적인지 그렇지 않은지를 묻는 것의 정반대이다. 비교적 짧은 알고리즘으로 연산할 수 있다면 숫자 n은 흥미롭고, 그렇지 않다면 무작위적이다. '1을 인쇄한 다음 100개의 0을 인쇄하라'라는 알고리즘은 흥미로운 수(구골googol)를 생성한다. 이 수는 연산 가능하다. 

 

하지만 "PRINT [n]" 의 n은 흥미롭지 않다. 이 수는 무작위적이며 최대의 복잡성을 갖는다. 또한 이 수는 패턴이 없어야 한다. 왜냐하면 패턴이 있다는 것은 단축 알고리즘을 만들 방법이 있다는 말이기 때문이다. 체이틴은 말한다. "수를 계산하는 짧고 간결한 컴퓨터 프로그램이 있다는 것은 이 수를 선택해 더 작은 알고리즘으로 압축할 수 있도록 해주는 어떤 특성이나 특질이 있다는 뜻이다. 따라서 그 수는 특이하며 흥미로운 수이다."

 

하지만 '정말' 특이할까? 수학자는 하나의 수를 보면 더 작은 알고리즘을 찾을 수 있을지 항상 확실히 알 수 있을까? 체이틴에게는 중요한 질문들이었다.

 

체이틴은 첫 번째 질문에 계수의 논리로 답한다. 대다수 수들은 계산할 수 있는 간결한 컴퓨터 프로그램이 충분할 수 없기 때문에 흥미롭지 않을 수밖에 없다. 이를테면 1,000비트는 2의 1000승개의 수를 가진다. 하지만 1,000비트로는 절대 그렇게 많은 유용한 컴퓨터 프로그램을 만들 수 없다. "자연수는 아주 많다. 만약 프로그램이 더 작아야 한다면 모든 다른 자연수를 명명하기에 충분할 만큼 있지 않다." 따라서 어떤 길이의 수라도 대부분의 n은 무작위적이다.

 

두 번째 질문은 훨씬 더 까다로웠다. 수학자들은 그 수가 무작위적임을 증명할 수 있을까? 수를 본다고 알 수 있는 건 아니다. 수학자들은 종종 그 반대, 즉 n이 흥미롭다는 사실을 증명할 수 있다. 이 경우 n을 생성하는 짧은 알고리즘을 찾기만 하면 된다. (전문적으로 말하면, 알고리은 n을 이진수로 작성하는 데 필요한 log2n비트보다 짧아야 한다.)

 

"설사 대부분의 자연수가 흥미롭지 않다 하더라도, 우리는 이에 대해 결코 확신할 수 없다.  ... 오직 소수의 사례에서만 이 점을 증명할 수 있을 뿐이다."  모든 가능한 알고리즘을 작성하고 하나씩 검증하면서 우격다짐으로 증명을 시도하는 것을 생각할 수도 있다. 하지만 컴퓨터가 테스트를 실행해야(한 알고리즘이 다른 알고리즘을 테스트해야) 했고 체이틴은 곧 새로운 형태의 베리의 역설이 등장한다는 것을 증명한다. 

 

따라서 "흥미롭지 않은 가장 작은 수" 대신 "n음절 미만으로 명명할 수 없다고 증명할 수 있는 가장 작은 수"의 형태로 된 진술과 불가피하게 마주치게 된다. (물론 우리는 더 이상 음절에 대해 이야기하는 것이 아니라 튜링기계의 상태에 대해 이야기하는 것이다.) 또 다른 재귀적, 자기 순환적인 꼬임에 빠지는 것이다. 체이탄판 괴델의 불완전성이었다. 프로그램 크기로 정의되는 복잡성은 일반적으로 연산 불가능하다. 100만 자리의 임의적인 수열이 주어졌을 때 수학자는 이 수열이 거의 확실히 무작위적이고 복잡하며 패턴이 없음을 알 수 있지만, 절대적으로 확신할 수 없다.

 

체이틴의 연구를 보면 수학은 일종의 경험적 학문으로 취급되었다. 말하자면 절대적 진리로 가는 플라톤적 통로가 아니라 세상의 우연성과 불확실성의 영향을 받는 연구 프로그램이었던 것이다. 체이틴의 말을 들어보자. "불완전성과 연산 불가능성 그리고 심지어 알고리즘적 무작위성에도 불구하고 수학자는 절대적 확실성을 포기하려 하지 않습니다. 왜 그럴까요? 아마 절대적 확실성이 신과 같기 때문일 것입니다."

 

양자물리학에서, 그리고 나중에 나온 카오스 이론에서 과학자들은 지식의 한계를 발견했다. 과학자들은 불확실성을 탐구했다. 체이틴 말마따나 "신은 양자물리학과 비선형 역학뿐만 아니라 심지어 정수론에서도 주사위 놀이를 한다."

 

이들의 교훈 중 몇 가지를 보자.

• 대부분의 수는 무작위적이다. 그러나 무작위적임을 '증명할' 수 있는 수는 극히 적다.
• 정보의 카오스적 흐름도 단순한 알고리즘을 숨기고 있을 수 있다. 카오스에서 알고리즘으로 역행하는 일은 불가능할 수 있다.
• 콜모고로프-체이틴 복잡성이 수학에서 차지하는 위치는 엔트로피가 열역학에서 차지하는 위치와 같다. 둘 다 완벽성에 대한 해독제이다. 영구 운동기관을 만들 수 없듯이 완전한 형식적 공리 체계도 있을 수 없다.
• 몇몇 수학적 사실들은 특별한 이유 없이 참이다. 이 사실들은 우연적이며, 원인이나 깊은 의미를 지니지 않는다.

물리학자 조지프 포드는, 체이틴이 괴델의 불완전성에서 카오스로 가는 경로를 밝힘으로써 "물질의 본질을 멋지게 포착했다"라고 말했다. 포드는 이것이 "카오스의 더 심오한 의미"라고 밝혔다.

카오스적 궤도는 존재한다. 하지만 괴델의 후손인 카오스적 궤도는 너무나 복잡하고 엄청나게 정보가 가득해서 인간이 절대 이해할 수 없다. 그러나 카오스는 자연 어디에나 있다. 따라서 우주는 인간이 절대 이해할 수 없는 수많은 신비로 가득하다.

 

그럼에도 우리는 우주를 측정하려 노력한다.

 

 

'얼마나 많은 정보가 있을까....?'

어떤 대상을 더 적은 비트로 다르게 표현할 수 있으면 압축이 가능하다. 알뜰한 전신수는 메시지의 압축판을 보내는 것을 좋아한다. 섀넌 역시 자연스럽게 이론적으로나 실질적인 측면에서 데이터 압축을 연구했다. 섀넌이 보기에 압축이 핵심이었다. 데이터 압축은 똑같이 정보를 인코딩한다.

 

지금은 섀넌-파노 코딩으로 불리는 최초의 알고리즘은 모스 코드처럼 자주 쓰는 기호에 짧은 코드를 할당한다는 단순한 아이디어에서 시작되었다. 하지만 섀넌과 파노는 이 방법이 최선이 아님을 알았다. 가능한 가장 짧은 메시지를 만들어낼 수 없기 때문이었다. 3년이 채 지나지 않아 MIT 대학원생 데이비드 허프만의 연구에 의해 따라잡히고 만다. 이후 수십 년 동안 허프만의 코딩 알고리즘은 수없이 많이 이용되었다.

 

레이 솔로모노프는 1950년대 초반 섀넌의 논문을 접하고는 섀넌이 정보 패킹 문제라 말한 것에 천착하기 시작했다. 이 문제는 주어진 수의 비트에 얼마나 많은 정보를 '담을' 수 있는지 혹은 반대로 어떤 정보가 주어졌을 때 가능한 한 가장 적은 비트에 어떻게 담을 것인지를 다루었다. 

 

아울러 새로운 정보이론적 개념을 언어 구조의 형식화에 적용한 노암 촘스키의 색다르고 독창적인 논문 <언어 기술의 세 가지 모델>을 읽었다. 이 모든 것들을 머릿속에서 이리저리 생각하던 솔로모노프는 이것들이 어디로 향할지 확실히는 알 수 없었지만, 자신이 '귀납'의 문제에 초점을 맞추고 있음을 깨달았다.

 

사람들은 자신이 세상에서 경험한 것들을 설명하는 이론을 어떻게 만드는 것일까? 이론을 만들려면 일반화를 해야 하고, 언제나 무작위성과 잡음에 의해 영향받는 데이터에서 패턴을 찾아야 한다. 기계가 이 일을 하게 만들 수 있을까? 다시 말해 컴퓨터가 경험을 통해 배우도록 만들 수 있을까?

 

1964년 이에 대한 정밀한 해답을 계산해낸 솔로모노프는 이를 논문에 담아 발표했다. 사실상 솔로모노프 역시 컴퓨터가 데이터의 열(수열 혹은 비트열)을 보고 무작위성과 숨겨진 패턴을 측정하는 방법을 파악하고 있었다. 경험을 통해 배울 때 인간 혹은 컴퓨터는 불규칙한 정보의 흐름에서 규칙성을 파악하는 귀납법을 쓴다. 이런 관점에서 보면 과학 법칙은 데이터 압축이 진행되고 있음을 나타낸다. 이론물리학자들은 아주 똑똑한 코딩 알고리즘처럼 행동한다.

 

"발견된 과학 법칙은 우주에 대한 수많은 경험적 데이터를 간략하게 요약한 것으로 볼 수 있다. 각 법칙은 현재의 맥락 안에서 그 법칙의 토대가 되는 경험적 데이터를 긴밀하게 코딩하는 수단으로 전환될 수 있다." 이 말을 달리 표현하면 뛰어난 과학 이론은 경제적이다.

 

솔로모노프, 콜모고로프, 체이틴은 세 가지 다른 문제와 씨름했고, 같은 해답을 제시했다. 솔로모노프의 관심은 귀납적 추론이었다. 일련의 관측 결과가 주어졌을 때 다음에 무엇이 올지 예측하는 최선의 방법은 무엇일까? 콜모고로프는 무작위성을 수학적으로 정의하는 방법을 찾고 있었다. 동전 던지기에서 나올 수 있는 확률이 같을 때 한 수열이 다른 수열보다 더 무작위적이라는 말은 무슨 의미일까? 체이틴은 튜링과 섀넌을 거쳐 괴델의 불완전성에 이르는 난해한 길을 찾고 있었다. 이들 모두는 최소 프로그램 크기에 이르렀다. 또한 결국 이들은 복잡성에 대해 논하게 된다.

 

E : 1010101010101010101010101013

 

전신수(혹은 이론가 혹은 압축 알고리즘)는 전체 메시지에 주의를 기울여야 한다. 그럼에도 불구하고 추가 정보는 아주 적다. 여기서도 메시지에서 패턴이 존재하는 부분을 압축할 수 있다. 따라서 이 수열에는 잉여적 부분과 임의적 부분이 들어 있다고 할 수 있다.

 

F : 1011010111110101110110111101001110111011101110111111101110101011110

 

1이 많고 0이 적은 이 수열은 편중된 동전을 던져서 나온 결과일 수 있다. 허프만 코딩과 다른 코딩 알고리즘은 데이터를 압축하기 위하여 통계적 규칙성을 활용한다. 사진은 피사체의 자연스러운 구조 때문에 압축이 가능하다. 통계적으로 보면 가까운 화소들은 비슷한 확률이 높고 먼 화소들은 비슷할 확률이 낮다. 동영상은 대상이 빠르고 격렬하게 움직이는 때를 제외하고 한 프레임과 다음 프레임 사이의 차이가 비교적 작기 때문에 더 많이 압축할 수 있다. 자연어는 섀넌이 분석한 유형의 잉여성과 규칙성 때문에 압축할 수 있다. 오직 완전히 무작위적이어서 연달아 의외의 수밖에 나오지 않는 수열만 압축할 수 없다.

 

무작위적 수열은 '정규적'이다. 진정한 무작위적 수열은 정규적이어야 하지만 그 역이 반드시 성립하지는 않는다. 어떤 수는 통계적으로 정규적이지만 전혀 무작위적이지 않을 수 있다.

 

정규수는 파악하기 어렵다. 수의 우주에서는 정규성이 일반적이다. 수학자들은 거의 모든 수가 정규적임을 확실히 안다. 하지만 이 거대하고 일반적인 질문을 해결한 수학자들도 어떤 특정한 수가 정규적인지 결코 증명할 수 없다. 이 자체가 수학의 가장 놀랍고 기이한 점 중 하나이다.

 

파이라는 어마어마한 메시지의 첫 1조 자리 혹은 십진수로 알려진 수를 분석하느라 전 세계의 컴퓨터들이 많은 시간을 소모했다. 이 수를 보는 사람은 누구나 정규적으로 보인다고 말할 수 있다. 어떤 통계적 특징이 발견되지 않는 것이다. 어떤 평향도 상관관계도 없다. 파이는 무작위적으로 행동하는 것처럼 보이는 본질적으로 비무작위적인 수이다. n번째 수를 알아도 다음 수를 예측하는 지름길은 없다. 그다음 비트도 역시 의외의 수이다.

 

그렇다면 이 수열은 얼마나 많은 정보를 나타낼까? 이 수열은 무작의적인 수처럼 정보가 풍부할까? 혹은 질서 정연한 수열처럼 정보가 빈약할까?

 

물론 전신수는 단지 "파이"라는 메시지를 보냄으로써 키 조작을 많이 줄일 수 있다. 그러나 이는 편법이다. 발신자와 수신자 사이에 미리 공유된 지식을 전제한다. 우선 발신자가 이 특수한 수열을 인식해야 하고, 수신자는 파이가 무엇이며 그 십진법 전개를 어떻게 찾는지 혹은 계산하는지 알아야 한다. 사실상 하나의 코드북을 공유해야 하는 것이다.

 

그렇다고 해서 파이가 많은 정보를 담고 있다는 얘기는 아니다. 핵심적인 메시지는 더 적은 키 조작으로 보낼 수 있다. 얼마나 많은 십진수가 필요하든 간에 전체 정보량은 똑같다.

 

회선의 양쪽 끝이 지식을 공유한다는 문제는 상황을 복잡하게 한다. 사람들은 때로 이런 종류의 문제(메시지에 담긴 정보량의 문제)를 먼 은하계에서 외계 생명체와 의사소통하는 문제로 표현하기도 한다. 

 

메시지의 발신자는 수신자의 머릿속에 든 코드북을 절대 완전히 알 수 없다. 창문에서 깜박이는 두 번의 불빛은 아무 뜻이 없을 수도 있고, '영국군이 바다로 온다'를 뜻할 수도 있다. 시의 메시지는 독자들마다 다르게 읽는다. 이런 사고의 논리에서 모호함을 제거하는 방법이 있다. 체이틴의 말을 들어보자.

 

멀리 있는 친구가 아니라 디지털 컴퓨터와의 의사소통을 생각하는 것이 바람직하다. 친구는 수를 추론하거나 불완전한 정보 혹은 모호한 지시문을 보고 수열을 구성하는 지적 능력을 가졌을 수도 있다. 컴퓨터는 이런 능력이 없으나, 우리 입장에서는 이런 결함이 장점이 된다. 컴퓨터에 주어지는 지시문은 완전하고 명시적이어야 하며, 컴퓨터가 단계별로 진행할 수 있도록 만들어야 한다.

 

다시 말하지만, 메시지는 알고리즘이다. 또한 수신자는 기계이다. 즉, 창의성도 없고 불확실성도 없으며, 기계 안에 내장된 '지식' 외에는 아무런 지식이 없다. 1960년대가 되자 디지털 컴퓨터는 이미 지시문을 비트로 측정되는 형식으로 받기 시작했다. 따라서 어떤 알고리즘에 얼마나 많은 정보가 포함됐는지 생각하는 것이 당연했다.

 

 

바흐가 지은 창작물의 핵심을 담은 음표 기록인 악보가 더 명확한 메시지를 담은 것일까? 더 일반적으로 말해 메시지를 해독하기 위하여 회선의 반대쪽에서는 어떤 종류의 지식(어떤 종류의 코드북)이 필요한 것일까? 소리(음표)는 무리지어 있다. 말하자면 소리는 선율로 불리는 형태를 형성하며, 묵시적 문법의 규칙들을 따른다. 음악은 지역 및 역사와 무관한 고유의 논리를 갖는 것일까?

 

비트와 관련해서 보면 바흐의 전주곡은 정보가 전혀 많지 않은 것처럼 보일지도 모른다. 바흐가 두 페이지에 걸쳐 펜으로 쓴 이 곡은 단출한 문자의 부호인 600개의 음으로 구성된다. 1964년 글렌 굴드가 간결한 지시문에 연주자의 뉘앙스와 변주를 더하면서 피아노로 이 곡을 연주했을 때 1분 36초가 걸렸다. CD에 저장하면 1억 3,500만 비트가 된다. 그럼에도 이 비트 스트림은 아무런 정보 손실 없이 상당히 압축할 수 있다. 미디 프로토콜과 함께 인코딩하면 수천 비트면 된다. 심지어 기본적인 600개의 부호 메시지는 엄청난 잉여성이 있다. 변하지 않는 박자, 균일한 음색, 마지막 소절까지 조금씩 변주되면서 거듭 반복되는 한 단어 같은 간결한 선율적 패턴이 있는 것이다. 

 

유명한 얘기지만 믿을 수 없을 정도로 단순하다. 반복 자체가 예상을 만들고 예상을 깬다. 거의 아무것도 일어나지 않으며, 모든 것이 의외이다. "눈부시게 하얀 하모니를 지닌 불멸의 분산 화음." 이 곡은 렘브란트의 그림이 단순한 것과 같은 방식으로 단순하다. 이 곡은 적은 것을 가지고 많은 것을 하낟. 그렇다면 정보가 풍부할까? 어떤 음악은 정보가 빈약하다고 볼 수 있다. 

 

음악은 시 그리고 모든 예술과 마찬가지로 완벽하게 이해하기가 불가능하다. 음악의 바닥을 찾을 수 있다면 음악은 지루해지고 말 것이다. 

 

따라서 최소 프로그램 크기로 복잡성을 정의하는 것이 완벽해 보인다. 섀넌의 정보이론과도 아주 잘 어울린다. 하지만 달리 보면 여전히 매우 불만족스럽다. 특히 예술, 생물학, 지성가 같은 거대 질문(혹자는 인류의 문제라고 말할 수도 있을 것이다)에 대해서는 더욱 그렇다. 

 

최소 프로그램 크기로 측정하는 방법에 따르면 100만 개의 0과 100만 번의 동전 던지기는 스펙트럼의 양극단에 존재한다. 무의미한 수열은 굉장히 단순하고, 무작위적 수열은 극도로 복잡하다. 0들은 아무 정보도 전달하지 않지만 동전 던지기는 최대의 가능한 정보를 생성한다. 그럼에도 이 극단적인 두 수열은 공통점이 있다. 둘 다 지루하고 아무 가치가 없는 것이다.

 

우리가 중요하게 생각하는 모든 것은 패턴과 무작위성이 얽히는 곳 중간 어딘가에 존재한다. 베넷은 '논리적 깊이'라는 새로운 가치 척도 연구를 진행 했다. 베넷의 개념은 복잡성과 관련이 있지만 다른 면도 있었다. 깊이는 (어떤 특정한 영역에서 유용성이 무엇을 의미하든 간에) 메시지의 유용성을 포착한다는 것을 의미했다. 마침내 1988년 베넷은 자신의 개념을 내놓으면서 이렇게 썼다.  "정보이론이 태동할 때부터 정보 그 자체는 메시지가 지닌 가치의 좋은 척도가 될 수 없다는 사실을 인식하고 있었다."

 

동전을 던져서 나온 전형적인 수열은 정보량은 많지만 가치는 거의 없다. 반면 100년 동안 매일 달과 행성의 위치를 알려주는 천문력은 계산에 필요한 운동의 방정식과 초기조건보다 많은 정보는 갖고 있지 않지만, 천문력을 보는 사람이 이 위치들을 다시 계산하는 수고를 덜어준다.

 어쨌든 계속해서 일만 하는 튜링기계를 염두에 두고 만든 이론에서는 어떤 것을 연산하는 데 필요한 일의 양이 대개 무시(배제)되었다. 베넷은 일의 양을 다시 끄집어냈다. 메시지에서 순전히 무작위성과 예측 불가능성만 있는 부분에는 논리적 깊이가 없다. 명백한 잉여성, 즉 평범한 반복과 복제만 있는 부분에도 논리적 깊이가 없다. 

 

베넷의 말을 들어보자. 메시지의 가치는 "묻혀 있는 잉여성으로 부를 수 있는 것, 즉 어렵게 예측할 수 있는 부분, 원칙적으로 수신자가 말을 듣지 않고도 파악할 수 있지만 돈이나 시간 혹은 연산 측면에서 상당한 비용을 치러야만 하는 것"에 있다. 우리는 대상의 복잡성 혹은 정보량을 평가 할 때 숨겨진 지루한 연산을 감지한다. 이는 음악이나 시, 과학 이론, 낱말풀이에도 해당하는데, 이런 것들은 너무 불가해하거나 얄팍하지 않고 그 중간 어딘가에 있을 때 푸는 사람에게 즐거움을 준다.

 

수학자와 논리학자들은 정보처리가 물을 긷거나 돌을 나르는 일과 달리 그저 이뤄진다고 생각하는 경향이 있다. 우리 시대에는 확실히 정보처리가 저렴해졌다. 하지만 정보처리는 결국 일을 포함하고 있다. 베넷은 우리가 이 일을 인식하고 복잡성을 이해하는 데 드는 비용을 계산해야 한다고 말한다. "어떤 것이 은밀할수록 발견하기가 어렵다."

 

베넷은 논리적 깊이 개념을 자기 조직화의 문제, 즉 자연에서 복잡한 구조가 어떻게 발달하는지에 대한 질문에 적용한다. 진화는 단순한 초기조건에서 시작된다. 분명히 이를 기반으로 복잡성이 발생한다. 어떤 기본적 과정이 개입하든 물리적이든 생리적이든 간에, 연산과 닮아가기 시작하는 어떤 것이 진행된다.