HN 日本語サマリー

← 一覧へ戻る
科学・技術

数学におけるつながり:ランダムの二種類

Connections in Math: the two kinds of random (stillthinking.net)

38 pointsby pcael25 コメント

要約

この記事は、統計的に区別がつかないように見える2つのデータセット(ランダムノイズと円周率の数字)を例に、圧縮可能性の2つの異なる種類について論じています。1つは記号の出現頻度に依存する統計的冗長性によるもので、もう1つは生成プロセスが単純であることによるものです。後者の圧縮可能性は、統計的性質だけでは捉えられない、より深い概念であることを示唆しています。

全文翻訳

数学におけるつながり:2種類のランダム

免責事項:この記事の執筆にAIは使用されていません。誤字脱字、不自然な言い回し、奇妙な脱線はすべて100%オーガニック、フリーレンジ、人間が作ったものです。

放置していたパズルを拾い上げる

前回の投稿の最後に、私はパズルを投げ出して立ち去りました。今回もそれを提示します。なぜなら、この記事全体が、私がそれを手放せないことの裏返しだからです。

2つのファイルがあると想像してください。それぞれに100万桁の数字が入っています。最初のファイルは純粋なノイズです。10面ダイスを100万回振ってその結果を書き留めたと想像してください。2番目のファイルは、円周率πの最初の100万桁です。

次に、統計学者のようにそれらを見てみましょう。00から99までの各数字が何回出現するかを数えます。どちらのファイルでも、各数字は約10分の1の確率で出現します。そのため、2つのヒストグラムをプロットしても、それらを区別することはできません。どちらも平坦で、特徴がありません。そして、「これはランダムか?」というテストを好きなだけ実行できます。なぜなら、どちらのファイルも合格するからです。あらゆる統計的尺度において、これら2つのファイルは同じです。どちらも純粋で、圧縮不可能なランダム性のように見えます。

[画像: 同じヒストグラムが2つ。統計的には、ノイズとπは区別がつかず、どちらも平坦で「圧縮不可能」である。]

しかし、それでも。

これらのファイルのうち、1つは3行であなたに送ることができます。私はあなたに小さなプログラムを書きます。「πを計算し、100万桁を出力せよ」というプログラムです。あなたはファイルを正確に再生できます。もう一方のファイルはまったく短縮できません。あなたに送るためには、数字ごとに、そのファイル自体のより短い説明がないため、全体を送る必要があります。

したがって、この記事全体の質問は次のようになります。

2つのファイルが統計的に同一であるのに、なぜ一方だけを圧縮できるのでしょうか?

この質問には簡単な答えがなく、それがまさに興味深い点だと私は思います。これについて何か進展を得るためには、「圧縮可能」という言葉が実際に何を意味するのかを注意深く考える必要があります。そして、注意深くなると、それは2つの非常に異なる考えに分かれます。この記事の大部分は、それら2つを分離し、2番目のものに待っている驚き、つまり、存在するときはいつでも確認でき、存在しないときは決して除外できない種類の圧縮可能性についてです。

2種類の圧縮

最初にはっきりさせておきたいことがあります。この記事のすべては可逆圧縮に関するものです。これは、何も破棄されず、何も近似されないことを意味します。短い説明を送り、あなたは元のデータをビット単位で正確に再構築できます。

その厳密なルールでも、物事が圧縮可能である理由は本当に2つあると私は思います。そして、この記事はその2つを区別することを学ぶことが主です。

最初の理由は統計的なものです。一部のシンボルは他のシンボルよりも頻繁に出現するため、一般的なシンボルには短いコードを、まれなシンボルには長いコードを与え、平均してスペースを節約します。これはzipファイルやハフマンコーディングが行うことであり、ほとんどの人が「圧縮」という言葉を聞いたときに思い浮かべる種類のものだと私は思います。

2番目の理由はプロセスに関するものです。シンボルが完全に均等に分散しているように見えても、そのデータは単純なルール、つまり短いプログラムから生成されている可能性があります。その場合、統計的な冗長性はまったく利用できません。それでも、データは圧縮されます。なぜなら、短さはシンボルの頻度ではなく、それを生成するプロセスに宿っているからです。

したがって、この記事の本当の質問は次のとおりです。統計的冗長性は、圧縮可能性の唯一の種類なのでしょうか?そして、πはそうではないと主張しようとしています。

統計的な種類:エントロピー

予算からのエントロピーの構築

πの奇妙さについて語る前に、「統計的圧縮」が実際に何を測定するのかを確定する必要があります。その測定には名前があります:エントロピー。

非公式には、エントロピーはシンボルソースの平均的な驚きの量です。ソースが常に同じシンボルを発する場合、まったく驚きはありません。あなたはすでに次に何が来るかを知っているので、新しいシンボルは何も教えてくれません。エントロピーはゼロです。ソースが10種類の異なる数字を等しい確率で発行する場合、新しいシンボルは可能な限り驚くべきものであり、エントロピーは最大になります。ほとんどのソースは、その中間に位置します。一部のシンボルは一般的(驚きが少なく、情報が少ない)であり、一部はまれ(驚きが大きい、情報が多い)です。エントロピーは、それらがどれだけ頻繁に出現するかによって重み付けされた、それらすべてに対する平均です。

圧縮との関連は直接的です。驚きこそが、ビットを支払う必要があるものです。予測可能なものはすべて省略できます。受信者がそれを補うことができるからです。驚くべきものはすべて実際に送信する必要があります。したがって、シンボルあたりのビット数で測定されるソースのエントロピーは、達成できる最短の平均メッセージのサイズです。これは、どの可逆コードもそれ以下にはなれない下限です。

それが非公式な説明です。しかし、単に公式を述べて次に進むのではなく、それを実際に導出する方法があります。そして、私はクリス・オラーの素晴らしいビジュアル情報理論の精神を借りています。以下の図は、彼の議論の私のバージョンです。

セットアップを見てみましょう。できるだけ少ないビットでシンボルのストリームを送信したいと考えています。各シンボルにコードワード、つまり短いビット列を与えます。一般的なシンボルには短いコードワードを、まれなシンボルには長いコードワードを割り当てるべきです。それは直感であり、明らかに正しいです。本当の質問は、確率 pp のシンボルに対して、正確にどれだけ短いコードワードを与えるべきかということです。

ここに、それが本当の質問に変わる引っ掛けがあります。コードワードは競合します。ストリームを曖昧さなくデコードするには、どのコードワードも他のコードワードのプレフィックスであってはなりません。もし 0 がコードワードなら、他の何も 0 で始まってはなりません。したがって、短いコードワードを与えることは高価です。それは、利用可能なコードワード空間の大きな塊を消費します。正確には、長さ LL のコードワードは、その空間の 1/2L のスライスを消費します。1ビットのコードワードはすべてを半分燃やし、2ビットのコードワードは4分の1を燃やします。短いコードワードは希少なリソースであり、それらに費やすことは他のコードワードを長くすることを強制します。

固定予算として考えてください。各シンボルはコードワードを購入する必要があり、短いコードワードはより高価です。

では、固定予算をシンボル間でどのように配分しますか?自然な動き、そしてそれが最適な動きであることが判明したことは、各シンボルにその使用頻度に比例して費やすことです。確率 pp のシンボルに予算の pp サイズのスライスを与えます。サイズ pp のスライスは、コスト pp、つまり 1/2L = p を持つコードワードを購入します。これは、L = log₂ (1/p) を意味します。

そして、ここにあります。主張されたのではなく、導出されました。確率 pp のシンボルに対する理想的なコードワードの長さは log₂ (1/p) ビットです。したがって、一般的なシンボル(pp が 1 に近い)はゼロに近い長さを取得し、まれなシンボル(pp が非常に小さい)は長い長さを取得します。これは、私たちが始めた直感とまったく同じですが、今では数値が付いています。

そして、私が最も気に入っている部分です。平均メッセージ長を面積として見ることができます。各シンボルの確率を一方の軸に、コードワード長 log₂ (1/p) をもう一方の軸に配置します。これにより、各シンボルは面積 p・log₂ (1/p) の長方形になり、合計面積はシンボルあたりの平均ビット数になります。

H = ∑ᵢ pᵢ log₂ (1/pᵢ) = -∑ᵢ pᵢ log₂ pᵢ

これがシャノンエントロピーであり、最小の可能な面積です。つまり、どのコードもこの分布に対して達成できる最短の平均メッセージです。一般的なシンボルに長いコードワードを与えると、多くの面積が追加されます。予算ルールは、まさにその無駄を排除するものです。

[画像: 平均メッセージ長を面積として表示。各シンボルは長方形:幅はそのコードワード長、高さはその確率。不格好な固定長コード(左)は、最適な予算コード(右)よりも多くの面積を積み上げています。エントロピーは、どのコードも到達できる最小の面積です。]

(log₂ (1/p) の2番目の読み取り方があり、それは覚えておく価値があります。それは、pp の割合を占めるものを分離するために必要なイエス/ノー質問(二分割)の数です。まれなものには多くの二分割が必要で、一般的なものには少なくて済みます。同じ数、2つのレンズです。)

それをきれいなケースで感じてみましょう。確率が 1/2, 1/4, 1/8, 1/8 の4つのシンボルを考えます。公式は理想的な長さを 1, 2, 3, 3 ビットとして割り当てます。そして、実際にそれらのコードワードを構築できます:0, 10, 110, 111。プレフィックスの衝突はありません。平均長は (1/2)(1) + (1/4)(2) + (1/8)(3) + (1/8)(3) = 1.75 ビットです。これはまさに H です。最も一般的なシンボルは1ビットのコードワードを取得し、まれなシンボルは長さで支払いました。そして、予算は完璧にバランスが取れました。

そして、私たちのパズルが必要とする事実があります。エントロピーは、すべてが等しく可能性が高い場合に最大になります。10桁に対する均一分布は、log₂ 10 ≈ 3.32 ビット/桁で最大になります。なぜなら、安いコードワードを購入できる頻繁なシンボルがないからです。私たちの両方のファイルは均一なので、どちらも最大エントロピーを持っています。これは、統計的には、どちらも物事がなりうる限り圧縮不可能であることを意味します。

エントロピーの盲点

ここで注意したいのは、間違いやすい微妙な点があるからです。エントロピーは、実際にはソース、つまり特定の確率でシンボルを発行するプロセス、単一の固定シーケンスのプロパティです。厳密に言えば、「πのエントロピー」というものは存在しません。πは単一のシーケンスであり、単一のシーケンスには確率が付随していません。

では、私たちのファイルの1つの「エントロピーを測定する」ときに実際に何をしているのでしょうか?各数字がどれだけ頻繁に出現するかを数え、それらの頻度を、数字を独立に発行するソースから来たかのように扱い、そのソースのエントロピーを計算します。そして、まさにここに盲点が生じます。シーケンスをその頻度で要約した瞬間、その順序を捨ててしまいます。そのため、同じ数字の頻度を持つどのシーケンスも、私たちには同一に見えます。順序付けられたものもパターンレスなものも同様です。πとノイズファイルは同じ頻度を与えるため、この頻度ベースの推定値は、一方が単純なルールによって生成されているにもかかわらず、それらを等しくランダムと呼びます。

ルールはすべての統計にとって不可視ではありません。正しいソースを知っていれば、πのプロセスを記述でき、そのエントロピーは非常に小さくなるでしょう。ポイントはもっと狭いです。手元に単一のシーケンスがあり、その頻度以外には何もなくても、生成ルールは痕跡を残しません。必要なのは、ソースを必要としない、個々のオブジェクトに対して定義された尺度です。それがまさにコルモゴロフ複雑性です。

プロセスの種類:コルモゴロフ複雑性

ここにあります。そして、それは非常にシンプルです。

文字列のコルモゴロフ複雑性 K(x) は、それを生成する最短のプログラムの長さです。

平均でも、分布でもありません。1つの文字列、1つの最短プログラムです。

10億個のゼロからなる文字列の複雑性は非常に小さいです。なぜなら、「0を10億回出力せよ」は非常に短いプログラムだからです。長さ nn の真にランダムな文字列の複雑性は約 nn です。なぜなら、それ自身より短い説明はないため、「プログラム」は基本的に「全体を出力せよ」だからです。そしてπは?非常に小さいです。数百ビット程度です。なぜなら、小さなプログラムがその数字を永遠に生成するからです。

したがって、パズルは解決され、その解決策は、私たちが2つの異なる定規を持っていたということです。

  • シャノンエントロピーは統計的です。それはアンサンブル、つまりソース、分布、長期的視点に関するものであり、頻度のみを認識します。
  • コルモゴロフ複雑性は構造的です。それは1つのオブジェクトに関するものであり、ルール、構造、生成プロセスを認識します。

πは、2つの定規が可能な限り大声で意見が分かれるオブジェクトです:最大エントロピー、最小複雑性。統計学は「ランダム、圧縮不可能」と言い、コルモゴロフは「些細なこと、ここに5行のプログラムがあります」と言います。どちらも正しいです。なぜなら、それらは異なる質問に答えているからです。

[画像: 同じオブジェクト上の2つの定規:統計定規は平坦なヒストグラムを見て「ランダム」と言い、アルゴリズム定規は小さなジェネレーターを見て「些細」と言います。πは、それらが意見が分かれる場所です。]

しかし、2つの間には橋があります。真にランダムなソースの場合、その出力の期待コルモゴロフ複雑性は、小さな定数を除いてそのシャノンエントロピーに等しくなります。したがって、平均して、分布全体で、2つの定規は一致します。そして、統計学を、アンサンブルにのみ焦点を当てたときにアルゴリズム構造が落とす影と考えるのが好きです。2つは、生成ルールを隠す個々の特別なオブジェクトに対してのみ分離します。そしてπはその極端なケースです。しかし、ほとんどのオブジェクトは特別ではありません。そして、それが次のことです。なぜなら、それが実際に証明できる唯一のことだからです。

ほとんど何も圧縮できない

ここに、難しそうに聞こえるが実際には引き算である主張があります。

ほとんどすべての文字列は、それ自身の最短の説明です。ほとんどのものはまったく圧縮できません。

見てみましょう。長さ nn を固定して、質問します。ちょうど長さ nn の文字列はいくつありますか?位置ごとに2つの選択肢、nn 個の位置があるので、2ⁿ 個です。

次に質問します。長さ nn より短い説明、つまり長さ 0, 1, 2, ..., n-1 のプログラムはいくつありますか?それらを合計すると、

1 + 2 + 4 + ... + 2ⁿ⁻¹ = 2ⁿ - 1

となり、文字列の数より1つ少なくなります。

それが議論全体です。2ⁿ 個の文字列があり、2ⁿ - 1 個より短い説明しかありません。したがって、想像できる最も寛大な世界でさえ、すべての短い説明が使用され、それぞれが異なる文字列を指していると仮定しても、最大で 2ⁿ - 1 個をカバーできます。これは、少なくとも1つの長さ nn の文字列には、それ自身より短い説明がないことを意味します。

そして、同じ数え方をもう少し進めると、状況ははるかに悪くなります。たとえば、真の圧縮、つまり少なくとも cc ビット短い説明を望むとします。それより短い説明は約 2ⁿ⁻ᶜ しかありません。したがって、最大で2⁻ᶜ の割合の文字列だけが cc ビットで圧縮できます。10ビット節約したい場合、それを達成できるのは1000個に1つの文字列にすぎません。20ビット節約したい場合、それは100万分の1に低下します。したがって、深い圧縮はまれなだけでなく、要求するほど指数関数的にまれになります。

この議論の形状には、後で再び現れるので指摘しておきたいことがあります。私たちは、非圧縮可能な文字列がほとんどすべてであること、単一のものを名前を付けることなく証明しました。それは、ドアを数え、鍵を数え、鍵が足りないことを認識するようなものです。いくつかのドアはロックされたままでなければならないことを知っていますが、数え方ではどれがロックされているかはわかりません。なぜなら、私たちは実際にどのドアも開けなかったからです。

数え方の中に隠れている動きもあり、声に出して言う価値があります:プログラム自体も文字列である。これが、文字列の数とプログラムの数を並べて引き算できた唯一の理由です。それらは同じ種類のオブジェクトであり、同じビットで測定されます。この単純な事実が、投稿の残りの部分が依存しているものだと私は思います。それを保持してください。

もう1つ、この数え方で決まることがあります。私が最初にこの議論を理解したとき、賢く回避しようとしました。文字列自体を保存するのではなく、すべての文字列のリスト内のインデックスを保存するのはどうでしょうか?または、短いプログラムを書いて、シードから多くの文字列を生成し、シードだけを保存するのはどうでしょうか?すべてのスキームは同じように失敗し、理由は常に同じであることが判明しました。

ファミリーサイズ NN から特定のものを選択するには、NN 個のものを区別できる名前が必要であり、NN 個の可能性を区別する名前は約 log₂ N ビットのコストがかかります。

2ⁿ 個の文字列へのインデックスは、書き込むのに nn ビットかかる数値なので、節約はありません。2ᵏ 個の出力の1つを選択するシードは kk ビットかかるため、シードは単に名前が異なるインデックスにすぎません。すべてを列挙するのは、どの項目を意味したかを言う必要がある瞬間まで安価です。そして、それを言うには完全なアドレスが必要になります。選択は、削減不可能なコストです。そして、これがπが圧縮可能である理由を最も明確に見る方法だと思います。そのジェネレーターは正確に1つの出力を生成するため、選択するものはなく、シードを支払う必要もありません。ランダムな文字列は逆のケースです。2ⁿ 個の等しく可能性のある文字列があり、正確に1つを特定する必要があるため、完全な log₂ (2ⁿ) = n ビットを支払います。

これまでのすべては数え方だけで証明でき、しっかりした基盤です。しかし、これらの最短の説明を実際に見つけようとして数え方をやめた瞬間、地面が崩れます。

障害:計算できない

コルモゴロフ複雑性の定義はクリーンでシンプルですが、初めて出会ったときに本当に奇妙だと感じる障害があります。それは、実際に計算できないということです。文字列を受け取り、その複雑性を返すアルゴリズムはありません。

その理由は、私がゆっくりと説明する価値があると思う非対称性にあります。まず、あなたができることについて考えてみてください。短いプログラムを探しに行くことができます。もし長さ50のプログラムが見つかり、それがあなたの文字列を出力する場合、K(x) が50以下であることを証明したことになります。プログラムはそこにあり、実行すれば機能します。そして、さらに探し続けることができます。明日、さらに短いものを見つけるかもしれません。これは、複雑性の上限が常に下がる可能性があり、文字列が思ったより単純であることを常に発見できることを意味します。

次に、反対方向を考えてみましょう。K(x) が少なくとも50であると証明したい場合、つまり、50より短いどのプログラムもあなたの文字列を出力しないと証明したい場合です。これはもはや1つのプログラムに関する主張ではなく、すべての短いプログラムすべてに関する主張です。そして、それらのうちの1つを排除するためには、それを実行して何をするかを見る必要があります。しかし、それは10億ステップ実行してから突然あなたの文字列を出力するかもしれませんし、決して停止せずに無限に実行するかもしれません。どちらが起こるかを決して確信できません。したがって、1度に1つの候補さえもケースを閉じることができません。つまり、下限は密封されたままです。

上限は見つけられますが、下限は見つけられません。物事が以前より圧縮可能であることを常に学ぶことができますが、それが外見どおりに圧縮不可能であることを決して証明できません。

そして、これにはより鋭いバージョンがあります。KKは計算が難しいだけでなく、完全に計算不可能であり、おそらく日常的な形で既に知っているパラドックスから来ています。「12語未満で記述できない最小の数」というフレーズを考えてみてください。12語未満のフレーズは有限個しかないので、そのように特定できる数は有限個しかありません。つまり、いくつかの数は記述から逃れなければならないということです。そして、それらの中には、最小の数があるはずです。しかし、もう一度フレーズを見てください。それはわずか11語で、その数をちょうど名前付けました。したがって、その数は12語未満で記述できると同時に記述できないということになり、矛盾です。これはベリーのパラドックスであり、それが実際の定理にどのように変わるかを示します。KKを計算できるアルゴリズムがあると仮定しましょう。そうすれば、次のような短いプログラムを書くことができます。「文字列を順番に調べ、その複雑性が10億を超える最初の文字列を出力せよ」。そのプログラムは短いです。数千ビットで十分です。それにもかかわらず、それが生成する文字列は、それを生成するために10億ビット以上必要であるとちょうど証明された文字列です。したがって、その文字列は、数千ビットの説明(プログラム自体)と10億ビットの複雑性を同時に持っていることになります。それはありえません。私たちが仮定したのは、KKが計算可能であることだけです。したがって、その仮定が間違っているに違いありません。

この議論では、プログラムを実行してそれが停止するかどうかを待つことは一度もなかったことに注意してください。それは純粋な自己参照です。もし複雑性を測定できれば、複雑なものを名前付ける短いプログラムを書くことができ、それはすでに矛盾です。自己参照こそがすべてを機能させるものであり、自己参照はプログラム自体が文字列であり、他のプログラムが読み取り、検索し、実行できるものであるためのみ可能です。これは、数え上げの議論で頼ったのと同じ事実です。プログラムは文字列であり、静かに再び作業を行っています。

これが本当に何だったのか

すべての下には、単一の区別があると私は思います。そして、それがこの記事の本当の主題です。それは2種類のステートメントの間の違いです。

  • 「NN個のものがあります。」 これはセットのサイズに関するステートメントです。それはそれらを区別しません。そして、区別しないというまさにその理由から、それは安価です。ほとんど情報を持っていません。
  • 「これはKK番目のものです。」 これは1つを singled out するステートメントであり、NN個の可能性の中からそうするには約 log₂ N ビットのコストがかかります。他のすべてから1つを区別する完全な価格です。

私たちが実行したほとんどすべてが、そのギャップです。「ほとんどの文字列は圧縮不可能である」は数え上げです。安価で、数え方だけで証明できます。「この文字列は圧縮不可能である」は点呼です。そして、その点呼こそ、決してできなかったものなのです。それは、短いプログラムが存在する場合にそれを見つけることができるという形で、もう一度現れました。なぜなら、それは単一の証人であり、有限時間で到達するからです。しかし、それより短いすべてを排除することはできません。なぜなら、それは無限のセット全体に一度に主張するからです。1つを見つけることは有限です。すべてを解決することはそうではありません。

そして、それはエントロピーにループバックします。情報とは、本当に何でしょうか?それは、物事を区別するコストです。

selection cost = log₂(tell your target apart from) の数

エントロピーはそのコストの平均を分布全体で見たものであり、コルモゴロフ複雑性は単一のオブジェクトに対する同じコストです。したがって、どちらも本当に同じことを尋ねています。どれか1つ、いくつの中からか。圧縮とは、選択する必要がないすべてです。πはほとんど何も圧縮されません。なぜなら、その小さなジェネレーターが実行されると、指し示すものがなくなるからです。支払うべき選択肢はありません。ランダムな文字列は何も圧縮されません。なぜなら、すべてのビットを指し示す必要があるからです。統計的圧縮と構造的圧縮の両方とも、同じ価格を持つことが判明しました。区別の価格です。そして、最も安価なステートメントは、何も区別しないステートメントです。NN個のものがあります。

次に進むこと

私は意図的にここで停止します。なぜなら、この記事は本当に1つの質問、つまりπを圧縮できるのに、その統計的な双子を圧縮できないのはなぜか、ということに関するものだったからです。そして、私はそれが1つのことをうまくやることを望みます。しかし、同じ数え方は続いており、私がそれを進めたいいくつかの場所があります。

圧縮が学習になるとき。 ここでのすべては可逆でしたが、同じ考えの非可逆バージョンがあります。あなたのデータに近似的に似ているが、構造を保持しノイズを捨てるもののための最短プログラム。そして、それは多かれ少なかれ学習が何であるかであることが判明します。オッカムの剃刀はスローガンではなくなり、算術になります。最良の説明は、まだ適合する最短のプログラムです。

証明さえできないとき。 数え上げの議論は、ほとんどすべての文字列が非圧縮可能であると述べていますが、単一の具体的なものを決して与えてくれません。そして、それは巧妙なアイデアで閉じることができる一時的なギャップではないことが判明します。これがコンピューターに関するものではなく、証明自体の限界に関するものになる点があります。形式システムが、どんなに真実であっても、特定の文字列が複雑であると証明できない点です。それはゲーデルにまっすぐつながっており、それ自身の投稿に値します。

有限宇宙。 物理的なものを名前を付けることしかできず、宇宙が有限個の区別可能な状態しか保持しない場合、これらすべてが有限になります。選択コストは、実際の物理的な数の log₂ の log₂ になり、圧縮の物語全体が熱力学第二法則の物語のように見え始めます。まれな圧縮可能な状態から圧倒的な非圧縮可能な多数派へとすべてが漂流します。これは、熱力学第二法則が単なる数え上げの議論であり、時間とともに展開されているにすぎないと言う奇妙な方法です。

しかし、それらはそれ自身の投稿です。この記事は単一の質問に関するものであり、それが導いた驚くべき場所に関するものでした。πが圧縮可能であることは、単にプログラムを渡すことでいつでもわかります。しかし、そのランダムに見える双子については、それができないことを決して確信できません。短い説明が存在する場合はそれを見つけることができ、存在しないことを証明することは決してできません。