#09 인포메이션 정보이론

 

제 7 장. 정보이론

내가 추구하는 것은

평범한 두뇌일 뿐입니다

 

섀넌은 펜타곤의 루스벨트와 전시내각집무실의 처칠을 잇는 음성통화를 암호화하는 엑스 시스템을 개발했다. 섀넌의 임무는 엑스 시스템을 설계하는 것이 아니라 엑스 시스템을 이론적으로 분석하고, 이를 해독할 수 없음을 증명하는 것이었다.

 

기계가 생각하는 것을 배울 수 있을까? 섀넌이 전자두뇌에 음악 같은 "문화적인것"을 입력하는 것을 제안하자, 튜링은 "'강력한' 두뇌를 개발하는 일에는 관심이 없습니다. 제가 추구하는 것은 AT&T 회장의 두뇌처럼 '평범한' 두뇌일 뿐입니다." 트랜지스터와 전자 컴퓨터가 아직 개발도지 않은 1943년, 생각하는 기계를 말하는 것은 다소 시건방진 일이었다. 하지만 섀넌과 튜링이 함께 생각했던 것은 전자공학과 아무 관련이 없었다. 그건 논리에 대한 것이었다.

 

'기계가 생각할 수 있을까?' 이 질문이 특이한 이유는 기계 자체가 너무나 확고하게 물리적이기 때문이었다. 기계가 할 수 있는 일에 대한 문제는 이런 물음과 함께 제기되었다. '기계적인' 일은 무엇인가. 기계가 음악을 연주하고, 이미지를 포착하고, 대공포를 겨냥하고, 통화를 연결하고, 조립라인을 제어하고, 수학적 계산을 할 수 있었기 때문에 기계적이라는 말이 경멸적이지만은 않았다. 정해진 경로를 따라 자동으로 이뤄지는 '기계적인' 일에 상반되는 특질이었다. 이제 이 개념은 철학자들이 다루는 주제가 되었다. 지적인 연구대상에서 기계적이라고 부를 수 있는 것으로는 알고리즘이 있다. 20세기가 되자 알고리즘은 중심에 서게 된다.

 

수학에는 풀리지 않은 문제들이 많았다. 하지만 대부분의 사람들은 '아직' 증명되지 않았을 뿐이라고 생각했다. 언젠가는 증명될 것이라고 여겨졌고, 심지어 이를 믿기까지 했다.

 

'결정 문제'는 특정한 연역 추론의 형식 언어에 따라 증명을 자동으로 수행할 수 있는 엄밀한 절차를 찾는 것이다. 이는 모든 타당한 추론을 기계적 규칙으로 표현한다는 라이프니츠의 꿈을 다시 한 번 되살렸다. 수학과 논리학이 갈림길에 섰던 바로 그때 괴델이 불완전성 정리를 내놓는다. 이는 낙관주의에 대한 완벽한 해독제였다.

 

힐베르트는 세 가지 질문을 던졌다.

수학은 완전한가?

수학은 모순이 없는가?

수학은 결정 가능한가?

 

괴델은 수학이 완전할 수 없으며, 무모순적일 수도 없음을 증명했다. 하지만 세 번째 질문에 대해서는, 분명하게 답하지 않았다. 비록 형식논리학이라는 특유의 닫힌 체계는 그 체계 안에서 증명할 수도, 반증할 수도 없는 진술이 반드시 있다 하더라도 외부의 심판, 말하자면 외부의 논리나 규칙에 의해 결정된다고 생각할 수도 있었다.

 

앨런 튜링은 완전히 다른 질문을 제기했다. "모든 수는 연산이 가능한가?" ** 괴델은 말년에 "튜링의 작업 덕분에 나의 증명이 산술을 포함한 '모든' 형식 체계에 적용된다는 사실이 완전히 명료해졌다."라고 썼다.**

 

튜링은 어떤 식으로든 명명하고 정의할 수 있지만 연산할 수 '없는' 수가 있을지 모른다는 진술을 했다. 이것이 의미하는 바는 뭘까? 튜링은 한정된 수단으로 그 수의 십진표기를 계산할 수 있는 수를 연산 가능한 수라고 정의한다. 튜링은 이렇게 말한다. "이런 정의가 타당한 이유는 인간의 기억이 필연적으로 한계가 있기 때문이다." 또한 튜링은 '계산'을 기계적인 절차, 즉 알고리즘으로 정의했다. 인간은 직관, 상상, 통찰의 번뜩임 같은 분명히 비기계적인 계산, 아니면 절차가 드러나지 않은 연산을 통해 문제를 해결했다. 튜링은 말로 표현할 수 없는 것들을 제거해야 했다. 말 그대로 기계가 무엇을 할 수 있는지를 질문했던 것이다. "나의 정의에 의하면 기계가 십진 전개할 수 있는 수는 계산 가능하다."

 

튜링이 자신의 기계에 반드시 필요한 최소 항목을 열거한 것은 다음과 같다. 테이프, 기호, 상태state. '테이프'는 타자기의 종이에 해당한다. '기호'는 한 칸에 하나씩 테이프에 표시된다. 튜링은 최소주의 정신에 입각해 만들어진 기계와 어울리도록 절대 최소치인 두 개의 기호를 생각했다. 바로 0과 1로 모든 수를 표현하는 이진법이었다. '상태'는 더 많은 설명이 필요하다. 여기서 튜링은 "구성"이라는 단어를 썼는데, 이는 "마음의 상태"와 비슷하다. 기계는 한정된 수의 상태를 가진다. 특정한 상태에서 기계는 현재의 기호에 따라 하나 이상의 동작을 한다. 상태표는 사실상 기계의 지시서에 해당했다. 이것이 전부였다.

 

튜링은 일부 수(사실상 대부분의 수)가 연산 불가능하다는 사실을 증명했다. 또한 모든 수는 코드화된 수학적, 논리적 명제에 대응하므로 튜링은 모든 명제가 결정 가능한지에 대한 힐베르트의 질문도 해결한 셈이었다. '결정 문제'에는 답이 있는데, 그 답은 '아니요'라는 것을 증명한 것이다. 사실상 연산 불가능한 수는 결정 불가능한 명제이다.

 

이렇듯 상상 속에만 있고, 추상적이며, 전적으로 머릿속에만 존재하는 튜링 계산기는 튜링을 괴델과 일맥상통하는 증명으로 이끈다. 튜링은 형식 체계의 보편 개념을 정의함으로써 괴델에서 한 걸음 더 나아갔다. 공식을 생성하기 위한 모든 기계적 절차는 본질적으로 튜링기계이다. 따라서 '모든' 형식 체계는 결정 불가능한 명제를 가질 수밖에 없다. 수학은 결정 불가능하다. 이 불완전성은 연산 불가능성에서 나온다.

 

기계 자체의 운동을 숫자로 코드화할 때 다시 한 번 역설이 고개를 든다. 재귀적 순환의 필연적인 등장이었다. 인식되는 대상은 인식하는 대상과 운명적으로 얽힌다. 더글러스 호프스태터는 "중요한 것은 계속 머뭇거리는 관찰자가 그 자신을 바라보면서 자신의 행동을 예측하려 하는 자신을 바라보면서 자신의 행동을 예측하려 하는 자신을 바라보면서... 자신의 행동을 예측하려는 데 있다."

 

바로 베르너 하이젠베르크의 불확정성 원리였다. 불확정성 원리를 접한 튜링은 이를 자기참조 개념으로 표현했다. "과학은 어떤 특정한 순간 우주의 모든 것을 안다면, 앞으로 어떤 일이 벌어질지 예측할 수 있다고 가정했다. ... 하지만 최근 과학은 우리가 정확한 상태를 전혀 알 수 없는 원자와 전자를 다루고 있다는 결론에 이르렀다. 우리의 도구 자체가 원자와 전자로 이루어져 있다.

 

 

앨런 튜링과 클로드 섀넌 사이에는 코드라는 공통점이 있었다. 튜링은 지시서를 숫자로, 십진수를 0과 1로 코드화했다. 섀넌은 유전자와 염색체, 릴레이와 스위치를 나타내는 코드를 만들었다. 두 사람은 논리연산자와 전기회로, 대수 함수와 기계 지시서처럼 한 대상의 집합을 다른 대상의 집합으로 사상하는 데 자신들의 창의성을 발휘한다. 기호의 작용과 두 집합 사이의 엄격한 대응관계를 찾아낸다는 의미에서의 '사상'은 이들의 정신적 보고에서 중요한 위치를 차지했다. 이런 코드화는 숨기기 위한 것이 아니라 밝히기 위한 것, 다시 말해 사과와 오렌지가 결국 동등한 것, 그게 아니라면 대체 가능하다는 사실을 발견하기 위한 것이었다. 전쟁은 가장 수수께끼 같은 형태를 지닌 암호의 세계로 두 사람을 이끌었다.

 

암호해독자들은 쓰레기 더미 같은 데이터 안에서 진정한 신호를 찾고자 한다. 섀넌의 말을 들어보자. "암호분석가 입장에서 암호시스템은 잡음이 많은 통신시스템과 거의 같다." 데이터 흐름은 확률론적 혹은 무작위적으로 보이지만 당연히 그렇지 않다. 만약 정말로 무직위적이라면 신호를 파악할 수 없을 것이다. 암호는 패턴이 있는 것을(이를테면 일상 언어를) 패턴이 없어 보이는 것으로 바꿔야 한다. 하지만 패턴은 놀랄 만큼 끈질기게 유지된다. 섀넌은 암호화의 변환을 분석하고 분류하기 위해 학자들(가령 언어학자들)이 한 번도 시도하지 않았던 방식으로 언어의 패턴을 이해해야 했다. 하지만 언어학자들도 언어 안의 구조(희미하게 피어 오르는 형태와 소리 가운데서 발견되는 체계)에 초점을 맞추기 시작했다.

 

1921년 언어학자 사피어는 "언어에서 본질적인 것은 단순한 말소리가 아니라 범주화와 형식적 패턴화이다. ... 언어는 하나의 구조로서 내면에 사고의 틀을 지닌다." "사고의 틀"은 대단히 세련된 표현이었다. 그러나 섀넌에게 언어는 만질 수 있고 셀 수 있는 대상이어야 했다.

 

섀넌은 패턴이 잉여성과 같다고 보았다. 일상 언어에서 잉여성은 이해를 돕는 역할을 한다. 암호분석에서는 바로 그 잉여성이 아킬레스건이다. (오타가 있어도 맥락으로 문장을 이해 할 수 있는점) 't' 뒤에서는 'h'가 일정한 잉여성을 갖는다. 뒤에 나올 가능성이 가장 높은 글자이기 때문이다. 섀넌은 모든 언어가 일정한 통계적 구조와 잉여성을 갖는다고 주장했다.

 

섀넌은 영어가 약 50퍼센트의 잉여성을 가졌다고 추정했다. 가장 단순한 초기의 대치 암호에서 이런 잉여성은 첫 번째 약점이었다. 'q'를 밝히면 'u'도 쉽게 밝힐 수 있었다. 암호해독자는 the, and, -tion처럼 흔한 단어나 글자 조합에 맞는 반복적인 패턴을 찾았다.

 

모든 암호체계의 공통점은 키를 사용한다는 것이었다. 이것을 다룬 비밀 보고서에서 섀넌은 거의 지나가는 내용으로 전에는 한번도 쓴 적이 없는 말을 사용한다. 바로 "정보이론"이었다.

 

먼저 섀넌은 "의미"를 제거해야 했다. "메시지의 '의미'는 대체로 아무 상관이 없다." 이론을 만들기 위해서는 '정보'라는 단어를 납치해야 했다. "여기서 말하는 '정보'는 일상적인 의미와 관련이 있기는 하지만 그것과 혼동해서는 안 된다." (정보에서 에너지와 엔트로피가 분리되는 아이디어로 접근할 수 있을듯, 물질은 복제가 되면 질량이 늘어 에너지가 늘어나지만 정보는 복제가 되어도 물질 처럼 에너지가 크게 늘지 않는다. 하지만 엔트로피는 증가하게 되는 개념)

 

정보는 불확실성, 의외성, 어려움, 엔트로피였다.

• "정보는 불확실성과 밀접하게 연관되어 있다." 불확실성은 결국 가능한 메시지의 수를 셈으로써 측정할 수 있다. 단 하나의 메시지만 가능하다면 불확실성이 없으며, 따라서 정보도 없다.
• 어떤 메시지는 다른 메시지보다 더 그럴듯하며, 정보는 의외성을 내포한다. 의외성은 확률을 설명하는 한 방법이다. 't'나오는 글자가 'h'라면 그다지 많은 정보가 전달되지 않는다. 'h'가 나올 확률이 비교적 높기 때문이다.
• "주목할 만한 것은 메시지를 한 지점에서 다른 지점으로 전달하는 것의 어려움이다." 마치 물체를 이동하는 데 필요한 힘의 개념으로 질량을 정의하는 것처럼 말이다. 하지만 질량은 그런 방식으로 '정의될 수 있다'.
• 정보는 엔트로피이다. 엔트로피는 열과 에너지를 다루는 학문인 열역학에서 무질서의 척도였다.

 비전문가라면 통신의 근본적인 문제가 자기 말을 남에게 이해시키는 것, 즉 의미를 전달하는 것이라고 말할지도 모르지만 섀넌의 시각은 달랐다. 통신의 근본 문제는 한 지점에서 선택된 메시지를 다른 지점에 정확하게 혹은 비슷하게 재현하는 데 있다.

 

의미를 완전히 못 본 체할 수 없었던 섀넌은 의미에 다음과 같은 과학적 정의를 내려놓았다.

 

흔히 그 메시지는 '의미'를 갖는다. 말하자면 메시지는 어떤 체계에 따라 특정한 물리적 혹은 개념적 실체를 나타내거나 상관관계를 보여준다. 통신의 이러한 의미론적 측면은 공학적 문제와 무관하다.

 

통신 시스템은 다음과 같은 요소들을 포함해야 한다. 정보 소스, 송신기, 채널, 수신기, 목적지. 일상적인 대화의 경우 이런 요소들은 말하는 사람의 뇌, 성대, 공기, 듣는 이의 귀, 듣는 이의 뇌이다.

 

섀넌은 연속적인 시스템과 이산적 시스템이라는 두 가지 다른 유형의 시스템으로 잡음을 다룬다. 이산적 시스템에서 메시지와 신호는 글자나 숫자 혹은 점과 선 같은 개별적으로 분리된 신호의 형태를 지닌다. 전신이 있기는 하지만 파동과 함수의 연속적 시스템은 전기 엔지니어들이 매일 접하는 것이었다. 엔지니어라면 한 채널로 더 많은 정보를 보내는 방법을 알고 있었다. 바로 출력을 높이는 것이었다. 하지만 신호를 증폭할수록 잡음이 심해지기 때문에 이 방법이 통하지 않았다.

 

섀넌은 신호를 이산적 기호의 열로 다룸으로써 이 문제를 피해갔다. 발신자는 이제 출력을 높이는 대신 오류 정정을 위한 기호를 추가함으로써 잡음을 극복할 수 있다. 이는 마치 아프리카의 북꾼들이 북을 더 세게 치는 것이 아니라 이야기를 장황하게 늘림으로써 멀리 의사를 전달한 것과 같은 이치였다. 섀넌은 이산적 방법이 수학적 의미에서도 더 근본적이라고 생각했다. 아울러 섀넌은 또 다른 지점을 고려했다. 메시지를 이산적으로 처리하는 방법은 전통적 통신뿐만 아니라 계산기계 이론이라는 새롭고 다소 난해한 하위 분야에도 적용할 수 있었다.

 

그리하여 섀넌은 다시 전신으로 돌아갔다. 정확하게 분석하면 전신은 점과 선이라는 두 가지 기호만으로 된 언어를 사용하는 것이 아니었다. 실제로 전신수들은 점("회선 닫힘, 회선 열림")과 선(세 단위 회선 닫힘과 한 단위의 회선 열림) 말고도 서로 구별되는 두 개의 공백도 활용했다. 바로 글자 간 공백(대개 세 단위의 회선 열림)과 더 긴 단어 간 공백(여섯 단위의 회선 열림)이었다. 이 네 가지 기호는 다른 위상과 확률을 지닌다. 가령 점이나 선은 어떤 기호 뒤에도 나올 수 있지만 공백은 절대 공백 뒤에 나올 수 없다.

 

섀넌은 이 상태를 '상태' 개념으로 표현했다. 섀넌에 따르면 전신 시스템은 두 가지 상태를 지닌다. 하나의 상태에서는 공백이 이전 기호였다면 점이나 선만 허용되고 그 다음에는 상태가 바뀐다. 다른 상태에서는 모든 기호가 허용되고 공백이 전송된 경우에만 상태가 바뀐다. 

 

이 구조는 단순한 이진 인코딩 체계와 많이 달랐다. 그럼에도 불구하고 섀넌은 정보량과 채널 용량을 구하는 정확한 공식을 유도하는 방법을 보여준다. 더 중요한 것은 섀넌이 메시지를 구성하는 언어의 통계적 구조가 미치는 영향에 초점을 맞췄다는 것이다. 바로 이 구조가 존재하기 때문에('q'보다 'e'가, 'xp'보다 'th'가 더 빈도가 크기 때문에) 시간이나 채널 용량을 절약할 수 있다.

 

메시지의 구조를 밝히기 위해 섀넌은 브라운 운동에서 천체물리학에 이르기까지 확률과정을 다루는 물리학 방법론과 언어에 의지한다. 확률과정은 결정론적이지도, 무직위적이지도 않다. 확률에 의해 좌우되는 것이다. 각각의 사건은 확률적인데, 이는 시스템의 상태 그리고 아마도 이전 사건에 따라 좌우된다. 여기서 '사건'을 '기호'로 대체하면 영어나 중국어 같은 자연적 문어도 확률과정이 된다. 디지털화된 말이나 텔레비전 신호도 마찬가지이다.

 

좀 더 깊이 파고든 섀넌은 메시지가 다음 기호의 확률에 미치는 영향과 관련한 통계적 구조를 분석했다. 결론적으로 아무 영향이 없을 수도 있었다. 다시 말해 각 기호는 고유한 확률을 지니며 이전 기호에 좌우되지 않을 수 있다. 이것이 1차 사례이다. 2차 사례의 경우 각 기호의 확률은 직전 기호에만 좌우될 뿐 다른 모든 기호와는 무관하다. <계속 확률 이야기는 생략>

 

섀넌이 생각했듯이 메시지는 동역학계처럼 움직였다. 과거의 역사에 의해 미래의 경로가 결정되는 것이다.(복잡계의 역사의존성)

 

• "0차 근삿값" : 각 글자가 아무 구조나 상관관계 없이 무작위로 나열.
  XFOML RXKHRJFFJUJ ZLPWCFWKCYJ
  FFJEYVKCQSGHYD QPAAMKBZAACIBZLHJQD.
• 1차 : 각 글자는 서로의 영향을 받지 않지만 통계적 빈도를 따름.
  OCRO HLI RGWR NMIELWIS EU LL NBNESEBYA
  TH EEI ALHENHTTPA OOPTTVA NAH BRL.
• 2차 : 각 글자와 두 글자의 조합이 통계적 빈도를 따름.
  ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIND
  ILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBESEACE CTISBE.
• 3차 : 세 글자 조합 구조.
  IN NO IST LAT WHEY CRATICT FROURE BIRS GROCID
  PONDENOME OF DEMONSTURES OF THE REPTAGIN IS
  REGOCTIONA OF CRE.
• 1차 단어 근삿값.
  REPRESENTING ADN SPEEDILY IS AN GOOD APT OR COME CAN
  DIFFERENT NATURAL HERE HE THE A IN CAME THE TO OF TO
  EXPERT GRAY COME TO FURNISHES THE LINE MESSAGE HAD BE THESE.
• 2차 단어 근삿값 : 단어의 쌍이 예상 빈도로 나타남.
  THE HEAD AND IN FRONTAL ATTACK ON AN ENGLISH
  WRITER THAT THE CHARACTER OF THIS POINT IS
  THEREFORE ANOTHER METHOD FOR THE LETTERS THAT
  THE TIME OF WHO EVER TOLD THE PROBLEM FOR AN UNEXPECTED.

이 기호열들은 점점 더 영어처럼 '보인다.' 좀 더 객관적으로 보면 타자수들은 이 기호열들을 갈수록 빠르게 칠 수 있는 것으로 드러난다. 이는 사람들이 무의식적으로 언어의 통계적 구조를 내면화하는 방식을 보여주는 또 다른 예시였다.

 

섀넌은 추가 근삿값을 만들 수 있었지만 요점은 메시지를 이산적 확률로 사건을 발생시키는 프로세스의 결과로 나타내는 것이었다. 그렇다면 정보량 혹은 정보 생성률에 대해 무엇을 말할 수 있을까? 각 사건에서 가능한 선택들은 정해진 확률을 갖는다. 섀넌은 'H'로 표기되는 정보의 척도를 "사건에 '선택'이 얼마나 개입하는지 혹은 결과가 얼마나 불확실한지" 말해주는 불확실성의 척도로 정의하려 했다.

 

각각의 확률은 같거나 다를 수 있다. 하지만 일반적으로 선택지가 많다는 것은 보다 큰 불확실성, 보다 많은 정보를 의미한다. 선택은 각각 확률이 가지는 일련의 순차적 선택으로 나눌 수 있으며, 이 확률은 가법적이어야 한다. 이를테면 특정한 두 글자 조합의 확률은 개별 기호가 지닌 확률의 가중 총합이었다. 이 확률들이 같다면 각 기호가 전달하는 정보량은 가능한 기호 개수의 로그일 뿐이다. 이를 표현한 것이 바로 나이키스트와 하틀리의 공식이었다.

 

H=n log s

 

더 현실적인 사례에서 섀넌은 확률 함수로 정보를 측정하는 명쾌한 해결책을 내놓는다. 바로 로그 가중치를 둔(밑을 2로 삼는 것이 가장 편리했다) 확률의 합을 구하는 공식이었다. 이는 메시지의 불가능성을 보여주는 평균 로그로, 사실상 의외성의 척도였다.

 

H = - Σpi log2 pi

 

여기서 pi는 각 메시지의 확률을 가리킨다. 섀넌은 이 공식의 값은 "정보이론에서 정보, 선택, 불확실성의 척도로서 중심적인 역할을 한다"라고 주장했다. 실제로 H는 어디에나 존재하며, 통상적으로 메시지의 엔트로피 혹은 섀넌 엔트로피 아니면 간단히 정보로 불렸다.

 

측정의 새로운 단위가 필요했다. "귀결되는 단위는 바이너리 디지트(이진 부호) 또는 줄여서 '비트bit'라고 부를 수 있다. 1비트는 가능한 최소 정보량으로 동전을 던질 때 나오는 불확실성의 양을 나타낸다. 동전 던지기는 동일한 확률을 가진 두 가능성 사이의 선택을 나타낸다. 이 경우 p1과 p2는 각각 2분의 1이며, 밑이 2인 2분의 1의 로그는 -1이다. 따라서 H는 1비트이다.

- (1/2 + 1/2) x log2 (1/2) = 1

 

이 지점에서 자연어의 통계적 구조가 다시 개입된다. 만약 1,000자로 된 메시지가 영어 텍스트라면 가능한 메시지의 수는 '훨씬' 적다. 섀넌은 여덟 자까지의 상관관계를 살펴서 영어에 약 50퍼센트의 잉여성이 내재해 있다고 추정했다. 따라서 메시지에 새로 포함되는 각 글자는 5비트가 아니라 약 2.3비트의 정보만 전달한다.

 

섀넌은 아내를 대상으로 실험을 했다. 뒤에 오는 단어를 맞히지 못했지만 첫 글자가 'D'인 것을 안 후에는 다음 세 글자를 쉽게 맞혔다. "예상대로 생각이 가지를 쳐나갈 가능성이 더 높은 단어와 음절의 시작에서 오류가 더 자주 발생한다."

 

역설적으로 들리지만 무작위적 메시지가 '더 많은' 정보를 전달한다.(즉 엔트로피가 높아진다는 의미)

 

"레코드 판(128레벨)"은 약30만 비트, 두꺼운 전문저널 <무선 엔지니어 협회보>는 1,000만 비트, <브리태니커 백과사전>은 10억 비트, 한 시간 분량의 텔레비전 방송은 10의 11승비트, 한 시간 분량의 컬러영화는 1조 비트 이상으로 추정했다. 끝으로 100조 비트에 해당하는 10의 14승 비트는 자신이 생각할 수 있었던 최대 정보 저장소인 의회 도서관이었다.

이제 정보를 비트로 계산 할 수 있다는 의미