정의
알고리즘 정보 이론(Algorithmic Information Theory, AIT)은 수학적 객체(특히 문자열)의 복잡도를 측정하기 위해 알고리즘적 접근을 사용하는 정보 이론의 한 분야이다. 주된 목표는 어떤 대상의 정보를 그 대상을 생성할 수 있는 최소한의 프로그램(또는 알고리즘)의 길이로 정의하는 것이다. 이 최소 프로그램 길이는 Kolmogorov 복잡도(또는 알고리즘적 복잡도)라 불린다.
주요 역사·연구자
- Andrey Kolmogorov(1960년대): 문자열을 기술하는 가장 짧은 프로그램 길이를 정의하는 개념을 제안하였다.
- Ray Solomonoff(1960년대): 귀납적 추론과 관련된 알고리즘적 확률 모델을 제시하며 AIT의 초기 이론적 기반을 마련하였다.
- Gregory Chaitin(1970년대): Kolmogorov 복잡도의 수학적 성질을 체계화하고, 자체적인 Chaitin‑Ω 수(알고리즘적 무작위성의 대표적 예)를 정의하였다.
핵심 개념
| 개념 | 설명 |
|---|---|
| Kolmogorov 복잡도(K(x)) | 문자열 x를 생성하는 최단 프로그램(보통 범용 튜링 기계에 대한)이 차지하는 비트 수. |
| 무작위성 | 문자열 x의 Kolmogorov 복잡도가 x의 길이와 거의 동일할 때, x는 무작위적이라 한다. |
| 알고리즘적 확률(P(x)) | 무작위 프로그램이 x를 출력할 확률. 이는 $P(x) = \sum_{p:U(p)=x} 2^{- |
| Chaitin‑Ω | 모든 자가 중단하는 프로그램이 무한히 많지 않음에도 불구하고, 무작위 프로그램이 멈출 확률의 합을 나타내는 실수. 알려진 바에 따르면 Ω는 계산 불가능하고, 그 비트열 자체가 완전한 무작위성을 갖는다. |
응용 분야
- 데이터 압축: Kolmogorov 복잡도는 이론적 압축 한계와 직접 연결된다. 실제 압축 알고리즘은 이 한계에 근접하려는 시도로 해석된다.
- 무작위성 검증: 무작위 수열의 복잡도를 분석함으로써 난수 생성기의 품질을 평가한다.
- 복잡도 이론: 계산 복잡도와 정보 복잡도의 관계를 탐구하며, 예를 들어 P vs NP 문제와 연관된 논의에 활용된다.
- 생물정보학·통계학: 서열 데이터나 모델의 복잡성을 정량화하는 데 사용된다.
제한점 및 비판
- 비계산성: 일반적인 Kolmogorov 복잡도는 알고리즘적으로 계산할 수 없으며, 상한·하한만 추정 가능하다.
- 모델 의존성: 복잡도는 선택된 튜링 기계(또는 프로그래밍 언어)의 정의에 따라 상수 차이만 존재하지만, 실제 수치 비교 시 영향을 줄 수 있다.
관련 분야
- 정보 이론(Shannon entropy)과는 달리 확률 분포가 아닌 개별 객체의 구조적 복잡도에 초점을 맞춘다.
- 계산학(computability theory), 수리 논리학, 통계 물리학 등과 교차 연구가 활발하다.
참고 문헌
- Li, M., & Vitányi, P. (2008). An Introduction to Kolmogorov Complexity and Its Applications. Springer.
- Chaitin, G. J. (1975). “A Theory of Program Size Formally Identical to Information Theory”. Journal of the ACM.
- Cover, T. M., & Thomas, J. A. (2006). Elements of Information Theory. Wiley.
위 내용은 현재 학계에 널리 알려진 알고리즘 정보 이론에 대한 객관적인 요약이다.
