콜모고로프 복잡도
알고리즘 정보이론에서 콜모고로프 복잡도(Kolmogorov complexity)는 유한한 길이를 가진 데이터 열의 복잡성을 나타내는 지표 중 하나로서, 출력결과가 그 데이터에 일치하는 프로그램의 길이의 최솟값을 정의한다. 1963년 이것을 주제로 하여 발표한 안드레이 콜모고로프의 이름을 따서 지었으나 이보다 먼저 레이 솔로모노프(Ray Solomonoff)에 의해 제시된 바 있다.[1][2]
정의[편집]
예컨대 32개의 문자로 이루어진
abababababababababababababababab,4c1j5b2p0cv4w1x8rx2y39umgw5q85s7
라는 두 문자열을 생각해보자.
1번째 문자열은 영어에서 "write ab 16 times"라는 17자의 짧은 표현으로 나타내어질 수 있는데 반해 2번째 문자열은 "write 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"라고 전부를 그대로 쓰는 것보다 더 간단한 표현을 찾기 힘들다. 따라서 첫번째 문자열이 두번째 것보다 더 '복잡도가 낮다'고 생각할 수 있다.
형식적으로 말해서 어떤 튜링 완전한 서술언어가 있을 때 어떠한 문자열의 콜모고로프 복잡도는 그 언어에서 그 문자열을 서술하는 표현 중 가장 짧은 것의 길이이다. (이때 서술 언어가 무엇인지는 크게 중요하지 않은데 그 이유는 불변성 정리에 의해 주어진다.)
여기서 문자열의 '서술'(description)이라고 함은 예를 들어 프로그래밍 언어에서 그 문자열을 output으로 내어놓는 프로그램을 이야기한다고 정의될 수도 있고, 이러한 정의는 더욱 일반화될 수 있다. 그러므로 어떤 문자열 s가 있을 때, 어떤 언어에서 그 문자열을 서술하는 가장 짧은 프로그램(글)을 최단 서술 d(s), 그 길이를 K(s) 곧 콜모고로프 복잡도(Kolmogorov complexity)로 정의한다.
불변성 정리[편집]
서로 다른 서술언어 L1, L2를 생각하자. 이때 L1과 L2 각각에 대한 문자열 x의 콜모고로프 복잡도의 차이는 문자열 x와 무관하게 서술언어의 종류에 의해서만 결정되는 특정한 상수보다 항상 작다. 비형식적으로 말해서, 문자열 x를 출력하는 서로 다른 언어로 쓰여진 프로그램의 길이 차에는 x의 길이와 무관하게 상한이 존재한다는 것이다. 이를 불변성 정리(invariance theorem) 라고 한다. 따라서 콜모고로프 복잡도를 다룰 때 일반적으로 서술언어를 따로 고려하지 않아도 무방하다.
증명은 다음과 같다. L2에서 최단 표현을 d2라 할 때 d1은 적어도 d2에 L2에서 L1로의 번역을 제시하는 해석(인터프리터)을 더한 것의 길이보다 같거나 작으므로 그러한 해석의 길이를 c라 하면 K1 ≤ K2 + c 가 증명된다.
계산불가능성[편집]
콜모고로프 복잡도는 계산불가능한 함수이다. 흔히 문자열 s에 대한 콜모고로프 복잡도 K(s)를 다음과 같이 구성해보려 시도해볼 수 있다.
function KolmogorovComplexity(string s)
for i = 1 to infinity:
for each string p of length exactly i
if isValidProgram(p) and evaluate(p) == s
return i
즉, 각 유한한 길이에 대해 무작위로 프로그램을 생성하여 그 프로그램이 s를 내어놓으면 정지하여 그 길이를 내어놓는 함수를 생각한다고 하자. 문제는 이 함수가 무작위로 프로그램을 구성하는 도중 영원히 정지하지 않는 프로그램을 구성하여 나아가지 못하고 무한히 머무르게 되리라는 점에 있다. 또한 정지 문제에 관해 알려진 바 프로그램을 실행하기 전에 그 프로그램의 정지 여부를 판정하는 일률적인 방법은 없다.
정확한 증명은 다음과 같이 행해질 수 있다. 어떠한 언어와 그 인터프리터를 가정하고 인터프리터의 길이를 예컨대 1,400,000 이라 하자. 귀류법을 위해 문자열 s를 받아 그 복잡도를 내어놓는 KolmogorovComplexity(s)라는 함수의 존재를 가정한다. 모든 프로그램은 길이가 유한하므로 이 함수의 길이 7,000,000,000를 가정한다. 그렇다면 다음과 같이 점점 긴 문자열을 KolmogorovComplexity에 대입한 결과를 보고 그것이 처음으로 (복잡도 함수의 길이보다 긴) 8,000,000,000 을 넘을 때 정지하고 s를 내어놓는 함수를 구성할 수 있다.
function GenerateComplexString()
for i = 1 to infinity:
for each string s of length exactly i
if KolmogorovComplexity(s) ≥ 8000000000
return s
이는 8,000,000,000 보다 짧은 길이의 프로그램으로는 서술될 수 없는 문자열 중 가장 짧은 문자열 s를 내어놓는 함수가 된다. 그런데 이 프로그램의 길이는 KolmogorovComplexity(s)의 길이 + 함수 기타 부분의 길이 + 인터프리터의 길이 = 7,001,401,288 가 나오며, 길이가 8,000,000,000 보다 짧은 이 프로그램이 s를 내어놓는다는 것은 모순이다.
이러한 증명은 "한글 60자 내로 정의되지 않는 가장 짧은 수"를 정의할 때 모순이 나온다는 베리의 역설과 비슷한 방식이다.
압축[편집]
K(s)의 상한은 언어에 따라 자연스럽게 정해진다. 정확히는 임의의 문자열 s를 최대한 압축한 후 이를 풀어서 출력하는 해제 프로그램(decompressor)을 뒤에 붙인 뒤 그 길이를 재면 되므로, |s|에 해제 프로그램의 길이를 붙인 것보다 커지지는 않는다.
여기서 s가 'c만큼 압축가능(compressible)하다' 함은 서술이 |s| − c 비트보다 커질 수 없다는 것, 즉 K(s) ≤ |s| − c임으로 정의할 수 있다. 단순히 '압축가능하다'는 것을 1만큼 압축가능한 것으로 정의할 수 있다.
그런데 압축된 문자열은 오직 하나의 압축되지 않은 문자열에 대응되어야 하는데, 임의의 n에 대해 n 길이의 문자열이 2n개 존재하는 한편 그것보다 짧은 문자열은 2n - 1개만 존재하므로, 비둘기집 원리에 의해 압축불가능한 문자열이 반드시 존재할 수 밖에 없다는 결론이 나온다. 또한 같은 이유에서 더 짧은 문자열의 개수는 더 긴 문자열의 개수보다 훨씬 작으므로 확률적으로 대다수의 문자열은 유의미하게 압축할 수 없다는 것 또한 간단히 증명된다.
차이틴의 불완전성 정리[편집]
차이틴의 불완전성 원리(Chaitin's incompleteness theorem)에 의하면, 문자열이 압축가능한지의 여부는 문자열의 복잡도가 일정치를 넘으면 형식적으로 증명불가능하다.
우선 자연수에 대한 공리계 S를 고정한다. 이 공리계는 다음 성질을 만족한다 하자: "문자열의 복잡도에 관한 주장 A가 있을 때, S의 언어에 논리식 FA가 있어서 공리계 S에서 FA가 증명가능하다면 A도 참이다." 이는 괴델 수매김(Gödel numbering)을 통해 형식화가능하다. 그렇다면 다음이 성립한다.
정리: 공리계 S와 서술 언어에 따라서만 결정되는 상수 L이 있어서, 이에 대해 S에서 다음의 주장이 증명가능한 문자열 s는 존재하지 않는다:
- K(s) ≥ L
이는 베리의 역설과 비슷한 자기언급을 구성하여 증명할 수 있다.
각주[편집]
- ↑ Kolmogorov, Andrey (1963). “On Tables of Random Numbers”. 《Sankhyā Ser. A.》 25: 369–375. MR 178484.
- ↑ Kolmogorov, Andrey (1998). “On Tables of Random Numbers”. 《Theoretical Computer Science》 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.