最も単純な形式のデータ圧縮のタスクは、数値とその表記法に関連する可能性があります。 数字は数字（ 11の場合は「11」 ）、数式（1048576の場合は「20分の2」 ）、文字列式（99999の場合は「ファイブナイン」 ）、666の場合は「 獣の数」 、 「チューリングの死の年」 " 1954年）、またはそれらの任意の組み合わせ。 対話者がどの種類の発言が適切であるかを明確に決定することができる任意の指定が適切です。 明らかに、対人関係者に「階乗8」を知らせることは、同等の呼称「4万3000」よりも効果的です。 これは論理的な問題を提起します：与えられた番号の最短指定は何ですか？
1908年に哲学者のバートランドラッセルは、反対側の数字の表記の問題に対処する「ベリーパラドックス」を発表しました。80文字が足りないことを示す最小の数字は何ですか？
そのような数字が存在する必要があります：80のロシア語の文字とスペースから、合計34 80の指定を作成できます。つまり、80の文字を使用して、34 80の数字しか指定できません。 したがって、34 80以下の特定の番号をこの方法で指定することはできません。
これは、 「80文字では不十分な最小の数字」という指定がこの数字に対応することを意味し、78文字しかありません。 一方では、この番号が存在する必要があります。 一方、この番号が存在する場合、その指定はそれに対応しません。 パラドックス！
このパラドックスを却下する最も簡単な方法は、言葉による指定の非公式性を参照することです。 同様に、表記で特定の表現セットのみが許可されている場合、 「80文字では不十分な最小数」は有効な指定ではありませんが、 「階乗8」タイプの実際に有用な指定は有効のままです。
数値に対するアクションのシーケンス（アルゴリズム）を記述する正式な方法はありますか？ 豊富にあります-それらはプログラミング言語と呼ばれます。 言語表記の代わりに、必要な数値を出力するプログラム（たとえば、Python）を使用します。 たとえば、ファイブナインの場合、
print("9"*5)
プログラム
print("9"*5)
適しています。 私たちは、与えられた数の最短プログラムに興味を持ち続けます。 このようなプログラムの長さは、 コルモゴロフ数の複雑さと呼ばれます。 これは、特定の数値を圧縮できる理論上の制限です。
ベリーのパラドックスの代わりに、同様のパラドックスを考えることができます。キロバイトのプログラムでは不十分な最小数は何ですか？
前と同じ方法で議論します。256,1024キロバイトのテキストがあります。つまり、キロバイトプログラムでは256,224を超える数値を表示できません。 したがって、この方法では、256 1024以下の特定の数を推定できません。
しかし、可能なすべてのキロバイトテキストを生成し、それらを実行するために起動し、それらが特定の数を出力する場合、この数は達成可能な辞書に追加されます。 256 1024の可能性をすべてチェックした後、プログラムはどれだけ時間がかかっても、辞書にない最小の番号を探し、この番号を表示します。 このようなプログラムが1キロバイトのコードに収まることは明らかです。1キロバイトのプログラムでは表示できない数値を出力します。
今のキャッチは何ですか？ 表記法の非公式性によるものではありません！
プログラムが動作するために天文学的な量のメモリ（256 1024要素の辞書（またはビットマップ））を必要とすることに混乱している場合、それなしで同じことを行うことができます：256 1024の数字ごとに、可能なすべての256 1024を反復処理します適切なものが見つかるまでプログラムします。 このような列挙が非常に長く続くことは問題ではありません。数とプログラムから（256 1024 ） 2ペア未満をチェックした後、終了し、非常に大切な数を見つけます。
それとも終わりませんか？ 確かに、試行されるすべてのプログラムの中で
while True: pass
（およびその機能的な同等物）があり、物事はそのようなプログラムをチェックする以上のことはありません！
キャッチが非公式の表記法であったベリーのパラドックスとは異なり、2番目のケースでは、 「停止問題」のよく偽装された再定式化があります。 事実、プログラムによれば、有限の時間内に結論を決定することは不可能です。 特に、コルモゴロフの複雑さは計算できません。この数値を出力する最短のプログラムの長さを特定の数値で検索できるアルゴリズムはありません。 これは、ベリー問題の解決策がないことを意味します-与えられた数について、最短の単語指定の長さを見つけること。