데이터 압축에 대한 역설

가장 간단한 형태의 데이터 압축 문제는 숫자 및 표기법과 관련될 수 있습니다. 숫자는 숫자("열하나" 숫자 11의 경우), 수학식("XNUMX분의 XNUMX" 1048576의 경우), 문자열 표현식("파이브 나인" 99999의 경우), 고유명사("짐승의 수" 666의 경우, "튜링이 죽은 해" for 1954) 또는 이들의 임의 조합. 대담자가 우리가 말하는 숫자를 명확하게 결정할 수 있도록 모든 지정이 적합합니다. 분명히 대화 상대에게 말하십시오. "XNUMX의 계승" 등가 표기법보다 효율적 "사만삼백이십". 여기서 논리적인 질문이 생깁니다. 주어진 숫자에 대한 가장 짧은 표기법은 무엇입니까?

철학자 버트런드 러셀은 1908년에 출판했습니다. "베리의 역설", 반대편의 숫자 표기 문제를 다룹니다. XNUMX자를 필요로 하지 않는 가장 작은 숫자는 무엇입니까?
이러한 숫자는 반드시 존재해야 합니다. 3480개의 러시아어 문자와 공백 중에서 3480개만 지정할 수 있습니다. 즉, 3480개의 문자를 사용하면 XNUMX개 이하의 숫자를 지정할 수 있습니다. 이는 이런 방식으로 XNUMX 이하의 특정 숫자를 지정할 수 없음을 의미합니다.

이는 이 번호가 지정에 해당함을 의미합니다. "XNUMX개의 글자로 충분하지 않은 가장 작은 숫자", 78 글자 밖에 없습니다! 한편으로는 이 숫자가 존재해야 합니다. 반면에 이 번호가 존재하면 해당 지정이 해당 번호와 일치하지 않는 것입니다. 역설!

이 역설을 일축하는 가장 쉬운 방법은 언어 표기법의 비공식성을 언급하는 것입니다. 예를 들어, 특별히 정의된 표현식 세트만 표기법에 허용된 경우 "XNUMX개의 글자로 충분하지 않은 가장 작은 숫자" 유효한 표기법은 아니지만 실제로 유용한 표기법은 다음과 같습니다. "XNUMX의 계승" 허용 가능한 상태로 유지됩니다.

숫자에 대한 동작 순서(알고리즘)를 설명하는 공식적인 방법이 있습니까? 프로그래밍 언어라고 불리는 것들이 많고 풍부합니다. 구두 표기 대신 필요한 숫자를 표시하는 프로그램(예: Python)을 사용합니다. 예를 들어, XNUMX의 경우 프로그램이 적합합니다. print("9"*5). 우리는 주어진 숫자에 대한 가장 짧은 프로그램에 계속 관심을 가질 것입니다. 그러한 프로그램의 길이를 콜모고로프 복잡성 숫자; 이는 주어진 숫자를 압축할 수 있는 이론적 한계입니다.

이제 Berry의 역설 대신에 유사한 역설을 생각해 볼 수 있습니다. 킬로바이트 프로그램이 출력하기에 충분하지 않은 가장 작은 숫자는 무엇입니까?

우리는 이전과 같은 방식으로 추론할 것입니다: 2561024킬로바이트 텍스트가 있으며, 이는 킬로바이트 프로그램에서 2561024개 이상의 숫자를 출력할 수 없음을 의미합니다. 이는 2561024보다 크지 않은 특정 숫자를 이런 방식으로 파생할 수 없음을 의미합니다.

하지만 가능한 모든 킬로바이트 텍스트를 생성하고, 실행을 위해 실행하고, 숫자가 출력되면 이 숫자를 도달 가능한 숫자 사전에 추가하는 프로그램을 Python으로 작성해 보겠습니다. 2561024개의 가능성을 모두 확인한 후, 시간이 얼마나 걸리더라도 프로그램은 사전에서 누락된 가장 작은 숫자를 찾아 해당 숫자를 인쇄합니다. 그러한 프로그램이 XNUMX킬로바이트의 코드에 들어갈 것이라는 것은 명백해 보입니다. 그리고 킬로바이트 프로그램에서 출력할 수 없는 바로 그 숫자를 출력할 것입니다!

지금 문제는 무엇입니까? 더 이상 표기법의 비공식성 때문이라고 할 수 없습니다!

우리 프로그램이 작동하려면 천문학적인 양의 메모리(2561024 요소의 사전(또는 비트 배열))가 필요하다는 사실에 혼란스러우면 이 메모리 없이도 동일한 작업을 수행할 수 있습니다. 각 2561024 숫자에 대해 차례로 , 적합한 프로그램이 없을 때까지 2561024개의 가능한 프로그램을 모두 살펴보세요. 이러한 검색이 매우 오랜 시간 동안 지속된다는 것은 중요하지 않습니다. 숫자와 프로그램에서 (2561024)2 쌍 미만을 확인한 후 종료되고 매우 소중한 숫자를 찾습니다.

아니면 끝나지 않을 것인가? 실제로, 시도될 모든 프로그램 중에는 while True: pass (및 그 기능적 유사체) - 문제는 그러한 프로그램을 테스트하는 것 이상으로 진행되지 않습니다!

표기법의 비공식성에 문제가 있었던 베리의 역설과는 달리, 두 번째 경우에는 잘 위장된 재구성이 있습니다. "문제 중지". 사실은 유한한 시간 내에 프로그램의 출력을 결정하는 것이 불가능하다는 것입니다. 특히 Kolmogorov 복잡성 계산할 수 없는: 주어진 숫자에 대해 이 숫자를 인쇄하는 가장 짧은 프로그램의 길이를 찾는 것을 허용하는 알고리즘은 없습니다. 이는 Berry의 문제에 대한 해결책이 없음을 의미합니다. 즉, 주어진 숫자에 대한 가장 짧은 구두 지정 길이를 찾는 것입니다.

출처 : habr.com