データ圧縮の問題は、最も単純な形では、数値とその表記法に関係する可能性があります。 数値は数字 ("十一" 数値 11)、数式 (「XNUMX分のXNUMX」 1048576の場合)、文字列式(「ファイブナイン」 99999 の場合)、固有名 (「獣の数」 666の場合、 「チューリングの死の年」 1954 年の場合）、またはそれらの任意の組み合わせ。 対話者が私たちがどの番号について話しているのかを明確に判断できるようにするための任意の指定が適しています。 もちろん、相手に伝えてください 「XNUMXの階乗」 同等の表記法よりも効率的 「四万三百二十」。 ここで論理的な疑問が生じます: 与えられた数値の最も短い表記法は何でしょうか?
哲学者バートランド・ラッセルが1908年に出版した 、これは反対側から数値表記の問題に触れています。 XNUMX文字を必要としない最小の数字は何ですか?
このような数字は必ず存在します。3480 個のロシア語の文字とスペースからは 3480 個の指定しか作成できません。つまり、3480 個の文字を使用しても指定できる数字は XNUMX 個までです。 これは、このように XNUMX を超えない特定の番号を指定することは不可能であることを意味します。
これは、この番号が指定に対応することを意味します 「XNUMX文字では足りない最小の数字」、文字数はわずか 78 文字です。 一方で、この数字は存在する必要があります。 一方、この番号が存在する場合、その指定はそれに対応しません。 逆説！
この矛盾を却下する最も簡単な方法は、口頭表記の非公式性に言及することです。 たとえば、特別に定義された一連の式のみが表記法で許可される場合、 「XNUMX文字では足りない最小の数字」 は有効な表記法ではありませんが、次のような実際に役立つ表記法はありません。 「XNUMXの階乗」 許容範囲内にとどまるだろう。
数値に対するアクションのシーケンス (アルゴリズム) を記述する正式な方法はありますか? プログラミング言語と呼ばれるものはたくさんあります。 口頭による表記の代わりに、必要な数値を表示するプログラム (Python など) を使用します。 たとえば、ファイブナインにはプログラムが適しています。 print("9"*5)。 私たちは、与えられた数値に対する最短プログラムに引き続き関心を持っていきます。 このようなプログラムの長さは次のように呼ばれます。 数字。 これは、特定の数値を圧縮できる理論上の限界です。
ベリーのパラドックスの代わりに、同様のパラドックスを考えることができます。 キロバイトのプログラムでは出力できない最小の数値は何ですか?
前と同じ方法で推論します。テキストは 2561024 キロバイトあります。これは、キロバイトのプログラムで出力できる数値は 2561024 個までであることを意味します。 これは、2561024 以下の特定の数値をこの方法では導出できないことを意味します。
しかし、考えられるすべてのキロバイトのテキストを生成し、それらを実行して数値が出力された場合は、その数値を到達可能なものの辞書に追加するプログラムを Python で作成してみましょう。 2561024 通りの可能性をすべてチェックした後、どれだけ時間がかかっても、プログラムは辞書から欠落している最小の数値を探し、その数値を出力します。 このようなプログラムが XNUMX キロバイトのコードに収まり、キロバイトのプログラムでは出力できない数値を出力することは明らかです。
今の獲物は何ですか？ それはもはや表記の非公式さに起因するものではありません。
私たちのプログラムが動作するには天文学的な量のメモリ (2561024 個の要素の辞書 (またはビット配列)) が必要であるという事実に混乱している場合は、それを使用せずに同じことを行うことができます。2561024 個の数値ごとに順番に実行します。 、適切なプログラムがなくなるまで、2561024 個の可能なプログラムをすべて検討します。 このような検索が非常に長時間続くことは問題ではありません。番号とプログラムから (2561024)2 未満のペアをチェックした後、検索は終了し、その非常に重要な番号を見つけます。
それとも終わらないのでしょうか？ 実際、試行されるすべてのプログラムの中には、 while True: pass (およびその機能的類似物) - そして問題は、そのようなプログラムをテストする以上に進みません。
表記法が非公式であることに問題があったベリーのパラドックスとは異なり、XNUMX 番目のケースでは、うまく隠蔽された再定式化が行われます。 。 実際のところ、有限時間内にプログラムからの出力を決定することは不可能です。 特に、コルモゴロフ複雑さ : 与えられた数値に対して、その数値を出力する最短のプログラムの長さを見つけることを可能にするアルゴリズムはありません。 これは、ベリーの問題、つまり、与えられた数字に対する最短の口頭指定の長さを見つけるという問題には解決策がないことを意味します。
出所： habr.com