알고리즘 정보 이론: 정보의 궁극적인 복잡성을 측정하다
우리는 일상에서 '복잡하다'와 '단순하다'는 말을 자주 사용합니다. 하지만 무엇이 어떤 것을 복잡하게, 또는 단순하게 만드는 걸까요? 다음 두 개의 숫자열을 한번 살펴보시죠.
A: 0101010101010101010101010101010101010101010101010101010101010101
B: 1011001011010001011110010011101101100010011011101011010011011001
두 문자열의 길이는 같습니다. 하지만 대부분의 사람들은 A가 B보다 훨씬 '단순하다'고 느낄 것입니다. 왜 그럴까요? A는 "01을 32번 반복"이라는 아주 짧은 규칙으로 설명할 수 있지만, B를 설명하기 위해서는 그저 "B는 10110010...이다"라고 전체를 나열하는 것 외에 뾰족한 수가 없어 보이기 때문입니다. 이 직관적인 차이를 수학적으로 엄밀하게 정의하려는 시도에서 **알고리즘 정보 이론 (Algorithmic Information Theory, AIT)**이 탄생했습니다.
알고리즘 정보 이론은 정보의 복잡성을 **'그 정보를 생성하는 데 필요한 가장 짧은 컴퓨터 프로그램의 길이'**로 정의합니다. 이는 정보에 대한 우리의 관점을 근본적으로 바꾸는 혁명적인 아이디어입니다. 이 글에서는 AIT의 핵심 개념인 '콜모고로프 복잡성'을 중심으로, 이 이론이 어떻게 정보, 무작위성, 그리고 지식의 한계를 설명하는지 깊이 있게 탐구해 보겠습니다.
1. 정보 이론의 전환: 섀넌에서 콜모고로프로
AIT를 이해하기 위해서는 먼저 '정보 이론의 아버지' 클로드 섀넌(Claude Shannon)의 이론과 비교해 볼 필요가 있습니다. 섀넌의 정보 이론은 통신 공학에 지대한 영향을 미쳤습니다. 그는 정보를 확률의 관점에서 정의했습니다. 즉, 어떤 메시지의 정보량은 그 메시지가 나타날 확률이 낮을수록 (즉, 불확실성이 클수록) 크다고 보았습니다. "해가 동쪽에서 떴다"는 정보량이 거의 없지만, "내일 서울에 운석이 떨어진다"는 엄청난 정보량을 가집니다.
하지만 섀넌의 이론에는 한계가 있었습니다. 이는 개별 메시지의 '내용'이나 '구조'가 아닌, 메시지들의 '집합'이 갖는 통계적 특성에만 초점을 맞춥니다. 앞서 예시로 든 문자열 A와 B는 0과 1의 개수가 거의 같으므로, 섀넌의 관점에서는 두 문자열의 정보량이 비슷하다고 볼 수 있습니다. 우리의 직관과는 다른 결론이죠.
1960년대, 안드레이 콜모고로프(Andrey Kolmogorov), 레이 솔로모노프(Ray Solomonoff), 그레고리 차이틴(Gregory Chaitin)은 독립적으로 이 문제에 대한 새로운 해법을 제시했습니다. 그들은 정보의 양을 확률이 아닌 **'알고리즘'**과 **'계산'**의 관점에서 정의하고자 했습니다. 이것이 바로 알고리즘 정보 이론의 시작입니다.
2. 콜모고로프 복잡성이란 무엇인가? (Kolmogorov Complexity)
AIT의 심장에는 **콜모고로프 복잡성 (Kolmogorov Complexity)**이라는 개념이 있습니다. 어떤 문자열 𝑠의 콜모고로프 복잡성 𝐾(𝑠)는 다음과 같이 정의됩니다.
𝐾(𝑠) = |𝑝|
(문자열 𝑠를 출력하고 멈추는 가장 짧은 프로그램 𝑝의 길이)
여기서 '프로그램'과 '길이'를 생각하려면 기준이 되는 '컴퓨터'와 '프로그래밍 언어'가 필요합니다. AIT에서는 이론적으로 모든 컴퓨터를 흉내 낼 수 있는 가상의 컴퓨터, 즉 **보편 튜링 기계(Universal Turing Machine)**를 기준으로 삼습니다. 어떤 프로그래밍 언어(예: Python, C++)를 사용하든, 그 변환 과정은 일정한 상수 길이의 '컴파일러' 프로그램으로 처리할 수 있기 때문에, 가장 짧은 프로그램의 길이는 언어 선택에 크게 좌우되지 않습니다. 이를 **불변성 정리(Invariance Theorem)**라고 하며, 덕분에 콜모고로프 복잡성은 특정 객체의 본질적이고 내재적인 속성으로 간주될 수 있습니다.
간단한 예시: 반복과 무작위성
다시 처음의 예시로 돌아가 봅시다.
- 문자열 A ("01"이 32번 반복):
이 문자열을 생성하는 파이썬 코드는
print("01" * 32)와 같이 매우 짧습니다. 이 프로그램의 길이는 원래 문자열의 길이(64)보다 훨씬 짧습니다. 따라서 𝐾(A)는 매우 작습니다. 즉, A는 압축 가능하며 복잡성이 낮다고 말할 수 있습니다. - 문자열 B (무작위적으로 보이는 수열):
이 문자열에는 특별한 패턴이나 규칙이 보이지 않습니다. 따라서 이 문자열을 생성하는 가장 짧은 프로그램은 아마도
print("10110010...")처럼 문자열 자체를 그대로 담고 있는 프로그램일 것입니다. 이 경우, 프로그램의 길이는 원래 문자열의 길이와 거의 같습니다. 따라서 𝐾(B)는 큽니다. 즉, B는 압축 불가능하며 복잡성이 높다고 말할 수 있습니다.
여기서 우리는 '무작위성(Randomness)'에 대한 강력한 정의를 얻게 됩니다. AIT의 관점에서 **진정한 무작위 문자열이란, 자기 자신을 그대로 출력하는 것보다 더 짧은 설명(프로그램)이 존재하지 않는 문자열**입니다. 즉, 𝐾(𝑠) ≈ |𝑠| 인 문자열입니다. 이는 더 이상 압축할 수 없는, 정보가 최대로 밀집된 상태를 의미합니다.
3. 계산 불가능성의 역설: 복잡성은 측정할 수 없다
콜모고로프 복잡성은 정보에 대한 심오한 통찰을 주지만, 치명적이면서도 매력적인 특징을 하나 가지고 있습니다. 바로 '계산 불가능성(Uncomputability)'입니다.
이는 임의의 문자열 𝑠가 주어졌을 때, 그것의 콜모고로프 복잡성 𝐾(𝑠)를 계산하는 일반적인 알고리즘이 존재하지 않는다는 의미입니다. 왜 그럴까요? 증명은 귀류법을 통해 간단히 이해할 수 있습니다.
- 만약 𝐾(𝑠)를 계산하는 함수
Kolmogorov(s)가 존재한다고 가정해 봅시다. - 우리는 이 함수를 이용해 "복잡성이 N보다 큰 첫 번째 문자열을 찾아 출력하는 프로그램"을 만들 수 있습니다. 이 프로그램을
FindComplexString(N)이라고 합시다. - 이
FindComplexString(N)프로그램 자체의 길이는 N 값에 따라 약간 변하겠지만, 그 구조는 고정되어 있습니다. 이 프로그램의 길이를 C라고 합시다. - 이제 이 프로그램에 아주 큰 수, 예를 들어 'C + 100'을 입력해 봅시다. 즉,
FindComplexString(C + 100)을 실행합니다. 이 프로그램은 정의에 따라 복잡성이 C + 100보다 큰 어떤 문자열 𝑠를 찾아 출력할 것입니다. 즉, 𝐾(𝑠) > C + 100 입니다. - 여기서 모순이 발생합니다.
FindComplexString(C + 100)라는 프로그램 자체가 바로 문자열 𝑠를 생성하는 하나의 '프로그램'입니다. 그리고 이 프로그램의 길이는 C에 상수를 더한 값, 즉 C + α 정도입니다. 이는 우리가 찾은 문자열 𝑠의 복잡성(C + 100보다 크다)보다 명백히 작습니다. - 이는 "가장 짧은 프로그램"이라는 콜모고로프 복잡성의 정의에 위배됩니다. 따라서 최초의 가정, 즉 "𝐾(𝑠)를 계산하는 함수가 존재한다"는 가정이 틀렸다는 결론에 이릅니다.
이 계산 불가능성은 AIT의 실패가 아니라, 오히려 그 깊이를 보여주는 결과입니다. 이는 마치 괴델의 불완전성 정리나 튜링의 정지 문제처럼, 형식 시스템과 계산의 근본적인 한계를 드러내는 것입니다. 우리는 정보의 궁극적인 복잡성을 정의할 수는 있지만, 그것을 완벽하게 측정할 방법은 영원히 찾을 수 없을지도 모릅니다.
4. 알고리즘 정보 이론의 응용과 철학적 함의
비록 계산은 불가능하지만, AIT는 여러 과학 및 철학 분야에 지대한 영향을 미칩니다.
- 데이터 압축: AIT는 데이터 압축의 이론적 한계를 제시합니다. 콜모고로프 복잡성은 어떤 데이터를 압축할 수 있는 궁극적인 크기입니다. 우리가 사용하는 ZIP, JPEG, MP3 등의 압축 알고리즘은 모두 데이터에 내재된 패턴(낮은 콜모고로프 복잡성)을 찾아내어 정보를 더 짧게 표현하려는 시도입니다.
- 인공지능과 머신러닝: '오컴의 면도날(Occam's Razor)' 원리, 즉 "가장 단순한 설명이 가장 좋은 설명"이라는 원칙에 대한 수학적 근거를 제공합니다. 머신러닝 모델이 데이터를 단순히 '외우는' 것(높은 복잡성)이 아니라, 데이터에 숨겨진 '패턴'을 학습(낮은 복잡성의 모델로 데이터를 설명)하도록 유도하는 MDL(Minimum Description Length) 원리 등이 AIT에 뿌리를 두고 있습니다.
- 과학철학: 과학 이론의 본질을 설명하는 틀을 제공합니다. 좋은 과학 이론이란 무엇일까요? 바로 방대하고 복잡한 관측 데이터(우주, 생명 현상 등)를 설명하는 매우 짧고 우아한 '프로그램'(예: 𝐸=𝑚𝑐², F=ma)입니다. 과학의 발전 과정은 곧 우리가 관찰하는 세계의 콜모고로프 복잡성을 더 줄여나가는 과정이라고도 볼 수 있습니다.
결론: 정보의 심연을 들여다보는 창
알고리즘 정보 이론은 "정보란 무엇인가?"라는 근본적인 질문에 대해 '계산'이라는 새로운 렌즈를 제공했습니다. 그것은 정보의 복잡성을 확률적 우연이 아닌, 내재된 구조와 설명 가능성의 문제로 전환시켰습니다.
콜모고로프 복잡성은 우리에게 단순함과 복잡함, 질서와 무작위성 사이의 경계를 명확히 보여줍니다. 비록 우리가 그 값을 직접 계산할 수는 없을지라도, 그 개념 자체는 우리가 세상을 이해하는 방식에 깊은 영감을 줍니다. 무한히 긴 무작위 문자열 속에 숨겨진 패턴을 찾는 일, 방대한 데이터 속에서 가장 간결한 설명을 찾아내는 인공지능, 그리고 혼돈처럼 보이는 우주 현상을 단 몇 줄의 방정식으로 꿰뚫는 과학 이론까지. 이 모든 지적 활동은 본질적으로 정보의 콜모고로프 복잡성을 낮추려는, 즉 **세상에 대한 가장 짧고도 완벽한 '프로그램'을 찾으려는 위대한 여정**일 것입니다. 알고리즘 정보 이론은 바로 그 여정의 지도이자 나침반이라 할 수 있습니다.