계산 예산과 설명 탐색

최적화 문제와 현재 발견한 답을 구분하기

짧은 프로그램을 찾는 데 계산 자원이 듭니다. 예산 안에서 얻은 결과는 대상의 본질뿐 아니라 후보 순서와 탐색 방식에도 좌우됩니다. 이 단원은 앞서 고정한 278개 유한 프로그램을 사용해 검사 개수를 직접 제한합니다. 각 프로그램은 즉시 종료하므로 보편 프로그램의 비종료 문제는 이 실험에 없습니다.

목표 byte와 정확히 같은 출력을 내는 후보만 정답으로 인정합니다. 대상을 근사하는 설명을 찾는 문제가 아니라 정확 복원을 유지하면서 최적 설명을 근사 탐색하는 문제입니다.

순서를 바꾸면 같은 예산도 다른 결과

“짧은 길이 먼저”는 프로그램 길이, 이어서 같은 길이의 사전순으로 검사합니다. 이 순서에서 대상을 처음 발견했다면 이 유한 집합에서는 최단입니다. “literal 먼저”는 256개 literal, 상수 2개, period2 4개, period4 16개 순서입니다. 후자는 먼저 긴 설명을 찾고 나중에 개선할 수 있습니다.

대상 0은 literal 먼저의 첫 후보에서 9비트 설명을 얻습니다. 257번째 후보가 상수 명령 100이므로 길이가 3으로 줄어듭니다. 같은 예산 1에서도 짧은 길이 먼저는 0의 상수 명령을 바로 찾습니다. 반대로 대상 173은 짧은 순서의 첫 후보로 찾을 수 없습니다.

그래프에서 상한과 미발견을 읽기

파란 곡선은 발견한 최선 설명 길이, 주황 점선은 유한 집합 전체를 별도로 조사한 최적값입니다. 미발견 구간에는 파란 점을 그리지 않고 수치에 —를 표시합니다. 미발견을 0비트나 무한 복잡도로 바꾸지 않습니다. 발견한 뒤에는 기존 최선을 보관하므로 상한은 증가하지 않습니다.

표는 첫 검사, 개선이 일어난 검사, 마지막 검사를 보여줍니다. 긴 동일 값 구간은 생략하되 검사 예산은 그대로 셉니다. 모든 278개를 검사하면 두 순서 모두 같은 유한 최적값에 도달합니다.

계산 제한과 연구 해석

여기서 예산은 프로그램 검사 수이며 실제 초 단위 시간과 같지 않습니다. 일반 탐색에서는 후보별 실행 비용도 다릅니다. 보편 시간 제한 복잡도 Kᵗ처럼 시간 제한을 명시하는 정의는 별도의 대상이며 이 유한 예산 실험이 그 값을 계산하지 않습니다.

AI가 찾은 압축 설명·프로그램·모형은 실행해 검증할 수 있지만, 탐색 예산이 작은 경우 성능 격차를 곧바로 표현력 한계로 해석하면 안 됩니다. 비교하는 탐색 순서·허용 언어·후보 평가 비용·복원 조건을 맞춰야 합니다.

확인 문제와 해설

1. 0의 9비트 설명을 찾으면 최단인가요? literal 먼저 예산 1에서는 아닙니다. 같은 유한 언어에 길이 3인 명령이 있습니다.
2. 미발견이면 하한이 커지나요? 일반적으로 아닙니다. 아무 순서로 일부 후보만 검사한 실패는 남은 짧은 후보를 배제하지 않습니다. 길이 순서 탐색처럼 별도 구조가 있으면 검사한 길이에 한정한 결론은 가능합니다.
3. 보편 프로그램 탐색도 모든 짧은 후보를 끝까지 기다리면 되나요? 일부는 종료하지 않습니다. 유한 실험의 종료 보장을 일반화할 수 없습니다.

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