설명 언어와 알고리즘 정보

분포의 엔트로피에서 개별 대상의 설명으로

Shannon 엔트로피는 확률분포에 대한 평균 불확실성입니다. 반면 알고리즘 정보는 주어진 문자열 하나를 출력할 가장 짧은 프로그램을 묻습니다. 동전으로 생성했는지 모르더라도 01010101에는 “01을 네 번 반복”이라는 설명이 있습니다. 생성 이력과 설명 가능성은 다르며, 짧은 한 문자열만 보고 강한 무작위성 결론을 내리지 않습니다.

보편 prefix 기계 U를 고정하면 Kolmogorov 복잡도는 다음과 같습니다. 프로그램은 출력 후 종료해야 합니다.

직접 계산 가능한 작은 설명 언어

실습은 보편 기계 대신 고정한 유한 복호기 D를 사용합니다. 모든 출력은 정확히 8비트이고 모든 명령은 즉시 종료합니다. 헤더를 포함한 길이를 비교합니다.

명령 집합은 prefix-free입니다. 헤더로 어느 명령인지 알면 남은 payload 길이가 정해집니다. 전체 Kraft 합은 256×2⁻⁹ + 2×2⁻³ + 4×2⁻⁵ + 16×2⁻⁸ = 15/16입니다.

예제: 같은 출력의 여러 프로그램

85는 이진수 01010101입니다. literal 설명 001010101은 9비트, period2 설명 11001은 5비트, period4 설명 11100101은 8비트입니다. 최솟값은 5입니다. 0의 상수 설명 100은 3비트입니다. 언어 수준 0에서는 literal만 허용하므로 두 대상 모두 9비트가 됩니다.

파란 막대는 같은 대상의 가능한 설명 길이입니다. 실습이 계산하는 것은 이 유한 K_D이며 보편 K_U가 아닙니다. 긴 설명을 발견하는 것은 상한을 주고, 여기서 최적임을 아는 것은 고정한 모든 후보를 전수 조사했기 때문입니다.

언어 선택과 해석기 비용

보편 기계 U가 D를 해석하는 고정 프로그램을 포함할 수 있으므로 K_U(x)≤K_D(x)+c_D입니다. c_D에는 복호기를 지정하는 비용이 들어갑니다. 서로 다른 보편 기계의 복잡도는 대상과 무관한 가산 상수 범위에서 비교할 수 있지만, 아주 짧은 문자열에서는 그 상수가 중요합니다.

AI 모형이 데이터를 압축한다고 말할 때도 디코더·사전·아키텍처가 무료인지 점검해야 합니다. 학습 후 특정 데이터만 짧게 출력하는 새 언어를 만들고 그 언어의 비용을 빼면 공정한 비교가 아닙니다.

확인 문제와 해설

1. 11111111은 몇 비트인가요? 현재 언어에서 101의 3비트입니다. 원본 8비트와 명령 길이를 구분합니다.
2. 이 최솟값을 모든 알고리즘 중 최적이라고 부를 수 있나요? 아니요. 허용한 278개 명령에 대해서만 최적입니다.
3. “별도 명령 하나로 대상 출력”을 추가하면 항상 유리한가요? 공유 복호기 비용을 숨기면 그렇게 보일 수 있습니다. 비교의 조건이 달라집니다.

추가 읽기: Grünwald and Vitányi, Algorithmic Information Theory.