콜모고로프 복잡도(Kolmogorov complexity)

0과 1을 번갈아 백만 번 적은 문자열은 '01을 50만 번 출력하라'는 짧은 프로그램으로 줄일 수 있습니다. 동전을 백만 번 던져 적은 문자열은 거의 틀림없이 그 문자열을 통째로 출력하는 것보다 크게 짧게 쓸 방법이 없습니다(얼마나 확실한지는 아래에서 셉니다). 1960년대 중반 미국의 레이 솔로모노프, 소련의 콜모고로프, 아르헨티나계 미국 수학자 그레고리 차이틴은 각자 이 차이를 수로 만들었습니다. 문자열 x의 콜모고로프 복잡도 $K(x)$는 고정된 보편 튜링 기계⁠(Turing machine)⁠ U에서 x를 출력하고 멈추는 가장 짧은 프로그램의 길이입니다. 보편 튜링 기계⁠(universal Turing machine)⁠는 다른 어떤 튜링 기계든 흉내 내는 기계이니, U를 고르는 일은 프로그래밍 언어 하나를 고르는 일에 해당합니다. 언어를 바꾸면 값이 달라지지 않을까요? 한 언어로 다른 언어의 해석기(그 언어로 쓴 프로그램을 읽어 그대로 실행해 주는 프로그램)를 짜 두면 되니, 차이는 해석기 길이만큼의 상수, 곧 x와 상관없는 상수를 넘지 않습니다(불변성 정리⁠, invariance theorem⁠). 이 정리는 보편 기계⁠(universal machine)⁠가 다른 기계를 흉내 낼 수 있다는 사실만으로 증명됩니다. 튜링 기계가 아닌 다른 합리적인 계산 모형으로 바꿔도 같은 결론이 나리라는 기대는 처치–튜링 논제⁠(Church–Turing thesis)⁠에 기댑니다.

진짜 K는 계산할 수 없으니(아래에서 봅니다) 아주 작은 언어로 흉내 내 봅시다. 이 언어의 프로그램은 0과 1, 그리고 괄호 안의 것을 k번 되풀이하라는 $(\ldots \times k)$만 씁니다. 예를 들어 (01×3)1은 0101011을 출력합니다. 프로그램 길이는 글자 수입니다. 가장 짧은 프로그램은 부분 문자열마다의 최적 답을 표에 채워 가는 동적 계획법⁠(dynamic programming)⁠으로 정확히 찾을 수 있고, 답은 되풀이 안에 되풀이가 든 재귀⁠(recursion)⁠적인 모양입니다. 문자열: . 비트를 눌러 뒤집어 보세요.

가장 짧은 프로그램: ()

대부분의 문자열은 줄어들지 않습니다. 길이가 n − c보다 짧은 이진 프로그램은 길이 0부터 n − c − 1까지 모두 합쳐 $2^{n-c} - 1$개이고, 프로그램 하나는 문자열 하나만 출력합니다. 그러니 n비트 문자열 $2^n$개 가운데 $K(x) \lt n - c$인 것, 곧 c비트보다 많이 줄어드는 것은 $2^{-c}$보다 적은 비율입니다(비둘기집 원리⁠, pigeonhole principle⁠). 동전을 던져 얻은 문자열이 10비트 넘게 줄어들 확률⁠(probability)⁠은 1,000분의 1도 되지 않습니다. 장난감 언어에서도 마찬가지입니다. 길이 12인 문자열 4096개를 모두 가장 짧게 적어 보면

그래서 콜모고로프 복잡도는 '무작위'의 정의가 됩니다. 상수 c를 하나 정해 두고 $K(x) \ge |x| - c$인 문자열, 곧 c비트보다 많이 줄일 수 없는 문자열을 무작위라 부릅니다. 유한한 문자열에서 무작위는 이처럼 정도의 문제입니다. 계산 가능한 확률분포⁠(probability distribution)⁠에서 독립적으로 뽑은 기호들로 된 문자열이라면, K를 길이로 나눈 값이 길이가 길어질수록 확률 1로 그 분포의 엔트로피⁠(entropy)⁠로 수렴⁠(convergence)⁠합니다. 섀넌의 원천 부호화 정리⁠(source coding theorem)⁠를 문자열 하나에 대한 말로 옮긴 셈입니다. 렘펠–지브 압축⁠(Lempel–Ziv compression)⁠ 같은 압축기가 만든 파일 길이에 풀기 프로그램의 길이를 더하면 K의 위쪽 어림이 됩니다.

그런데 K는 계산할 수 없습니다. 복잡도가 백만보다 큰 문자열은 위의 셈에 따라 반드시 있습니다. 만약 K를 계산하는 프로그램이 있다면, '문자열을 짧은 것부터 차례로 훑으며 K를 계산해, 복잡도가 백만보다 큰 첫 문자열을 출력하라'는 프로그램을 만들 수 있습니다. 이 프로그램의 길이는 K를 계산하는 부분에 백만이라는 수를 적는 몇십 비트를 더한 것이라 백만보다 훨씬 짧으니, 복잡도가 백만보다 큰 문자열을 그보다 짧은 프로그램이 출력한 셈이 되어 모순입니다('백 글자 안으로 정의할 수 없는 가장 작은 자연수⁠(natural number)⁠'는 방금 백 글자 안으로 정의되었다는 베리 역설⁠(Berry paradox)⁠과 같은 모양입니다. 러셀이 옥스퍼드 도서관 사서 G. G. 베리에게서 들었다며 소개한 역설입니다). 이것은 정지 문제와 이어져 있습니다. 짧은 프로그램들을 모두 돌려 보면 되지 않느냐고 할 수 있지만, 어떤 프로그램이 끝내 멈출지 알 수 없습니다. 차이틴은 같은 논증으로 불완전성 정리⁠(incompleteness theorem)⁠의 한 판을 얻었습니다. 산수를 담을 만큼 강하고, 증명을 기계가 검사할 수 있는 무모순⁠(consistent)⁠ 형식 체계⁠(formal system)⁠에는 저마다 한계 L이 있습니다. 길이가 L보다 긴 문자열은 거의 전부 'K(x) > L'인데도, 그 체계는 어느 특정한 x에 대해서도 'K(x) > L'을 증명하지 못합니다. 그런 증명을 찾아 x를 출력하는 프로그램이 L보다 짧아질 수 있기 때문입니다. 이 모든 논증의 바탕은 짧은 프로그램이 몇 개 안 된다는 셈입니다. 같은 까닭으로 프로그램은 모두 합쳐 가산 개뿐이어서, 대부분의 실수⁠(real number)⁠는 어떤 프로그램으로도 적을 수 없습니다.

이어지는 곳. π의 이진 전개⁠(binary expansion)⁠나 망델브로 집합⁠(Mandelbrot set)⁠은 복잡해 보이지만 짧은 프로그램이 만들어 내니 K는 작습니다. 위의 'π의 이진 전개'는 장난감 언어로는 거의 줄지 않지만, 제대로 된 언어라면 앞 n자리를 출력하는 데 π를 계산하는 짧은 프로그램과 n을 적는 약 $\log_2 n$비트면 충분합니다. 이 위키의 그림들이 쓰는 '무작위' 수도 씨앗(난수 생성기에 처음 넣는 수) 하나에서 정해진 계산으로 나오니 K가 작습니다(무작위 알고리즘⁠(randomized algorithm)⁠, 몬테카를로 방법⁠(Monte Carlo method)⁠). '모형을 적는 길이 + 그 모형으로 데이터를 적는 길이'가 가장 짧은 모형을 고르라는 최소 기술 길이⁠(minimum description length)⁠ 원리(1978년 핀란드의 요르마 리사넨)는 이 생각을 학습에 옮긴 것입니다. 데이터를 통째로 외운 모형은 모형 자체가 길어지므로, 이 원리는 과적합⁠(overfitting)⁠을 막습니다. 설명이 같다면 가정이 적은 쪽을 택하라는 오컴의 면도날(14세기 영국 철학자 오컴의 윌리엄의 이름을 땀)을 수로 적은 셈입니다. 물리학에서는 비트를 지우는 데 드는 열의 최솟값이 란다우어 원리⁠(Landauer's principle)⁠로 정해집니다(무작위 비트 하나에 $k_B T \ln 2$. $k_B$는 볼츠만 상수⁠(Boltzmann constant)⁠, T는 절대 온도⁠(absolute temperature)⁠). 줄일 수 있는 비트열은 되돌릴 수 있는 방식으로 먼저 압축한 뒤 지우면 그만큼 덜 듭니다.