콜모고로프 복잡도

Kolmogorov complexity
이 이미지는 만델브로 집합 프랙탈의 일부를 보여줍니다.이 이미지에 각 픽셀의 24비트 색상을 저장하는 것만으로도 2,300만 바이트가 필요하지만, 작은 컴퓨터 프로그램은 만델브로 집합의 정의와 이미지의 모서리 좌표를 사용하여 이 23MB를 재생할 수 있습니다.따라서 이 이미지의 콜모고로프 복잡성은 어떤 실용적인 계산 모델에서도 23MB보다 훨씬 작습니다.PNG의 범용 이미지 압축은 원시 데이터보다 작지만 콜모고로프 복잡도보다 훨씬 큰 1.6MB로 감소시킬 뿐입니다.

콜모고로프 복잡도(Kolmogorov complexity)는 알고리즘 정보 이론(컴퓨터 과학 및 수학하위 분야)에서 텍스트 조각과 같은 객체의 복잡도를 출력으로 생성하는 가장 짧은 컴퓨터 프로그램의 길이입니다.이것은 대상을 특정하는 데 필요한 계산 자원의 척도이며, 알고리즘 복잡도, 솔로몬로프-콜모고로프-차이틴 복잡도, 프로그램 크기 복잡도, 기술 복잡도 또는 알고리즘 엔트로피라고도 합니다.1963년 이[1][2] 주제에 대해 처음 발표한 안드레이 콜모고로프의 이름을 따서 지어졌으며 고전 정보 이론을 일반화한 것입니다.

Kolmogorov complexity 개념은 칸토어의 대각선 논법, 괴델불완전성 정리, 튜링의 멈춤 문제와 같은 불가능한 결과를 기술하고 증명하는 데 사용될 수 있습니다.특히, 각 텍스트의 콜모고로프 복잡도에 대한 하한을 계산하는 어떤 프로그램 P도 P 자신의 길이보다 본질적으로 큰 값을 반환할 수 없습니다. 따라서 무한히 많은 텍스트에 대해 정확한 콜모고로프 복잡도를 계산할 수 있는 프로그램은 없습니다.

정의.

32개의 소문자와 숫자로 구성된 다음 두 문자열을 생각해 보십시오.

abababababababababababababababab,그리고.
4c1j5b2p0cv4w1x8rx2y39umgw5q85s7

첫 번째 문자열은 짧은 영어 설명, 즉 "ab 16번 쓰기"로 17자로 구성되어 있습니다.두 번째 것은 문자열 자체를 적는 것 외에 명백한 간단한 설명(동일한 문자 집합 사용)이 없습니다. 즉, "write 4c1j5b2p0cv4w1x8x2y39umgw5q85s7"은 38자입니다.따라서 첫 번째 문자열을 쓰는 동작은 두 번째 문자열을 쓰는 것보다 "복잡함이 덜하다"고 할 수 있습니다.

좀 더 형식적으로, 문자열의 복잡도고정된 범용 설명 언어에서 문자열의 가능한 가장 짧은 설명의 길이입니다(설명 언어의 선택과 관련된 복잡도의 민감도는 아래에서 논의됨).임의의 문자열의 콜모고로프 복잡도는 문자열 자체의 길이보다 몇 바이트 이상 클 수 없다는 것을 알 수 있습니다.콜모고로프의 복잡도가 스트링의 크기에 비해 작은 의 아바브 예와 같은 스트링들은 복잡하지 않은 것으로 간주됩니다.

콜모고로프 복잡성은 모든 수학적 대상에 대해 정의될 수 있지만, 단순화를 위해 이 기사의 범위는 문자열로 제한됩니다.문자열에 대한 설명 언어를 먼저 지정해야 합니다.이러한 설명 언어는 리스프, 파스칼, 자바와 같은 모든 컴퓨터 프로그래밍 언어를 기반으로 할 수 있습니다.만약 P가 문자열 x를 출력하는 프로그램이라면, P는 x에 대한 설명입니다.설명의 길이는 문자열로서 P의 길이에 문자의 비트 수를 곱한 값입니다(예: ASCII의 경우 7).

또는 튜링 기계에 대한 부호화를 선택할 수 있는데, 여기서 부호화는 각 튜링 기계 M과 비트열 <M>을 연결하는 함수입니다. 만약 M이 입력 w에서 문자열 x를 출력하는 튜링 기계라면, 연결된 문자열 <M> w는 x에 대한 설명입니다. 이론적 분석을 위해,이 접근법은 상세한 형식적 증명을 구성하는 데 더 적합하며 연구 문헌에서 일반적으로 선호됩니다.이 글에서는 비공식적인 접근법에 대해 논의합니다.

문자열에 설명이 하나 이상 있습니다.예를 들어, 위의 두 번째 문자열은 의사 코드에 의해 출력됩니다.

함수 GenerateString2() 반환 "4c1j5b2p0cv4w1x8rx2y39umgw5q85s7"

반면 첫 번째 문자열은 (약간 짧은) 의사 코드로 출력됩니다.

함수 GenerateString1() 반환 "ab" x 16

문자열의 d(s)가 최소 길이인 경우(즉, 가장 적은 비트를 사용함), s의 최소 설명이라고 하며, d(s)의 길이(즉, 최소 설명의 비트 수)는 s콜모고로프 복잡도(, K(s))입니다.상징적으로.

K() = d().

가장 짧은 설명의 길이는 설명 언어의 선택에 따라 달라집니다. 그러나 언어 변경의 효과는 제한됩니다(불변성 정리라고 불리는 결과).

불변성 정리

격식을 차리지

다음과 같은 의미에서 최적의 설명 언어가 있습니다. 설명 언어에서 객체에 대한 설명이 주어지면, 일정한 오버헤드를 가진 최적의 설명 언어에서 해당 설명이 사용될 수 있습니다.상수는 관련된 언어에만 의존하며, 개체의 설명이나 개체의 설명에는 의존하지 않습니다.

여기에 최적 설명 언어의 예가 있습니다.설명은 두 부분으로 구성됩니다.

  • 첫 번째 부분은 다른 설명 언어에 대해 설명합니다.
  • 두 번째 부분은 해당 언어로 된 객체에 대한 설명입니다.

좀 더 전문적인 용어로 설명의 첫 번째 부분은 컴퓨터 프로그램(구체적으로 설명 언어로 작성된 객체의 언어를 위한 컴파일러)이며, 두 번째 부분은 객체를 출력으로 생성하는 컴퓨터 프로그램에 대한 입력입니다.

불변성 정리는 다음과 같습니다. 임의의 설명 언어 L이 주어졌을 때, 최적의 설명 언어는 일정한 오버헤드와 함께 적어도 L만큼 효율적입니다.

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

D' = P + D

P의 길이는 D에 의존하지 않는 상수입니다.따라서 설명된 대상에 관계없이 최대 일정한 오버헤드가 발생합니다.따라서 최적 언어는 이 가산 상수까지 보편적입니다.

보다 격식을 갖춘 치료법

정리:만약1 K2 K가 튜링 완전 기술 언어1 L2 L에 대한 복잡도 함수라면, 상수 c가 존재하며, 이는 오직 선택된 언어1 L과 L에만2 의존합니다.

s. -c ≤ K(s) - K(s) ≤ c.

증명: 대칭성에 의해, 모든 문자열에 대해 어떤 상수 c가 존재한다는 것을 증명하는 으로 충분합니다.

K1() ≤ K2() + c.

이제1 L 언어에 L2 인터프리터 역할을 하는 프로그램이 있다고 가정해 보겠습니다.

함수 통역 언어( 문자열 p)

여기서 p는 L2 프로그램입니다.인터프리터의 특징은 다음과 같습니다.

입니다.InterpretLanguage입력 p에서는 p를 실행한 결과를 반환합니다.

따라서, 만약 P가 s의 최소 기술인 L2 프로그램이라면,InterpretLanguage(P)문자열을 반환합니다.s의 이 설명의 길이는 다음의 합입니다.

  1. 프로그램의 길이InterpretLanguage, 상수 c가 될 수 있습니다.
  2. 정의상 P의 길이는 K(s)입니다2.

원하는 상한을 증명합니다.

역사와 맥락

알고리즘 정보 이론은 콜모고로프 복잡성과 문자열(또는 기타 데이터 구조)에 대한 다른 복잡성 측정을 연구하는 컴퓨터 과학 분야입니다.

콜모고로프 복잡도의 개념과 이론은 레이 솔로몬로프가 1960년에 처음 발견한 중요한 정리를 기반으로 하며, 그는 이 정리를 알고리즘적 확률 발명의 일부로 "귀납적 [3]추론의 일반 이론에 대한 예비 보고서"에 설명했습니다.그는 1964년에 출판한 "귀납적 추론의 형식적 이론"에서 정보[4][5]통제의 1부와 2부를 좀 더 완벽하게 설명했습니다.

안드레이 콜모고로프는 나중에 독립적으로 문제 정보에 이 정리를 발표했습니다. 1965년 전송[6].그레고리 차이틴(Gregory Chaitin)은 이 정리를 1966년 10월에 제출하여 1968년 12월에 수정하였으며, 솔로몬로프와 콜모고로프의 [7]논문을 모두 인용하였습니다.

그 정리는 설명(코드)에서 문자열을 해독하는 알고리즘 중에 최적의 것이 존재한다는 것을 말합니다.이 알고리즘은 모든 문자열에 대해 알고리즘에 따라 달라지지만 문자열 자체에는 달라지지 않는 추가 상수까지 다른 알고리즘에서 허용하는 한 짧은 코드를 허용합니다.솔로몬로프는 이 알고리즘과 코드 길이를 사용하여 문자열의 다음 숫자에 대한 귀납적 추론이 기초할 수 있는 문자열의 "보편적 확률"을 정의했습니다.콜모고로프는 이 정리를 이용해 복잡성, 무작위성, 정보 등 문자열의 여러 기능을 정의했습니다.

콜모고로프는 솔로몬로프의 업적을 알게 되자 솔로몬로프의 [8]우선순위를 인정했습니다.몇 년 동안, 솔로몬로프의 작품은 서방세계에서보다 소련에서 더 잘 알려져 있었습니다.그러나 과학계의 일반적인 합의는 이러한 유형의 복잡성을 시퀀스의 무작위성에 관심이 있는 콜모고로프와 연관시키는 것이었고, 알고리즘 확률은 보편적 사전 확률 분포의 발명을 사용하여 예측에 초점을 맞춘 솔로몬로프와 연관되었습니다.기술적 복잡성과 확률을 포괄하는 더 넓은 영역은 종종 콜모고로프 복잡성이라고 불립니다.컴퓨터 과학자 밍 리는 이것을 매튜 효과의 예로 생각합니다. "... 가진 모든 사람에게 더 많은 것이 주어질 것입니다."[9]

콜모고로프 복잡성 또는 알고리즘 정보에는 몇 가지 다른 변형이 있습니다.가장 널리 사용되는 것은 자기희생 프로그램에 기반을 두고 있으며, 주로 레오니드 레빈(Leonid Levin, 1974)에 기인합니다.

Blum 공리(Blum 1967)에 기초한 콜모고로프 복잡성에 대한 공리적 [10]접근법은 Andrey Kolmogorov가 출판하기 위해 제시한 논문에서 Mark Burgin에 의해 소개되었습니다.

기초결과

다음 논의에서는 K()를 문자열의 복잡도라고 합니다.

문자열의 최소 설명은 문자열 자체보다 너무 클 수 없다는 것을 어렵지 않게 알 수 있습니다. 바로 프로그램입니다.GenerateString2출력 ss보다 큰 고정된 양입니다.

정리:다음과 같은 지속적인 c가 있습니다.

s. K(s) ≤ s + c.

콜모고로프 복잡도의 계산 불가능성

K를 계산하기 위한 프로그램의 순진한 시도

언뜻 보기에는 다음과 같은 K()을 계산할 수 있는 프로그램을 작성하는 것이 하찮아 보일 수 있습니다.

함수 KolmogorovComplexity( 문자열) i = 1 ~ 무한대: 길이의 각 문자열 p에 대해 유효한 프로그램(p)이고 평가(p) == s return i인 경우 정확히 i

이 프로그램은 가능한 모든 프로그램(가능한 모든 문자열을 반복하고 유효한 프로그램만 고려함으로써)을 가장 짧게부터 반복합니다.각 프로그램을 실행하여 해당 프로그램에서 생성된 결과를 입력과 비교합니다.결과가 일치하면 프로그램 길이가 반환됩니다.

그러나 테스트된 프로그램 중 일부는 종료되지 않기 때문에(예: 무한 루프를 포함하는 경우) 작동하지 않습니다.중단 문제의 계산 불가능성 때문에 실행하기 전에 어떤 방식으로든 테스트하여 이 모든 프로그램을 피할 방법은 없습니다.

게다가, 함수 K를 계산할 수 있는 프로그램은 전혀 없습니다.이는 다음과 같이 증명됩니다.

K의 계산 불가능성에 대한 공식적인 증명

정리:임의로 큰 콜모고로프 복잡성의 끈들이 존재합니다.공식적으로: 각각의 자연수 n에 대하여 K(s) ≥로 된 문자열이 있습니다.

증명: 그렇지 않으면 n비트 이하의 복잡도를 가지는 유한[note 2] 개의 프로그램에 의해 무한히 많은 가능한 유한 문자열이 생성될 수 있습니다.

정리: K는 계산 가능한 함수가 아닙니다.즉, 어떤 문자열도 입력으로 받아들이고 정수 K()를 출력으로 생성하는 프로그램이 없습니다.

모순에 의한 다음 증명은 프로그램을 나타내기 위해 간단한 파스칼 같은 언어를 사용합니다. 증명의 단순성을 위해 설명(즉, 인터프리터)은 1400,000 비트의 길이를 갖는다고 가정합니다.모순되는 경우 프로그램이 있다고 가정합니다.

함수 콜모고로프 복잡도( 문자열)

문자열을 입력으로 사용하고 K(s)를 반환합니다.모든 프로그램은 유한한 길이이므로 증명의 단순성을 위해 7000000000비트로 가정합니다.이제 길이 1288비트의 다음 프로그램을 생각해 보겠습니다.

함수 i = 1 ~ 무한대에 대한 ComplexString() 생성: 길이가 정확히 i인 각 문자열에 대해 Kolmogorov Complexity(들)  8000000000이 반환됩니다.

사용.KolmogorovComplexity서브루틴으로서, 프로그램은 콜모고로프 복잡도가 최소 8000000000 [note 3]비트인 문자열을 반환할 때까지, 즉 8000000000 비트보다 짧은 어떤 프로그램에 의해서도 생성될 수 없는 문자열을 최단으로 시작하여 모든 문자열을 시도합니다.그러나, s를 생성한 상기 프로그램의 전체 길이는 7001401288 [note 4]비트에 불과하며, 이는 모순입니다.(코드명:KolmogorovComplexity더 짧으면 모순이 남습니다.이 값이 길면 상수는GenerateComplexString항상 적절하게 변경할 수 있습니다.)[note 5]

위의 증명은 베리 역설의 모순과 유사한 모순을 사용한다:1 "20개 미만의 영어 단어로 정의될 수 없는 가장 작은 양의 정수".K와 H는 튜링 [11]등가이기 때문에 정지 문제 H의 계산 불가능성에서 감소하여 K의 계산 불가능성을 보여주는 것도 가능합니다.

프로그래밍 언어 커뮤니티에는 완벽한 크기 최적화 컴파일러가 없다는 유머러스하게 "완전 고용 정리"라고 불리는 논리가 있습니다.

콜모고로프 복잡도에 대한 연쇄법칙

콜모고로프 복잡성에 대한 연쇄[12] 규칙은 다음과 같이 말합니다.

K(X,Y) = K(X) + K(YX) + O(log(K(X,Y))).

X와 Y를 재현하는 최단 프로그램은 X를 재현하는 프로그램과 X가 주어지면 Y를 재현하는 프로그램보다 더 큰 로그항에 불과하다는 것입니다.이 문장을 사용하여 콜모고로프 복잡성에 대한 상호 정보의 아날로그를 정의할 수 있습니다.

압축

K()에 대한 상한을 계산하는 것은 간단합니다. 어떤 방법으로 문자열압축하고, 선택한 언어로 해당 압축 해제기를 구현하고, 압축 해제기를 압축된 문자열에 연결하고, 결과적인 문자열의 길이를 측정하는 것입니다. 구체적으로, 주어진 언어의 자체 압축 해제 아카이브의 크기입니다.

문자열은 길이가 s - c 비트를 초과하지 않는 설명이 있는 경우 숫자 c로 압축할 수 있습니다.이는 K(s) ≤ s - c라고 하는 것과 같습니다.그렇지 않으면 s는 c로 압축할 수 없습니다.1로 압축할 수 없는 문자열은 단순히 비압축성이라고 할 수 있는데, 이는 모든 압축 문자열이 하나의 비압축 문자열에만 매핑되기 때문에 적용되는 비둘기 구멍 원리에 의해 비압축성 문자열이 존재해야 하는데, 이는 길이 n의 비트열이 2개이지만n 길이 n보다 작은 문자열은 2 - 1개뿐이기n 때문입니다.0, 1, ..., n − 1).[note 6]

같은 이유로, 대부분의 문자열은 상당히 압축될 수 없다는 점에서 복잡합니다. 즉, K(s)는 비트 단위의 s 길이인 s보다 훨씬 작지 않습니다.이를 정확하게 하기 위해서 n 을 고정합니다.길이 n의 비트열이 2개 있습니다n.이러한 비트열의 공간에 대한 균일한 확률 분포는 길이 n의 각 문자열에 정확히 동일한 가중치n 2를 할당합니다.

정리:길이 n의 비트열 공간에 균일한 확률 분포를 사용하면 문자열이 c만큼 압축할 수 없을 확률은 최소 1c+1 - 2 + 2입니다n.

정리를 증명하기 위해 n - c넘지 않는 길이에 대한 설명의 수는 기하급수로 주어집니다.

1 + 2 + 22 + ...+ 2nc = 2nc+1 − 1.

적어도 남아있습니다.

2n − 2nc+1 + 1

c로 압축할 수 없는 n개 길이의 비트열.확률을 결정하려면 2로n 나눕니다.

차이틴의 불완전성 정리

콜모고로프 복잡도 K() 및 계산 가능한 하한 함수 2개prog1(s),prog2(s) . 가로축(논리 스케일)은 길이순으로 정렬된 모든 문자열을 열거하며, 세로축(선형 스케일)은 콜모고로프 복잡도를 비트 단위로 측정합니다.대부분의 문자열은 압축할 수 없습니다. 즉, 콜모고로프 복잡도가 일정한 양만큼 길이를 초과합니다.9개의 압축 가능한 문자열이 그림에 나타나 있으며 거의 수직 경사로 나타납니다.차이틴의 불완전성 정리(1974)로 인해 콜모고로프 복잡도의 하한을 계산하는 모든 프로그램의 출력은 입력 문자열과 독립적인 고정 한계를 초과할 수 없습니다.

위의 정리(§ Compression)에 의해, 대부분의 문자열은 의미 있는 "압축" 방식으로 설명할 수 없다는 점에서 복잡합니다.그러나 특정 문자열의 복잡성이 특정 임계값 이상일 경우 특정 문자열이 복잡하다는 사실을 공식적으로 증명할 수 없음이 밝혀집니다.정확한 형식은 다음과 같습니다.먼저 자연수에 대한 특정 공리계 S를 고정합니다.공리계는 문자열의 복잡성에 대한 특정 주장 A에 S의 공식A F를 연관시킬 수 있도록 충분히 강력해야 합니다.이 연결에는 다음 속성이 있어야 합니다.

만약A F가 S의 공리로부터 증명할 수 있다면, 그에 대응하는 주장 A는 참이어야 합니다. "공식화"는 괴델 번호를 기반으로 이루어질 수 있습니다.

정리:문장에 해당하는 문자열이 존재하지 않도록 상수 L(S와 설명 언어의 선택에만 의존함)이 존재합니다.

K(s) L (S에서 공식화한 바와 같이)

S [13][14]에서 증명할 수 있습니다.

증명 아이디어:이 결과의 증거는 베리의 역설에 사용된 자기 참조 구조를 모델로 합니다.우리는 먼저 S 에 있는 증명들을 열거하는 프로그램을 얻고 정수 L을 입력으로 하고 문장 K(x) ≥ L의 S 에 있는 증명들인 문자열 x를 출력하는 프로시저 P를 지정합니다. L을 이 프로시저 P의 길이보다 크게 설정함으로써 x를 출력하는 프로그램의 필요한 길이를 명시합니다.K(x) ≥ L적어도 L인 경우에는 문자열 x가 절차 P에 의해 인쇄되었기 때문에 L의 양보다 적습니다.이것은 모순입니다.따라서 증명 시스템 S가 임의로 큰 L에 대해 K(x) ≥ L증명하는 것은 불가능하며, 특히 절차 P의 길이(유한)보다 큰 L에 대해 증명할 수 있습니다.

증명:

우리는 몇 가지 절차에 의해 S의 모든 형식적 증명의 효과적인 열거를 찾을 수 있습니다.

기능 NthProof(intn)

n을 입력하고 증명을 출력합니다.이 함수는 모든 증명을 열거합니다.이들 중 일부는 S 언어로 가능한 모든 증명이 일부 n에 대해 생성되기 때문에 여기서는 상관하지 않는 공식에 대한 증명입니다.이들 중 일부는 S 언어에서 sn상수인 K(s) ≥ 형태의 복잡도 공식입니다.절차가 있습니다.

기능 N차 증명 복잡성 입증공식(intn)

이것은 n번째 증명이 실제로 복잡도 공식 K(s) ≥ L을 증명하는지 여부를 결정합니다. 문자열정수 L은 순서에 따라 계산할 수 있습니다.

기능 StringNthProof(intn)
함수 복잡도하한 N차 방지(intn)

다음 절차를 고려합니다.

함수 i = 1 ~ 무한대에 대해 적합하게 복잡한 문자열(intn) 생성: N번째 Proof가 복잡도를 증명하는 경우수식(i) 및 복잡도LowerBoundNthProof(i) ≥ 반환 StringNthProof(i

n이 주어지면, 이 절차는 일부 L ≥에 대한 공식 K(s) ≥ L의 공식 시스템 S에서 문자열과 증명을 찾을 때까지 모든 증명을 시도합니다. 만약 그러한 증명이 존재하지 않으면, 영원히 루프합니다.

마지막으로, 이 모든 절차 정의와 주요 통화로 구성된 프로그램을 고려해 보겠습니다.

적합하게 복잡한 문자열 생성(n0)

여기서 상수0 n은 나중에 결정됩니다.전체 프로그램 길이는 U+log2(n0)로 표현할 수 있으며, 여기서 U는 어느 정도 상수이고2 log(n0)는 정수 0 n의 길이를 나타냅니다. 2진수로 인코딩된다는 합리적인 가정 하에서 말입니다.n > U+log2(n0)이0 되도록 프로그램 길이보다 크게 선택합니다0.이것은 n개의 충분히 큰 경우0 명백하게 사실입니다. 왜냐하면 왼쪽은 n에서0 선형적으로 성장하는 반면 오른쪽은 고정 상수 U까지 로그적으로0 성장하기 때문입니다.

그렇다면 "K(s)"라는 형태의 증거는 없습니다.L≥n갖는 L"은 S에서 구할 수 있으며, 이는 간접적인 논법으로 알 수 있다:ComplexityLowerBoundNthProof(i)값 ≥n을 반환할 수 있고, 그 다음에 내부의 루프.GenerateProvablyComplexString결국 종료될 것이고, 그 절차는 다음과 같은 문자열을 반환할 것입니다.

K()
n0 의 건설에 의하여GenerateProvablyComplexString
> U+log2(n0) n0 선택에 의하여
K() s는 그 길이의 프로그램에 의해 묘사되었기 때문입니다.

이건 모순이에요, Q.E.D.

결과적으로, 선택된 n0 값을 갖는 상기 프로그램은 영원히 루프되어야 합니다.

차이틴 상수의 성질을 증명하기 위해 비슷한 개념이 사용됩니다.

최소 메시지 길이

통계적 및 귀납적 추론과 기계학습의 최소 메시지 길이 원리는 C.S.의해 개발되었습니다. 월리스와 D.M. 볼튼은 1968년에MML은 베이지안(즉, 이전의 신념을 통합한 것)이며 정보 이론적입니다.그것은 통계적 불변성(즉, 극좌표에서 직각좌표로 이동하는 것과 같은 재모수화로 추론 변환), 통계적 일관성(즉, 매우 어려운 문제에 대해서도 MML은 어떤 기본 모델로 수렴할 것) 및 효율성(즉,)의 바람직한 속성을 가지고 있습니다.MML 모델은 가능한 한 빨리 모든 진정한 기본 모델로 수렴될 것입니다.C.S. Wallace와 D.L. Dowe(1999)는 MML과 알고리즘 정보 이론(또는 Kolmogorov complexity)[15] 간의 공식적인 연관성을 보여주었습니다.

콜모고로프 무작위성

콜모고로프 무작위성(Kolmogorov randomness)은 문자열을 생성할 수 있는 모든 컴퓨터 프로그램이 문자열 자체의 길이만큼 긴 경우에만 무작위로 정의됩니다.이를 정확하게 하기 위해서는 범용 컴퓨터(또는 범용 튜링 기계)가 지정되어야 하며, 따라서 "프로그램"은 이 범용 기계를 위한 프로그램을 의미합니다.이런 의미에서 임의의 문자열은 문자열 자체보다 짧은 프로그램으로 "압축"하는 것이 불가능하다는 점에서 "압축 불가능"합니다.모든 범용 컴퓨터에는 각 [16]길이의 알고리즘적으로 랜덤한 문자열이 적어도 하나씩 있습니다.그러나 특정 문자열이 임의인지 여부는 선택된 특정 범용 시스템에 따라 달라집니다.범용 컴퓨터는 특정 문자열을 하드 코딩할 수 있고, 이 범용 컴퓨터에서 실행되는 프로그램은 단순히 짧은 비트 시퀀스(즉, 문자열 자체보다 훨씬 짧은)를 사용하여 하드 코딩된 문자열을 참조할 수 있기 때문입니다.

이 정의는 유한 알파벳의 무한 순서에 대한 무작위성 개념을 정의하기 위해 확장될 수 있습니다.알고리즘적으로 랜덤한 시퀀스는 세 가지 동등한 방법으로 정의할 수 있습니다.한 가지 방법은 효과적인 측정 이론의 아날로그를 사용하고 다른 방법은 효과적인 마르팅게일을 사용합니다.세 번째 방법은 초기 세그먼트의 접두사가 없는 콜모고로프 복잡성이 충분히 빠르게 증가할 경우 무한 시퀀스를 무작위로 정의합니다. 길이 n의 초기 세그먼트의 복잡성이 항상 n-c 이상이 되도록 일정한 c가 있어야 합니다.이 정의는 유한 문자열에 대한 무작위성 정의와 달리 접두사가 없는 콜모고로프 복잡성을 [17]정의하는 데 사용되는 범용 기계에 영향을 받지 않습니다.

엔트로피와의 관계

동적 시스템의 경우, 궤적의 엔트로피 속도와 알고리즘 복잡성은 거의 x {\ x에 대해 K (T) = ( K () = (가 성립하는 브루드노 정리와 관련이 있습니다.

마코프 정보원의 출력에서 콜모고로프 복잡도는 정보원의 엔트로피와 관련이 있음을[19] 알 수 있습니다.더 정확하게 말하면, 출력의 길이로 정규화된 마르코프 정보 소스의 출력의 콜모고로프 복잡성은 (출력의 길이가 무한대로 가면서) 소스의 엔트로피에 거의 확실히 수렴합니다.

조건부 버전

K K 조건부 콜모고로프 복잡도는 [20][21]대략적으로 절차에 대한 보조 입력으로 y가 주어진 x의 콜모고로프 복잡도로 정의됩니다.

또한 길이 조건 K ( L () K (L ( 가 있는데, 이는 알려진/[22][23]입력된 x의 길이를 고려할 때 x의 복잡도입니다.

참고 항목

메모들

  1. ^ 그러나 K() = n마찬가지모든 n에 대해 존재할 필요는 없습니다.예를 들어 n이 7의 배수가 아닌 경우, 어떤 ASCII 프로그램도 정확히 n비트의 길이를 가질 수 없습니다.
  2. ^ 1 + 2 + 22 + 2 + 23 + ...+ 2 = 2 - n비트까지의 길이를 가진 1개의 다른 프로그램 텍스트; cf. 기하급수.프로그램 길이가 7비트의 배수가 되어야 한다면, 훨씬 더 적은 프로그램 텍스트가 존재합니다.
  3. ^ 앞의 정리에 의하면, 그러한 문자열이 존재하므로,for루프는 결국 종료됩니다.
  4. ^ 언어 통역사와 서브루틴 코드를 포함합니다.KolmogorovComplexity
  5. ^ 한다면KolmogorovComplexityn비트 길이, 에서 사용되는 상수 m을 갖습니다.GenerateComplexStringn + 1400000 + 1218 + 7·log10(m) < m만족하도록 조정해야 합니다. 이는 m이 log(m)보다10 빨리 성장하기 때문에 항상 가능합니다.
  6. ^ 길이 L의 문자열이 N = 2개이므로 길이 L의 문자열 수 = 0, 1, ..., n - 1 N + N + ...입니다.+ N = 2 + 2 + ...+ 2n−10, 이것은 1 2 + 2 + ...유한 기하급수입니다.+ 2 = 2 × (1 - 2) / (1 - 2) = 2 - 1

참고문헌

  1. ^ Kolmogorov, Andrey (1963). "On Tables of Random Numbers". Sankhyā Ser. A. 25: 369–375. MR 0178484.
  2. ^ Kolmogorov, Andrey (1998). "On Tables of Random Numbers". Theoretical Computer Science. 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.
  3. ^ Solomonoff, Ray (February 4, 1960). A Preliminary Report on a General Theory of Inductive Inference (PDF). Report V-131 (Report). Revision published November 1960. Archived (PDF) from the original on 2022-10-09.
  4. ^ Solomonoff, Ray (March 1964). "A Formal Theory of Inductive Inference Part I" (PDF). Information and Control. 7 (1): 1–22. doi:10.1016/S0019-9958(64)90223-2. Archived (PDF) from the original on 2022-10-09.
  5. ^ Solomonoff, Ray (June 1964). "A Formal Theory of Inductive Inference Part II" (PDF). Information and Control. 7 (2): 224–254. doi:10.1016/S0019-9958(64)90131-7. Archived (PDF) from the original on 2022-10-09.
  6. ^ Kolmogorov, A.N. (1965). "Three Approaches to the Quantitative Definition of Information". Problems Inform. Transmission. 1 (1): 1–7. Archived from the original on September 28, 2011.
  7. ^ Chaitin, Gregory J. (1969). "On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers". Journal of the ACM. 16 (3): 407–422. CiteSeerX 10.1.1.15.3821. doi:10.1145/321526.321530. S2CID 12584692.
  8. ^ Kolmogorov, A. (1968). "Logical basis for information theory and probability theory". IEEE Transactions on Information Theory. 14 (5): 662–664. doi:10.1109/TIT.1968.1054210. S2CID 11402549.
  9. ^ Li, Ming; Vitányi, Paul (2008). "Preliminaries". An Introduction to Kolmogorov Complexity and its Applications. Texts in Computer Science. pp. 1–99. doi:10.1007/978-0-387-49820-1_1. ISBN 978-0-387-33998-6.
  10. ^ Burgin, M. (1982). "Generalized Kolmogorov complexity and duality in theory of computations". Notices of the Russian Academy of Sciences. 25 (3): 19–23.
  11. ^ 증명 없이 다음과 같이 기술:
  12. ^ Zvonkin, A.; L. Levin (1970). "The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms" (PDF). Russian Mathematical Surveys. 25 (6): 83–124. Bibcode:1970RuMaS..25...83Z. doi:10.1070/RM1970v025n06ABEH001269. S2CID 250850390.
  13. ^ Gregory J. Chaitin (Jul 1974). "Information-theoretic limitations of formal systems" (PDF). Journal of the ACM. 21 (3): 403–434. doi:10.1145/321832.321839. S2CID 2142553. 여기: Thm.4.1b
  14. ^ Calude, Cristian S. (12 September 2002). Information and Randomness: an algorithmic perspective. Springer. ISBN 9783540434665.
  15. ^ Wallace, C. S.; Dowe, D. L. (1999). "Minimum Message Length and Kolmogorov Complexity". Computer Journal. 42 (4): 270–283. CiteSeerX 10.1.1.17.321. doi:10.1093/comjnl/42.4.270.
  16. ^ 길이 n의 비트열은 2개이지만n 길이 n의n 비트열은 2-1개밖에 더 짧아서 압축 결과가 많아야 가능합니다.
  17. ^ Martin-Löf, Per (1966). "The definition of random sequences". Information and Control. 9 (6): 602–619. doi:10.1016/s0019-9958(66)80018-9.
  18. ^ Galatolo, Stefano; Hoyrup, Mathieu; Rojas, Cristóbal (2010). "Effective symbolic dynamics, random points, statistical behavior, complexity and entropy" (PDF). Information and Computation. 208: 23–41. arXiv:0801.0209. doi:10.1016/j.ic.2009.05.001. S2CID 5555443. Archived (PDF) from the original on 2022-10-09.
  19. ^ Alexei Kaltchenko (2004). "Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics". arXiv:cs.CC/0404039.
  20. ^ Jorma Rissanen (2007). Information and Complexity in Statistical Modeling. Springer S. p. 53. ISBN 978-0-387-68812-1.
  21. ^ Ming Li; Paul M.B. Vitányi (2009). An Introduction to Kolmogorov Complexity and Its Applications. Springer. pp. 105–106. ISBN 978-0-387-49820-1.
  22. ^ Ming Li; Paul M.B. Vitányi (2009). An Introduction to Kolmogorov Complexity and Its Applications. Springer. p. 119. ISBN 978-0-387-49820-1.
  23. ^ Vitányi, Paul M.B. (2013). "Conditional Kolmogorov complexity and universal probability". Theoretical Computer Science. 501: 93–100. arXiv:1206.0983. doi:10.1016/j.tcs.2013.07.009. S2CID 12085503.

추가열람

외부 링크