콜모고로프 복잡도

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 직관적인 예
- 2.2. 형식적인 정의
3. 불변성 정리
- 3.1. 증명
4. 주요 성질
5. 정보 엔트로피와의 관계
6. 무작위성과의 관계
7. 정지 문제와의 관계
8. 한국에서의 연구 및 활용
- 8.1. 데이터 압축
참조

1. 개요

콜모고로프 복잡도는 주어진 문자열을 생성하는 가장 짧은 프로그램의 길이로 정의되는 정보 이론의 개념이다. 튜링 완전한 서술 언어에서 문자열을 서술하는 가장 짧은 프로그램의 길이를 의미하며, 문자열의 '복잡도'를 측정하는 데 사용된다. 불변성 정리에 따라 서술 언어의 선택은 콜모고로프 복잡도에 큰 영향을 미치지 않는다. 이 복잡도는 계산 불가능하며, 문자열의 압축 가능성과 무작위성을 정의하는 데 사용된다. 또한 차이틴의 불완전성 정리에 따르면, 일정 수준 이상의 복잡도를 갖는 문자열의 복잡도는 형식적으로 증명할 수 없다. 시간 제한 콜모고로프 복잡도는 이 개념의 변형으로, 일방향 함수의 존재와 관련이 있을 수 있다는 가설이 있다. 콜모고로프 복잡도는 정보 엔트로피, 무작위성, 정지 문제 등과 밀접한 관련이 있으며, 데이터 압축, 정보 보안, 인공지능, 생물 정보학 등 다양한 분야에서 연구 및 활용된다.

더 읽어볼만한 페이지

알고리즘 정보 이론 - 베리의 역설
베리의 역설은 유한한 단어로 자연수를 정의하려는 시도에서 발생하는 자기모순적인 역설로, '정의할 수 있다'라는 개념의 모호성에서 비롯되며, 의미 계층화 도입으로 해결을 시도하지만, 불완전성 정리, 콜모고로프 복잡도 등과 연관되어 논의된다.
계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.
계산 가능성 이론 - 처치-튜링 논제
처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
계산 가능성 이론 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.

콜모고로프 복잡도
개요
분야	정보 이론, 계산 이론
다른 이름	알고리즘 복잡도, 설명 길이, Kolmogorov-Chaitin complexity
정의	주어진 대상을 설명하는 가장 짧은 프로그램의 길이
창시자	안드레이 콜모고로프
상세 내용
정의	어떤 객체 (문자열, 파일 등) x의 콜모고로프 복잡도는 그 객체를 출력하는 가장 짧은 프로그램 p의 길이 \|p\|로 정의됨. 여기서 프로그램은 특정한 프로그래밍 언어 또는 튜링 기계로 작성됨.
특징	계산 불가능 (uncomputable) 객체의 무작위성을 측정하는 데 사용될 수 있음 정보 이론, 철학, 통계학 등 다양한 분야에 응용됨
역사
개발자	안드레이 콜모고로프 레이 솔로모노프 그레고리 차이틴
개발 년도	1960년대
개발 배경	무작위성의 개념을 수학적으로 정의하고, 정보의 양을 측정하기 위한 시도에서 비롯됨
활용
응용 분야	최소 메시지 길이 (Minimum Message Length, MML) 최소 기술 길이 (Minimum Description Length, MDL) 귀납 추론 데이터 압축 무작위성 측정
관련 정리	차이틴의 불완전성 정리 (Chaitin's incompleteness theorem)
참고 자료
관련 논문	On Tables of Random Numbers - Andrey Kolmogorov A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions - Hector Zenil

2. 정의

어떤 문자열의 콜모고로프 복잡도는 튜링 완전한 서술 언어에서 해당 문자열을 출력하는 가장 짧은 프로그램의 길이다. 여기서 서술 언어가 무엇인지는 불변성 정리에 의해 크게 중요하지 않다.

문자열의 '서술'(description)은 프로그래밍 언어에서 그 문자열을 출력(output)하는 프로그램을 예로 들 수 있으며, 이 정의는 더 일반화될 수 있다. 문자열 s의 콜모고로프 복잡도 K(s)는 어떤 언어에서 s를 서술하는 가장 짧은 프로그램(글)의 길이, 즉 최단 서술 d(s)의 길이로 정의된다.

엄밀하게, 유한 길이 문자열 ''x''에 대한 만능 계산기 ''u''에서의 콜모고로프 복잡성은 다음 식으로 정의된다.

: $K_u (x) = \min_{ p : u(p)=x }\, l(p)$

여기서 ''p''는 계산기 ''u''를 위한 프로그램이고, ''u''(''p'')는 ''p''를 실행했을 때 출력되는 문자열이다. ''l''(''p'')는 프로그램의 길이를 나타낸다. 프로그램은 입력을 받지 않고 항상 정해진 출력을 반환한다. 만능 계산기는 만능 튜링 머신과 동등한 능력을 가진 계산기로, C 언어 등 일반적인 프로그래밍 언어를 해석하고 실행하는 처리계라고 생각할 수 있다.

2. 1. 직관적인 예

예를 들어 32개의 문자로 이루어진 다음 두 문자열을 생각해 보자.

:abababababababababababababababab

:4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

첫 번째 문자열은 "ab를 16번 쓰기"라는 짧은 영어 표현(17자)으로 나타낼 수 있지만, 두 번째 문자열은 문자열 자체를 쓰는 것보다 더 간단한 표현을 찾기 힘들다(38자). 따라서 첫 번째 문자열이 두 번째 문자열보다 '복잡도가 낮다'고 생각할 수 있다.

이와 비슷하게, 0과 1로 이루어진 60글자 길이의 다음 두 문자열을 비교해 보자.

:010101010101010101010101010101010101010101010101010101010101

:110010000110000111011110111011001111101001000010010101111001

전자는 "01의 30회 반복"으로 11글자로 설명할 수 있지만, 후자는 그러한 간단한 설명이 어려워 보인다. 따라서 전자가 더 간단하고, 후자가 더 복잡하다고 느낄 수 있다.^[2]

이처럼 문자열을 언어로 설명했을 때, 짧게 표현 가능한 문자열이 있는 반면 압축하기 어려운 문자열도 존재한다. 이러한 직관을 바탕으로, 문자열의 설명 길이를 통해 복잡성을 정의할 수 있다.^[2]

2. 2. 형식적인 정의

만능 튜링 머신을 이용하여 문자열을 출력하는 가장 짧은 프로그램의 길이를 콜모고로프 복잡도로 정의한다. 최소 설명의 길이는 설명 언어의 선택에 따라 달라지지만, 불변성 정리에 의해 그 차이는 상수에 불과하다.

예를 들어 다음과 같은 두 개의 32자 문자열을 생각해보자.

:abababababababababababababababab

:4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

첫 번째 문자열은 "write ab 16 times"라는 짧은 영어 표현(17자)으로 나타낼 수 있지만, 두 번째 문자열은 문자열 자체를 쓰는 것 외에 더 간단한 표현을 찾기 힘들다(38자). 따라서 첫 번째 문자열이 두 번째 문자열보다 '복잡도가 낮다'고 할 수 있다.

형식적으로, 어떤 튜링 완전한 서술 언어가 있을 때 문자열의 콜모고로프 복잡도는 그 언어에서 해당 문자열을 출력하는 가장 짧은 프로그램의 길이이다. 문자열 ''s''에 대한 설명 ''d''(''s'')가 최소 길이(즉, 가장 적은 비트 사용)이면, ''s''의 '''최소 설명'''이라고 하며, ''d''(''s'')의 길이(즉, 최소 설명의 비트 수)는 ''s''의 '''콜모고로프 복잡도'''이며, ''K''(''s'')로 쓴다.

:''K''(''s'') = |''d''(''s'')|.

예를 들어, 위의 두 번째 문자열은 다음 의사 코드로 출력할 수 있다.

'''function''' GenerateString2()

'''return''' "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

반면 첫 번째 문자열은 더 짧은 의사 코드로 출력할 수 있다.

'''function''' GenerateString1()

'''return''' "ab" × 16

이처럼 기술 언어 ''L''에서의 문자열 ''x''의 모든 기술 중 최소 길이를 갖는 기술을 찾아낼 수 있다면, 그 길이가 ''L''에서의 ''x''의 콜모고로프 복잡성이 된다.

콜모고로프 복잡성에는 '일반' 복잡도와 '접두사 없는' 복잡도, 두 가지 정의가 있다. 일반 복잡도는 임의의 프로그램의 최소 설명 길이이며,

C(x)

로 표기되고, 접두사 없는 복잡도는 접두사 없는 코드로 인코딩된 임의의 프로그램의 최소 설명 길이이며,

K(x)

로 표기된다. 일반 복잡도가 더 직관적이지만, 접두사 없는 복잡도를 연구하기가 더 쉽다.^[4]

일반 복잡도의 한 가지 문제는

C(xy) \not < C(x) + C(y)

라는 것이다. 직관적으로 말하면, 연결된 문자열만 보고 출력 문자열을 어디에서 나눌지 일반적인 방법이 없기 때문이다.

x

또는

y

의 길이를 지정하여 나눌 수 있지만, 그렇게 하려면

O(\min(\ln x, \ln y))

개의 추가 기호가 필요하다. 실제로, 임의의

c > 0

에 대해

C(xy) \geq C(x) + C(y) + c

를 만족하는

x, y

가 존재한다.^[4]

일반적으로, 일반 복잡도를 사용한 부등식은 한쪽에

O(\min(\ln x, \ln y))

와 같은 항을 갖는 반면, 접두사 없는 복잡도를 사용한 동일한 부등식은

O(1)

만 갖는다.

일반 복잡도의 주요 문제는 프로그램에 추가적인 무언가가 몰래 들어가 있다는 것이다. 프로그램은 코드뿐만 아니라 자체 길이도 나타낸다. 특히, 프로그램

x

는 자체 길이에 의해 최대

\log_2 |x|

까지의 이진 숫자를 나타낼 수 있다. 다른 말로 하면, 단어가 끝나는 위치를 나타내기 위해 종료 기호를 사용하는 것과 같아서, 2개의 기호가 아닌 3개의 기호를 사용하는 셈이다. 이 결함을 해결하기 위해 접두사 없는 콜모고로프 복잡도를 도입한다.^[5]

'''접두사 없는 튜링 기계'''는 접두사 없는 코드가 있는 튜링 기계로 정의하며, 튜링 기계는 코드에서 어떤 문자열도 한 방향으로 읽을 수 있고 마지막 기호를 읽는 즉시 읽기를 멈출 수 있다. 그 후 작업 테이프에서 계산을 하고 쓰기 테이프에 쓸 수 있지만, 더 이상 읽기 헤드를 움직일 수 없다.

이는 ''K''를 설명하는 다음과 같은 공식적인 방법을 제공한다.^[6]

읽기 테이프(한 방향으로 무한함), 작업 테이프(양방향으로 무한함), 쓰기 테이프(한 방향으로 무한함)의 세 개의 테이프가 있는 접두사 없는 보편 튜링 기계를 고정한다.
기계는 읽기 테이프에서 한 방향으로만 읽을 수 있으며(뒤로 돌아갈 수 없음), 쓰기 테이프에 한 방향으로만 쓸 수 있다. 작업 테이프는 양방향으로 읽고 쓸 수 있다.
작업 테이프와 쓰기 테이프는 모두 0으로 시작한다. 읽기 테이프는 입력 접두사 코드와 그 뒤에 0으로 시작한다.
$S$ 를 보편 튜링 기계에서 사용하는 $2^*$ 의 접두사 없는 코드라고 하자.

문자열

x

의 접두사 없는 복잡도는 기계가

x

를 출력하게 하는 가장 짧은 접두사 코드이다.

:

K(x) := \min\

3. 불변성 정리

서로 다른 서술 언어 L1, L2를 생각할 때, L1과 L2 각각에 대한 문자열 x의 콜모고로프 복잡도의 차이는 문자열 x와 무관하게 서술 언어의 종류에 의해서만 결정되는 특정한 상수보다 항상 작다.^[1] 비형식적으로 말해, 문자열 x를 출력하는 서로 다른 언어로 쓰여진 프로그램의 길이 차에는 x의 길이와 무관하게 상한이 존재한다는 것이다. 이를 '''불변성 정리'''(invariance theorem)라고 한다.^[1] 따라서 콜모고로프 복잡도를 다룰 때 일반적으로 서술 언어를 따로 고려하지 않아도 된다.콜모고로프 복잡성은 기술 언어 또는 만능 튜링 기계에 의존한다. 그러나 어떤 만능 튜링 기계 ''u''₁에서 다른 만능 튜링 기계 ''u''₂로 프로그램을 이식해도, 콜모고로프 복잡성은 기껏해야 (''u''₁와 ''u''₂에 의해 결정되는) 상수만큼만 증가한다. 왜냐하면 두 개의 만능 튜링 기계는 반드시 상대방의 기계를 에뮬레이션할 수 있기 때문이다.^[1] ''u''₂ 상에서 ''u''₁를 모방하는 에뮬레이션 프로그램 ε_1,2를 만들고, 그 위에서 ''u''₁의 프로그램 ''p''를 실행하면, 결과적으로 ''u''₂ 상에서 프로그램 ''p''를 실행한 것이 된다. 이 에뮬레이션 프로그램은 에뮬레이션하는 프로그램의 크기에 관계없이 항상 일정하다. 따라서 ''u''₂ 상에서의 콜모고로프 복잡성은 기껏해야 ''l''(''p'') + ''l''(ε_1,2)이다. 역의 경우도 마찬가지로 에뮬레이션이 가능하며, 이로부터 다음 정리가 성립한다.'''정리:''' 임의의 만능 튜링 기계 ''u''₁, ''u''₂에 대해, 어떤 상수 ''c''_1,2가 존재하여, 임의의 ''x''에 대해,:

|K_1(x) - K_2(x)| \leq c_{1,2}.

가 성립한다.^[1]

콜모고로프 복잡성 논의에서는 기술 언어의 차이에 의해 어떤 상수만큼을 제외하고 성립한다는 관계가 빈번하게 나타난다.^[1]

3. 1. 증명

L2에서 최단 표현을 d₂라 할 때 d₁은 적어도 d₂에 L2에서 L1로의 번역을 제시하는 해석(인터프리터)을 더한 것의 길이보다 같거나 작으므로 그러한 해석의 길이를 c라 하면 K₁ ≤ K₂ + c 가 증명된다.^[1]

어떤 대상의 설명을 위한 언어는 다음과 같은 의미에서 최적이다. 어떤 대상에 대한 설명이 설명 언어로 주어지면, 해당 설명은 상수 오버헤드를 사용하여 최적의 설명 언어로 사용할 수 있다. 이 상수는 대상의 설명이나 설명 대상에 의존하지 않고 관련된 언어에만 의존한다.^[1]

다음은 최적 설명 언어의 예이다.^[1] 설명은 두 부분으로 구성된다.

첫 번째 부분은 다른 설명 언어를 설명한다.
두 번째 부분은 해당 언어로 된 대상에 대한 설명이다.

더 기술적인 용어로, 설명의 첫 번째 부분은 컴퓨터 프로그램(구체적으로는 대상 언어의 컴파일러이며, 설명 언어로 작성됨)이며, 두 번째 부분은 해당 컴퓨터 프로그램의 입력으로, 출력을 통해 대상을 생성한다.^[1]

'''불변성 정리가 따릅니다:''' 어떤 설명 언어 ''L''이 주어지면, 최적의 설명 언어는 상수 오버헤드를 포함하여 ''L''보다 효율적이다.^[1]

'''증명:''' 언어 ''L''의 설명 ''D''는 먼저 ''L''을 컴퓨터 프로그램 ''P''로 설명한 다음(1부), 원래 설명 ''D''를 해당 프로그램의 입력으로 사용하여(2부) 최적 언어의 설명으로 변환할 수 있다. 이 새로운 설명 ''D′''의 총 길이는 (대략) 다음과 같다.^[1]

:|''D′'' | = |''P''| + |''D''|

''P''의 길이는 ''D''에 의존하지 않는 상수이다. 따라서 설명된 대상에 관계없이 최대 상수 오버헤드가 있다. 따라서 최적 언어는 이 가산 상수를 최대로 하여 보편적이다.^[1]

4. 주요 성질

콜모고로프 복잡도에는 크게 '일반' 복잡도와 '접두사 없는' 복잡도 두 가지 정의가 있다. 일반 복잡도는 임의의 프로그램의 최소 설명 길이를 의미하며, $C(x)$ 로 표기한다. 접두사 없는 복잡도는 접두사 없는 코드로 인코딩된 프로그램의 최소 설명 길이를 나타내며, $K(x)$ 로 표기한다.^[4] 접두사 없는 복잡도는 일반 복잡도보다 연구하기 더 쉽다.

여기서 사용되는 방정식은 기본적으로 상수 추가까지 유효하다. 예를 들어 $f(x) = g(x)$ 는 실제로는 $f(x) = g(x) + O(1)$ 을 의미하며, 이는 어떤 상수 $c$ 가 존재하여 모든 $x$ 에 대해 $|f(x) - g(x)| \leq c$ 가 성립함을 의미한다.

$U: 2^* \to 2^*$ 를 유한 이진 문자열을 이진 문자열로 매핑하는 계산 가능한 함수라고 할 때, 이 함수가 보편적이라는 것은 모든 계산 가능한 $f: 2^* \to 2^*$ 에 대해, $s_f$ 라는 "프로그램"으로 $f$ 를 인코딩하여 $\forall x \in 2^*, U(s_fx) = f(x)$ 가 성립하는 것을 의미한다. $U$ 는 프로그램 인터프리터로 생각할 수 있으며, 프로그램 설명과 처리할 데이터를 입력으로 받는다.

일반 복잡도에서는 $C(xy) \not < C(x) + C(y)$ 라는 문제가 있다. 연결된 문자열만 보고는 출력 문자열을 어디에서 나누어야 할지 알 수 없기 때문이다. $x$ 나 $y$ 의 길이를 지정하여 나눌 수는 있지만, 이를 위해서는 $O(\min(\ln x, \ln y))$ 개의 추가 기호가 필요하다. 실제로, 임의의 $c > 0$ 에 대해 $C(xy) \geq C(x) + C(y) + c$ 를 만족하는 $x, y$ 가 존재한다.^[4]

일반적으로 일반 복잡도를 사용한 부등식은 한쪽에 $O(\min(\ln x, \ln y))$ 와 같은 항을 갖는 반면, 접두사 없는 복잡도를 사용한 동일한 부등식은 $O(1)$ 만 갖는다.

일반 복잡도의 주요 문제는 프로그램에 코드뿐만 아니라 자체 길이도 나타내는 추가적인 정보가 숨겨져 있다는 것이다. 프로그램 $x$ 는 자체 길이에 의해 최대 $\log_2 |x|$ 까지의 이진 숫자를 나타낼 수 있다. 이는 단어가 끝나는 위치를 나타내기 위해 종료 기호를 사용하는 것과 같아서, 2개가 아닌 3개의 기호를 사용하는 것과 같다. 이러한 문제를 해결하기 위해 접두사 없는 콜모고로프 복잡도가 도입되었다.^[5]

접두사 없는 코드는 집합 $2^*$ 의 부분 집합으로, 집합 내의 서로 다른 두 단어 $x, y$ 에 대해 어느 것도 다른 하나의 접두사가 되지 않는 것을 말한다. 이러한 코드의 장점은 코드로 단어를 한 방향으로 읽는 기계를 만들 수 있으며, 단어의 마지막 기호를 읽는 즉시 단어가 완료되었음을 "알고" 뒤로 돌아가거나 종료 기호가 필요하지 않다는 것이다.

'''접두사 없는 튜링 기계'''는 접두사 없는 코드가 있는 튜링 기계로 정의하며, 튜링 기계는 코드에서 어떤 문자열도 한 방향으로 읽을 수 있고 마지막 기호를 읽는 즉시 읽기를 멈출 수 있다. 그 후 작업 테이프에서 계산을 하고 쓰기 테이프에 쓸 수 있지만, 더 이상 읽기 헤드를 움직일 수 없다.

''K''를 설명하는 공식적인 방법은 다음과 같다.^[6]

읽기 테이프(한 방향), 작업 테이프(양방향), 쓰기 테이프(한 방향)의 세 개의 테이프가 있는 접두사 없는 보편 튜링 기계를 고정한다.
기계는 읽기 테이프에서 한 방향으로만 읽을 수 있으며(뒤로 돌아갈 수 없음), 쓰기 테이프에 한 방향으로만 쓸 수 있다. 작업 테이프는 양방향으로 읽고 쓸 수 있다.
작업 테이프와 쓰기 테이프는 모두 0으로 시작한다. 읽기 테이프는 입력 접두사 코드와 그 뒤에 0으로 시작한다.
$S$ 를 보편 튜링 기계에서 사용하는 $2^*$ 의 접두사 없는 코드라고 한다.

일부 보편 튜링 기계는 접두사 코드로 프로그래밍할 수 없을 수 있으므로, 접두사 없는 보편 튜링 기계만 선택해야 한다.

문자열

x

의 접두사 없는 복잡도는 기계가

x

를 출력하게 하는 가장 짧은 접두사 코드이다.

:

K(x) := \min\

4. 1. 계산 불가능성

계산 불가능한 함수인 콜모고로프 복잡도는 문자열 s에 대한 콜모고로프 복잡도 K(s)를 구하기 위해 다음과 같은 함수를 시도해 볼 수 있지만, 이는 불가능하다.```function KolmogorovComplexity(string s)for i = 1 to infinity:for each string p of length exactly iif isValidProgram(p) and evaluate(p) == sreturn i```위 함수는 각 유한한 길이에 대해 무작위로 프로그램을 생성하여 그 프로그램이 s를 출력하면 정지하여 그 길이를 반환하는 함수이다. 그러나 이 함수는 무작위로 프로그램을 구성하는 도중 영원히 정지하지 않는 프로그램을 구성하여 무한히 머무르게 될 수 있다. 또한 정지 문제에 관해 알려진 바와 같이, 프로그램을 실행하기 전에 그 프로그램의 정지 여부를 판정하는 일률적인 방법은 없다.따라서, 콜모고로프 복잡도는 계산 가능한 함수가 아니다. 즉, 어떤 문자열의 콜모고로프 복잡도를 정확하게 계산하는 알고리즘은 존재하지 않는다. 이는 정지 문제와 베리의 역설을 이용하여 증명할 수 있다.

4. 1. 1. 증명

계산 불가능한 함수인 콜모고로프 복잡도를 계산하는 함수가 존재한다고 가정하고, 이를 이용하여 모순을 유도한다.어떤 문자열 ''s''를 입력받아 그 문자열의 콜모고로프 복잡도 ''K''(''s'')를 반환하는 함수 `KolmogorovComplexity(string s)`가 존재한다고 가정한다. 이 함수를 이용하여, 다음과 같은 함수 `GenerateComplexString()`을 구성할 수 있다.```function GenerateComplexString()for i = 1 to infinity:for each string s of length exactly iif KolmogorovComplexity(s) ≥ 8000000000return s```이 함수는 길이가 1부터 무한대까지의 모든 문자열을 검사하여, 콜모고로프 복잡도가 8000000000 이상인 첫 번째 문자열 ''s''를 반환한다.여기서 `GenerateComplexString()` 함수의 길이는 `KolmogorovComplexity()` 함수의 길이와 `GenerateComplexString()` 함수 자체의 길이, 그리고 인터프리터의 길이를 합한 값이 된다. `KolmogorovComplexity()` 함수의 길이를 7,000,000,000 비트, 인터프리터의 길이를 1,400,000 비트, `GenerateComplexString()` 함수 자체의 길이를 1288 비트라고 가정하면, `GenerateComplexString()` 함수의 총 길이는 7,001,401,288 비트가 된다.이는 8,000,000,000보다 작은 길이의 프로그램으로는 만들 수 없는 문자열을 8,000,000,000 보다 작은 길이의 프로그램으로 만든 것이므로 모순이다. 이러한 증명 방식은 베리의 역설과 유사하다.^[18]^[19]^[20]

4. 2. 압축과의 관계

콜모고로프 복잡도는 데이터 압축의 이론적인 한계를 제시한다. 대부분의 문자열은 유의미하게 압축할 수 없는데, 이는 비둘기집 원리에 의해 증명된다.^[23]K(s)의 상한은 문자열 s를 최대한 압축한 후 이를 푸는 해제 프로그램(decompressor)을 뒤에 붙여서 계산할 수 있다. 따라서, |s|에 해제 프로그램의 길이를 더한 값보다 K(s)는 커질 수 없다.문자열 s가 'c만큼 압축가능(compressible)하다'는 것은 K(s) ≤ |s| − c임을 의미한다. 단순히 '압축가능하다'는 것은 1만큼 압축가능한 것으로 정의할 수 있다.그러나 압축된 문자열은 오직 하나의 압축되지 않은 문자열에 대응되어야 한다. 비둘기집 원리에 의해, 임의의 n에 대해 n 길이의 문자열은 2ⁿ개, 그것보다 짧은 문자열은 2ⁿ - 1개만 존재하므로, 압축 불가능한 문자열이 반드시 존재한다. 또한, 같은 이유로 더 짧은 문자열의 개수는 더 긴 문자열의 개수보다 훨씬 적으므로, 확률적으로 대다수의 문자열은 유의미하게 압축할 수 없음이 증명된다.(가역적인) 압축 프로그램은 주어진 문자열 ''x''에 대해, 문자열 ''y''를 반환하는 함수로 생각할 수 있다. ''y''는 대응하는 전개 프로그램으로 ''x''로 복원될 수 있어야 한다. 콜모고로프 복잡성의 정의에 의해, 전개 프로그램의 길이와 ''y''의 길이의 합은 ''x''의 콜모고로프 복잡성 이상이어야 한다. 따라서 콜모고로프 복잡성은 해당 문자열 데이터에 대한 궁극적인 압축의 한계를 나타낸다.압축 프로그램에서 ''y''의 길이가 ''x''보다 작아지는 것이 일반적이지만, 압축 불가능한 문자열에 대한 논의는 압축 프로그램에도 적용된다. 따라서 실제로는 압축할 수 없는 ''x''가 적어도 절반 존재하며, 대부분은 큰 압축을 할 수 없다. 압축 프로그램이 많은 문자열을 압축할 수 있는 것처럼 보이는 이유는, 실제로 다루는 문자열이 가능한 모든 문자열에 비해 극히 편향되어 있기 때문이다.콜모고로프 복잡성이 계산 불가능하다는 사실은, 모든 문자열 ''x''에 대해 콜모고로프 복잡성이 나타내는 궁극의 압축을 실현하는 프로그램을 만드는 것이 원리적으로 불가능함을 의미한다.

4. 3. 차이틴의 불완전성 정리

차이틴의 불완전성 정리에 따르면, 문자열의 복잡도가 특정 값을 넘어서면, 그 문자열이 압축 가능한지 여부를 형식적으로 증명하는 것이 불가능하다.^[24]^[25]이는 베리의 역설과 비슷한 자기언급을 구성하여 증명할 수 있다. 우선 자연수에 대한 공리적 체계 '''S'''를 고정한다. 이 공리계는 "문자열의 복잡도에 관한 주장 A가 있을 때, S의 언어에 논리식 F_A가 있어서 공리계 S에서 F_A가 증명가능하다면 A도 참이다."라는 성질을 만족해야 한다. 이는 괴델 수매김을 통해 형식화할 수 있다.'''정리''': 공리계 S와 서술 언어에 따라서만 결정되는 상수 L이 있어서, S에서 다음의 주장이 증명가능한 문자열 s는 존재하지 않는다.^[16]:K(s) ≥ L'''증명 아이디어''': 이 결과는 베리의 역설에서 사용된 자기 참조 구성을 이용한다. 먼저 '''S''' 내의 증명을 열거하는 프로그램을 얻고, 정수 ''L''을 입력으로 받아 ''K''(''x'') ≥ ''L'' 명제의 '''S''' 내 증명 내에 있는 문자열 ''x''를 출력하는 절차 ''P''를 지정한다. 그런 다음 ''L''을 이 절차 ''P''의 길이보다 크게 설정하면, ''K''(''x'') ≥ ''L''로 진술된 대로 ''x''를 출력하는 프로그램의 필요한 길이는 문자열 ''x''가 절차 ''P''에 의해 인쇄되었으므로 ''L''의 양보다 적다. 이것은 모순이다. 따라서 증명 시스템 '''S'''가 ''L''이 임의로 클 때, 특히 절차 ''P''의 길이(유한함)보다 큰 ''L''에 대해 ''K''(''x'') ≥ ''L''을 증명하는 것은 불가능하다.'''증명''':어떤 절차에 의해 '''S'''의 모든 공식 증명의 유효한 열거를 찾을 수 있다.'''function''' NthProof('''int''' ''n'')이것은 입력으로 ''n''을 받고 어떤 증명을 출력하는 함수이다. 이 함수는 모든 증명을 열거한다. 이들 중 일부는 ''K''(''s'') ≥ ''n'' 형태의 복잡도 수식이며, 여기서 ''s''와 ''n''은 '''S'''의 언어에서 상수이다. 다음 절차가 있다.'''function''' NthProofProvesComplexityFormula('''int''' ''n'')이것은 ''n''번째 증명이 실제로 복잡도 수식 ''K''(''s'') ≥ ''L''을 증명하는지 여부를 결정한다. 문자열 ''s''와 정수 ''L''은 다음 절차에 의해 계산 가능하다.'''function''' StringNthProof('''int''' ''n'')'''function''' ComplexityLowerBoundNthProof('''int''' ''n'')다음 절차를 고려한다.'''function''' GenerateProvablyComplexString('''int''' ''n'')'''for''' i = 1 '''to''' 무한대:'''if''' NthProofProvesComplexityFormula(i) '''and''' ComplexityLowerBoundNthProof(i) ≥ ''n'''''return''' StringNthProof(''i'')''n''이 주어지면 이 절차는 공식 시스템 '''S'''에서 수식 ''K''(''s'') ≥ ''L''에 대한 문자열과 증명을 찾을 때까지 모든 증명을 시도한다(어떤 ''L'' ≥ ''n''); 그러한 증명이 없으면 영원히 루프한다.마지막으로, 이러한 모든 절차 정의와 주 호출로 구성된 프로그램을 고려한다.GenerateProvablyComplexString(''n''₀)여기서 상수 ''n''₀는 나중에 결정된다. 전체 프로그램 길이는 ''U''+log₂(''n''₀)로 표현할 수 있으며, 여기서 ''U''는 어떤 상수이고 log₂(''n''₀)는 이진 숫자로 인코딩된 정수 값 ''n''₀의 길이를 나타낸다. 우리는 ''n''₀를 프로그램 길이보다 크게, 즉 ''n''₀ > ''U''+log₂(''n''₀)가 되도록 선택할 것이다. 이것은 좌변이 ''n''₀에서 선형적으로 증가하는 반면 우변은 고정 상수 ''U''까지 ''n''₀에서 로그적으로 증가하므로, ''n''₀가 충분히 클 때 명백히 참이다.그런 다음, ''L''≥''n''₀인 형태의 "''K''(''s'')≥''L''" 증명은 '''S'''에서 얻을 수 없다. 이것은 귀류법에 의해 알 수 있다.만약 ComplexityLowerBoundNthProof(i)가 ≥''n''₀ 값을 반환할 수 있다면, GenerateProvablyComplexString 내부의 루프는 결국 종료되고, 해당 절차는 다음과 같은 문자열 ''s''를 반환한다.

K(s)

≥ n₀

> U+log₂(n₀)

≥ K(s)

이는 모순이다.결과적으로, 선택된 값 ''n''₀를 갖는 위 프로그램은 영원히 루프해야 한다.유사한 아이디어가 차이틴의 상수의 성질을 증명하는 데 사용된다.^[21]

콜모고로프 복잡도와 두 개의 계산 가능한 하한 함수. 가로축 (로그 척도)은 길이 순으로 정렬된 모든 문자열 ''s''를 열거하고, 세로축 (선형 척도)은 비트 단위로 콜모고로프 복잡도를 측정합니다. 대부분의 문자열은 압축할 수 없으며, 즉, 콜모고로프 복잡도가 상수만큼 길이를 초과합니다. 9개의 압축 가능한 문자열이 그림에 표시되어 있으며, 거의 수직에 가까운 기울기로 나타납니다. Chaitin의 불완전성 정리(1974)에 따르면, 콜모고로프 복잡도의 하한을 계산하는 프로그램의 출력은 입력 문자열 ''s''와 무관한 고정된 한계를 초과할 수 없습니다.

4. 4. 조건부 복잡도

두 문자열의 조건부 콜모고로프 복잡도 K(x|y)^영어는 대략적으로 절차에 대한 보조 입력으로 주어진 ''y''를 기준으로 ''x''의 콜모고로프 복잡도로 정의된다.^[34]^[35]또한 길이 조건부 복잡도 K(x|L(x))^영어도 있는데, 이는 알려지거나 입력된 ''x''의 길이를 기준으로 ''x''의 복잡도이다.^[36]^[37]

4. 5. 시간 제한 복잡도

시간 제한 콜모고로프 복잡도는 해답을 찾기 위해 검색할 프로그램의 공간을 미리 정의된 단계 수 내에서 실행할 수 있는 프로그램으로만 제한하는 콜모고로프 복잡도의 수정된 버전이다.^[38] 시간 제한 콜모고로프 복잡도를 근사적으로 결정하는 효율적인 알고리즘의 존재 가능성은 진정한 일방향 함수의 존재 여부와 관련이 있다는 가설이 있다.^[39]^[40]

5. 정보 엔트로피와의 관계

동역학적 시스템에서 궤적의 엔트로피율과 알고리즘 복잡도는 브루드노의 정리에 의해 연관되어 있으며, 거의 모든

x

에 대해

K(x;T) = h(T)

가 성립한다.^[29]

마르코프 정보원의 출력에 대해, 콜모고로프 복잡도는 정보원의 엔트로피와 관련이 있다는 것을 보일 수 있다.^[30] 보다 정확하게는, 마르코프 정보원의 출력의 콜모고로프 복잡도는 출력 길이로 정규화되었을 때, (출력 길이가 무한대로 갈수록) 거의 확실히 소스의 엔트로피로 수렴한다.

'''정리.''' (정리 14.2.5^[31]) 이진 문자열

x_{1:n}

의 조건부 콜모고로프 복잡도는 다음을 만족한다.

:

\frac 1n K(x_{1:n} | n ) \leq H_b\left(\frac 1n \sum_i x_i\right) + \frac{\log n}{2n} + O(1/n)

여기서

H_b

는 이진 엔트로피 함수이다 (엔트로피율과 혼동하지 않도록 주의).

6. 무작위성과의 관계

콜모고로프 복잡도는 문자열의 무작위성을 정의하는 데 사용될 수 있다. 어떤 문자열을 생성할 수 있는 모든 컴퓨터 프로그램이 그 문자열 자체보다 적어도 더 길 때, 그 문자열은 무작위성을 띤다고 정의된다. 이러한 의미에서 무작위 문자열은 "압축 불가능"하다고 간주되는데, 이는 문자열 자체보다 짧은 프로그램으로 해당 문자열을 "압축"하는 것이 불가능하기 때문이다.^[27]

문자열 ''s''가 길이 |''s''| − ''c'' 비트를 넘지 않는 설명을 가지면 숫자 ''c''로 압축 가능하다고 하며, 이는 ''K''(''s'') ≤ |''s''| − ''c''로 표현된다. 1로 압축할 수 없는 문자열은 단순히 ''압축 불가능''이라고 불린다. 비둘기집 원리에 따라, 압축 불가능한 문자열은 반드시 존재한다. 길이가 ''n''인 비트 문자열은 2^''n''개 존재하지만, 길이가 ''n''보다 짧은 문자열은 2^''n'' − 1개만 존재하기 때문이다.^[23]

대부분의 문자열은 상당히 압축할 수 없다는 점에서 복잡하다. 즉, 문자열의 ''K''(''s'')는 ''s''의 비트 길이인 |''s''|보다 훨씬 작지 않다. 길이 ''n''인 비트 문자열 공간에 대한 균등 확률 분포를 사용하면, 문자열이 ''c''로 압축 불가능할 확률은 최소 1 − 2^−''c''+1 + 2^−''n''이다.

알고리즘적 무작위 수열은 콜모고로프 무작위성에 기반하여 정의된다. 충분히 긴 문자열에서 "압축 불가능"한 문자열은 알고리즘화할 수 있는 어떤 규칙성도 가지지 않으므로 "랜덤"한 문자열로 간주될 수 있다. 콜모고로프 복잡성을 무한 길이 문자열로 확장했을 때, 압축할 수 없는 문자열은 "알고리즘적 무작위 수열"이라고 불린다. 주어진 무한 수열 ''x''의 모든 접두 부분 수열이 ''c'' 압축 불가능인 ''c''가 존재할 때, ''x''는 알고리즘적으로 무작위적이다.^[28]

그러나 특정 문자열이 무작위인지 여부는 선택된 특정 범용 컴퓨터에 따라 달라진다. 이는 범용 컴퓨터가 자체적으로 특정 문자열을 하드 코딩할 수 있기 때문이다.^[27]

7. 정지 문제와의 관계

콜모고로프 복잡도 함수는 정지 문제를 결정하는 것과 동등하다.^[32]^[33] 정지 오라클이 있다면, 문자열의 콜모고로프 복잡도는 렉시코그래피 순서로 모든 정지 프로그램을 시도하여 그중 하나가 문자열을 출력할 때까지 계산할 수 있다.

콜모고로프 복잡도 함수가 주어지면, 정지 문제를 해결하는 함수를 구성할 수 있다.

8. 한국에서의 연구 및 활용

한국에서는 정보통신 기술의 발전에 따라 콜모고로프 복잡도에 대한 연구가 활발하게 진행되고 있다. 특히, 데이터 압축, 정보 보안, 인공지능, 생물 정보학 등 다양한 분야에서 콜모고로프 복잡도의 개념이 활용되고 있다. 콜모고로프 복잡도는 데이터 압축의 이론적 한계를 제시한다.

8. 1. 데이터 압축

콜모고로프 복잡도는 데이터 압축의 이론적 한계를 제시한다. 어떤 문자열을 다른 문자열로 압축하는 프로그램에서, 전개 프로그램과 압축된 문자열의 길이 합은 원래 문자열의 콜모고로프 복잡성보다 작을 수 없다. 이는 데이터 압축의 근본적인 한계를 보여준다.

대부분의 문자열은 크게 압축하기 어렵지만, 우리가 실제로 다루는 문자열들은 특정한 패턴이나 구조를 가지는 경우가 많아 압축이 잘 되는 것처럼 보인다. 그러나 콜모고로프 복잡성은 계산 불가능하므로, 모든 문자열을 콜모고로프 복잡성까지 압축하는 프로그램을 만드는 것은 불가능하다.

이러한 콜모고로프 복잡도의 개념은 효율적인 압축 알고리즘 개발에 활용될 수 있다.

참조

_[1] 논문 On Tables of Random Numbers 1963-12
_[2] 논문 On Tables of Random Numbers
_[3] 논문 A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
_[4] 문서 (Downey and Hirschfeldt, 2010), Theorem 3.1.4
_[5] 문서 (Downey and Hirschfeldt, 2010), Section 3.5
_[6] 논문 Algorithmic information theory 2007-03-06
_[7] 간행물 A Preliminary Report on a General Theory of Inductive Inference http://world.std.com[...] 1960-02-04
_[8] 논문 A Formal Theory of Inductive Inference Part I http://world.std.com[...] 1964-03
_[9] 논문 A Formal Theory of Inductive Inference Part II http://world.std.com[...] 1964-06
_[10] 논문 Three Approaches to the Quantitative Definition of Information http://www.ece.umd.e[...]
_[11] 논문 On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
_[12] 논문 Logical basis for information theory and probability theory
_[13] 서적 An Introduction to Kolmogorov Complexity and its Applications https://archive.org/[...]
_[14] 논문 Generalized Kolmogorov complexity and duality in theory of computations https://www.mathnet.[...]
_[15] 서적 Universal artificial intelligence: sequential decisions based on algorithmic probability Springer 2005
_[16] 문서 'However, an ''s'' with ''K''(''s'') = ''n'' need not exist for every ''n''. For example, if ''n'' is not a multiple of 7, no [[ASCII]] program can have a length of exactly ''n'' bits.'
_[17] 문서 There are 1 + 2 + 2² + 2³ + ... + 2^''n'' = 2^''n''+1 − 1 different program texts of length up to ''n'' bits; cf. [[geometric series]]. If program lengths are to be multiples of 7 bits, even fewer program texts exist.
_[18] 문서 By the previous theorem, such a string exists, hence the for loop will eventually terminate.
_[19] 문서 including the language interpreter and the subroutine code for KolmogorovComplexity
_[20] 문서 'If KolmogorovComplexity has length ''n'' bits, the constant ''m'' used in GenerateComplexString needs to be adapted to satisfy {{nowrap|''n'' + {{val|1400000}} + {{val|1218}} + 7·log₁₀(''m'') < ''m''}}, which is always possible since ''m'' grows faster than log₁₀(''m'').'
_[21] 웹사이트 Course notes for Data Compression - Kolmogorov complexity http://www.daimi.au.[...]
_[22] 논문 The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. http://alexander.she[...]
_[23] 문서 'As there are {{nobr|1=''N''_''L'' = 2^''L''}} strings of length ''L'', the number of strings of lengths {{nowrap|1=''L'' = 0, 1, ..., ''n'' − 1}} is {{nobr|''N''₀ + ''N''₁ + ... + ''N''_''n''−1}} = {{nobr|2⁰ + 2¹ + ... + 2^''n''−1}}, which is a finite [[geometric series]] with sum {{nobr|2⁰ + 2¹ + ... + 2^''n''−1}} = {{nobr|1 = 2⁰ × (1 − 2^''n'') / (1 − 2) = 2^''n'' − 1}}'
_[24] 논문 Information-theoretic limitations of formal systems http://www.cas.mcmas[...] 1974-07
_[25] 서적 Information and Randomness: an algorithmic perspective https://www.springer[...] Springer 2002-09-12
_[26] 논문 Minimum Message Length and Kolmogorov Complexity
_[27] 문서 There are 2^''n'' bit strings of length ''n'' but only 2^''n''-1 shorter bit strings, hence at most that much compression results.
_[28] 논문 The definition of random sequences
_[29] 논문 Effective symbolic dynamics, random points, statistical behavior, complexity and entropy http://www.loria.fr/[...]
_[30] arXiv Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics
_[31] 서적 Elements of information theory Wiley-Interscience
_[32] 논문 Program-size Complexity Computes the Halting Problem 1995-09-01
_[33] 서적 An Introduction to Kolmogorov Complexity and Its Applications https://link.springe[...] 2008
_[34] 서적 Information and Complexity in Statistical Modeling https://archive.org/[...] Springer S
_[35] 서적 An Introduction to Kolmogorov Complexity and Its Applications https://archive.org/[...] Springer
_[36] 서적 An Introduction to Kolmogorov Complexity and Its Applications https://archive.org/[...] Springer
_[37] 논문 Conditional Kolmogorov complexity and universal probability https://ir.cwi.nl/pu[...]
_[38] 논문 Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity Schloss Dagstuhl – Leibniz-Zentrum für Informatik 2024
_[39] 웹사이트 Researchers Identify 'Master Problem' Underlying All Cryptography https://www.quantama[...] 2022-04-06
_[40] 간행물 On One-way Functions and Kolmogorov Complexity 2020-09-24
_[41] 웹사이트 Course notes for Data Compression - 2 Kolmogorov complexity Fall 2005 http://www.daimi.au.[...] University of Aarhus 2009-07-19
_[42] 저널 On Tables of Random Numbers
_[43] 저널 On Tables of Random Numbers

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com