Kolmogorov 복잡도의 계산 불가능성

유한 표는 계산할 수 있는데 무엇이 불가능한가

앞 단원의 278개 명령은 모두 종료합니다. 모든 후보를 실행해 출력별 최솟값을 구할 수 있습니다. 계산 불가능성은 이 유한 과제가 아니라, 고정한 보편 prefix 기계 U에서 모든 유한 문자열 x의 정확한 K_U(x)를 항상 종료하며 반환하는 알고리즘이 없다는 주장입니다.

특정 문자열의 짧은 설명을 아는 것과 모든 문자열의 정확한 최솟값을 계산하는 것은 다릅니다. 특정 x에 대한 값이나 상한을 증명할 수 없다는 주장도 아닙니다.

먼저 개수의 한계를 확인하기

Prefix-free 프로그램의 Kraft 부등식으로 길이 L 이하인 프로그램은 많아야 2ᴸ개입니다. 서로 다른 출력 수는 프로그램 수보다 클 수 없으므로 길이 L+1인 모든 문자열을 이 예산으로 설명할 수 없습니다.

실습에서는 유한 복호기 D의 길이 예산을 바꿉니다. L=3에서는 상수 출력 2개, L=5에서는 4개, L=8에서는 16개, L=9에서는 256개를 덮습니다. 여러 프로그램이 같은 출력을 내므로 “프로그램 수”와 “서로 다른 출력 수”가 다릅니다. L=8 이하 프로그램은 22개지만 출력은 16개입니다.

정확한 K 알고리즘을 가정한 대각 논증

모든 x의 K_U(x)를 계산하는 종료 알고리즘 A가 있다고 가정합시다. 주어진 n에 대해 길이 n+1의 문자열을 사전순으로 열거하고 A로 값을 구해 K_U(x)>n인 첫 xₙ을 출력하는 알고리즘을 만듭니다. 개수 논증 때문에 그런 문자열이 존재하므로 탐색은 종료합니다.

그러나 이 알고리즘 자체는 고정한 A와 탐색 규칙, 그리고 n만 부호화하면 됩니다. n의 자기 구분 부호는 길이 O(log n)으로 만들 수 있습니다. 따라서 충분히 큰 n에서 다음 모순이 생깁니다.

결론은 가정한 A가 없다는 것입니다. 브라우저의 유한 커버리지 그림이 이 일반 정리를 증명하는 것은 아닙니다. 그림은 짧은 설명의 부족과 중복 출력이라는 개수 직관을 돕습니다.

실행 시간을 늘리는 것으로 해결되지 않는 이유

보편 프로그램을 길이 순서로 실행하면 하나가 끝나지 않아 뒤를 막을 수 있습니다. 여러 후보에 실행 단계를 번갈아 주는 dovetailing으로 종료하는 프로그램은 결국 발견할 수 있습니다. 발견한 설명 길이를 줄이는 상한 근사는 가능하지만, 더 짧은 미종료 후보가 나중에 끝나지 않을 것이라고 일반적으로 인증할 수는 없습니다.

AI에서 압축기나 LLM이 짧은 설명을 제안하면 그것을 실제로 실행하고 복원 여부를 검증할 수 있습니다. 탐색 실패나 시간 초과로 대상이 본질적으로 무작위라거나 특정 설명이 보편 최적이라고 결론 내리지는 않습니다.

확인 문제와 해설

1. L=8에서 대상 173은 덮이나요? 아니요. 현재 유한 언어의 최솟값은 literal의 9비트입니다. 보편 K에 대한 하한은 아닙니다.
2. 정확한 K가 계산 불가능하면 유용한 압축기도 없나요? 아니요. 좋은 설명의 발견은 가능합니다. 모든 입력에 대한 정확한 최적성 보장이 불가능합니다.
3. 대각 논증에서 탐색 종료는 왜 필요한가요? xₙ을 출력하는 실제 프로그램을 구성해야 하기 때문입니다. 가정한 A의 총계산 가능성과 개수 논증이 이를 보장합니다.

추가 읽기: Vitányi, How Incomputable Is Kolmogorov Complexity?.