バグの理論に向けて:予期せぬもののルーリロジー
Towards a Theory of Bugs: The Ruliology of the Unexpected (writings.stephenwolfram.com)
要約
この記事は、スティーブン・ウルフラムが提唱する「ルーリロジー」という概念を用いて、ソフトウェアにおけるバグの発生メカニズムを理論的に探求する試みです。彼は、計算プロセスにおける予期せぬ振る舞いを理解することで、バグの根本原因を解明し、より堅牢なシステムを構築する道筋を示唆しています。
全文翻訳
バグの理論に向けて:予期せぬもののルーリロジー
[画像: Towards a Theory of Bugs: The Ruliology of the Unexpected]
「私のプログラムがおかしなことをした!」
バグはソフトウェアの世界に遍在する現象です。そして、定義上、それぞれのバグは、何らかの形でユニークで予期せぬものです。しかし、その遍在性を考えると、それらに関する一般的な「科学的」理論が存在するのではないかと疑問に思うかもしれません。ここではその問いを探求することを目標とします。そして、計算の不可約性(computational irreducibility)や計算の可約性(computational reducibility)といった概念を用いて、バグ(および「正しいプログラム」)について考えるための基礎的な方法があることを見出すでしょう。
ここで議論する内容は、計算の有効性とバグの発生しやすさとの間の根本的なトレードオフ、バグ検出のための戦略、そしてテストの難しさについての期待感を与えてくれます。その過程で、ソフトウェア検証やコンピュータセキュリティ、さらにはAIシステムによって生成されるコードに関連する根本的な問題点を明らかにすることができます。
ある意味で、ここで行うことの鍵は、バグという根本的な現象が、非常に単純なプログラムでさえ既に発生していることを認識することです。そしてそれは、ルーリロジー(ruliology)の方法論と直感をバグに関する基礎的な問題の研究に利用できることを意味します。
プログラムを書くとき、私たちは通常、プログラムに何をしてほしいかを知っています。そして、それが予期せずそうしなかった場合、私たちはそれをバグとみなします。より抽象的な言葉で言えば、私たちは通常、プログラムが何をすべきかの表現を心の中に持っています。そして、それが私たちの心に収まるためには、計算上非常に単純である必要があります。しかし、問題は、実際にプログラムを実行することに関連する計算プロセスが、何らかの形で対応して単純であるかどうかということです。もしそうであれば、私たちが持つ表現に厳密に従うことが可能です。
しかし、私の計算の等価性の原理(Principle of Computational Equivalence)によって捉えられる大きな驚きは、構造が非常に単純なプログラム(またはその断片)でさえ、ある意味で可能な限り洗練された計算を行うことができるということです。そしてその結果、そのようなプログラムは計算の不可約性を示す可能性があり、それは、私たちが予期せず、そして予見できないことを必然的に行うことができ、それをバグとみなすことになることを意味します。
人間が単独ではそれができないとしても、AIなどを搭載した自動システムでそのようなバグを根絶できると期待できるでしょうか? 議論するように、進歩が期待できる「計算の可約性のポケット」は必然的に存在します。しかし、鍵となるのは「計算の不可約性が端に潜んでいる」ということです。そして、計算の不可約性が存在する場合、計算を明示的に実行すること以外に、何が起こるかを決定する方法はありません。そしてそれは、特定のケースでプログラムを既に実行していない限り、その動作を確実に知ることはできないことを意味します。そして、それが望ましくないことを行った場合、私たちはそれを「バグ」と呼ぶでしょう。
チューリングマシンにおけるバグ
探求を始めるにあたり、計算の非常に単純で長年のモデルであるチューリングマシンを見ていきます。ルールを持つ(3状態、2色)チューリングマシンを考えます。
[画像]
チューリングマシンのテープに整数 n のバイナリ表現を初期状態として配置し、マシンを実行し、ヘッドが開始位置よりも右に進んだときにテープ上にある数値を調べると想像してください。
[画像]
これらの例を見ると、チューリングマシンが関数 n [画像] n + 1 を計算していると結論付けるでしょう。しかし、より大きな入力で試してみましょう。
[画像]
そして、入力7ではバグが発生します! 7 + 1 = 8 を出力する代わりに、チューリングマシンは9を出力します。
チューリングマシンが計算する値をプロットすると、小さなグリッチの連続が見られます。
[画像]
グリッチは、n が 8k – 1 の形式の値で現れることが判明します(その大きさは Floor[2^(IntegerExponent[k + 1, 2] + 3)/7])となります。チューリングマシンの実際の詳細な動作を見ると、これらのケースで「バグを引き起こす」原因がわかります。「正しく動作する」n の値では、ヘッドは左にスイープし、必要に応じてキャリービットを伝播させ、右にスイープするときはテープ上の構成にそれ以上の変更を加えません。しかし、n が末尾が111のバイナリ表現を持つ数(つまり、7 modulo 8 に等しい 8k – 1 の形式の数)である場合、ヘッドが右にスイープするときに「小さな追加のジグ」を行い、「間違った数字を」テープに書き込みます。
[画像]
n + 1 を計算する「正しい」チューリングマシンはたくさんあります。実際、3状態と2色では8934台あり、ほとんどがかなり単純な方法で動作しますが、
[画像]
一部は最初はほとんど不条理なほど複雑な方法で動作しますが(しかし最終的には右側の圧縮されたレンダリングに示すように、それらは単にネストされています)、
[画像]
しかし、このようなチューリングマシンに「バグがある」場合、それが現れるまでどれくらい進む必要があるでしょうか? ここに、ある値 n まで n + 1 を「正しく計算する」3状態、2色マシンの数がプロットされています。
[画像]
そしてここに「最初のバグ」が発生する場所の概要があります。
[画像]
「最も悪質な」バグは n = 15 まで発生しません。そのようなバグを持つマシンの例は次のとおりです。
[画像]
この場合の数値のシーケンスは次のとおりです。
[画像]
そして、0から14までの入力でこのマシンを実行すると、すべて問題なく動作しますが、n = 15 で突然、15 + 1 = 16 の代わりにマシンは20を生成します!(グリッチは 16k – 1 の形式のすべての入力、つまりバイナリ表現の末尾に1111を持つケースで続きます)。
より大きなチューリングマシンについてはどうでしょうか? 約40億台の4状態チューリングマシンのうち、900万台以上が n + 1 を正常に計算します。しかし、非常に悪質なバグを持つものもあります。例として、標準的なWolfram Language TuringMachineナンバリングスキームで118050142というマシンは、n = 62 までのすべての値で n + 1 を「正しく」計算しますが、
[画像]
その後、突然 n = 63 で64ではなく72を生成します。
[画像]
すべての4状態チューリングマシンを見ると、「n + 1 にほぼ」計算するマシンでバグが発生する場所をまとめることができます。
[画像]
ここに注目すべき特徴は、バグの「最もリスクの高い」n の値は 2i – 1 の形式、つまり n のバイナリ表現がすべて1で構成されているケースであるということです。また、少なくとも s = 2、3、4状態では、「最も悪質な」バグが常に n = 2^(s – 1) – 1 で発生し、すべてのマシンの中で非常にまれであることも注目に値します。
バグとは何か?
プログラムにバグがあるかどうかを判断するには、プログラムが何をすべきか、または何をすべきでないかを知る必要があります。そしてそのためには、何らかの正確な仕様が必要です。もちろん、プログラム自体が何をするかの仕様を提供します。そして、この仕様に関して、プログラムは常に「自分がすることをする」だけで、「バグを持つ」可能性はありません。しかし、通常、私たちはプログラム自体だけでなく、より吸収しやすい形式(たとえば、前のセクションの単純な数式「n + 1」)の仕様を想像します。そして、このような仕様に対してプログラムはバグを持つことができます。
実際にはいくつかの異なる種類の仕様が使用されています。最も直接的なものは、プログラムを別の、通常はより高レベルの言語(たとえば、Wolfram Language 対 C++、または数学表記 対チューリングマシンルール)で言い換えるだけです。これのより最小限のバージョンは、プログラムを同じタイプの別のプログラムとして言い換えるだけです。次に、2つのプログラムが同じことをしない場合にバグとみなします。(たとえば、コンパイラの最適化がプログラムの動作を変更した場合、それはバグです)。
この例を見るために、再びチューリングマシンを見てみましょう。ここでは、同じ関数を計算しているように見える2つのマシンを示します。
[画像]
しかし、突然、n = 27 で、異なることを行います。
[画像]
そして実際、このケースで「バグ」(つまり、出力の違い)が発生するパターンの複雑さは驚くほどです。
[画像]
仕様のもう1つの一般的なタイプは、プログラムが何をすべきかではなく、何をすべきでないかを述べるものです。たとえば、チューリングマシンでは、それらが「制御不能」になり、無制限のメモリ(つまりテープ)を使用し始めることを決して望まないことを指定できます。ここでは、幸せに計算出力を生成しているように見えるチューリングマシンの例を示します。
[画像]
しかし、突然、n = 42 で、「バグ」が発生します。
[画像]
そして、パターンが無限に広がり続けます。
[画像]
ここでは別のマシンを示します。これも幸せに計算出力を生成しているように見えます。
[画像]
しかし、n = 151 で、何か病的なことが起こり、マシンは無限ループに入ります。
[画像]
また、チューリングマシンの出力が常に、たとえば偶数であるべきという仕様を持つこともできます。そして、ここでは偶数の出力を生成しているように見えるチューリングマシンを示します。
[画像]
しかし、n = 32 で、突然9を生成します。
[画像]
そして、常に同じ話のようです。仕様を設定し、いくつかのチューリングマシンはそれを正確に順守します。しかし、私たちは常に、少なくとも「バグ」が発生するまで、それを順守しているように見えるものを見つけるようです。つまり、どのような制約を与えても、マシンが巧妙にそれを回避する、つまり「悪質なバグを持つ」ことになるようです。
セルオートマトンの例
単純なチューリングマシンにおける「バグ」について見てきたことはどのように一般化されるでしょうか? 別の例として、セルオートマトンを見てみましょう。特に、「入力を倍増する」ように設定されたセルオートマトン、つまり n 個の(非白)セルブロックから開始して、2n 個の(非白)セルを生成するものを考えます。
[画像]
上記のチューリングマシンの例と同様に、タスクを実行するための多くの方法があります(たとえば、k = 3色の場合)。効率が良いものもあれば、そうでないものもあります。
[画像]
特定のルールがタスクを実行するように見えることがありますが、突然「バグ」が発生します。たとえば、n = 14 の場合です。
[画像]
チューリングマシンの例と同様に、「バグ」が現れるまで時間がかかることがあります。
[画像]
ここでは、最初の「バグ」が n = 24 で現れる例を示します。
[画像]
そしてここでは32で、
[画像]
バグが発生するかどうかを判断できるか?
上記で見た多くのセルオートマトンは、パターンが単純であるため、「視覚的に明白」に「すべての入力サイズで正しく倍増する」ことがわかります。
[画像]
時にはそれほど明白ではありませんが、それでも何かが特定の封筒から逃れることはできないように見え、したがってバグは存在しないと考えられます。
[画像]
しかし、このケースはどうでしょうか。
[画像]
これは、最終的にバグを示す上記の場合と非常に似ています。しかし、n = 100000 まで実行しても、バグは現れません。より分析的に、n の関数としてパターンが安定するまでのステップ数をプロットできます。
[画像]
全体的な傾向は単純で、入力 n に対して 7.16n ステップでよくフィットします。しかし、ランダムに見える変動があります。
[画像]
これらの変動は、少なくとも[画像]のように成長するように見えます。しかし、バグにつながることを確実にするための明確な方法はありません。
このケースはどうでしょうか。
[画像]
パターンは常に「含まれる」のでしょうか、それとも最終的にバグにつながる「漏れ」が発生するのでしょうか? ここでも安定化時間をプロットでき、再びほぼ線形に増加するように見え、現在は 9n でよくフィットします。
[画像]
しかし、ランダムに見える変動があります。
[画像]
そして、これらの変動がいつか「野生化」してバグにつながるかどうかという問題が再び生じます。
さて、このケースでは、これが決して起こらないという議論を提供できます。安定化時間のようなものを単に見ているだけでは、これを理解するのは非常に困難です。しかし、計算のプロセス全体を見ると、セルオートマトンでは容易にできるため、物事がより明確になります。
小さな例を見ると、2つの重要な特徴が見られます。第一に、白い「縁」は常に同じ場所に留まるか、左に移動します。第二に、縁の内側では、パターンは[画像]と[画像]のみを含みます。
[画像]
縁の挙動(基盤となるセルオートマトンルールから容易に決定できる)は、複雑なパターンが決して拡大しないことを保証します。しかし、たとえば、パターンが周期的になり、全体のパターンが決して安定しなくなる可能性はあるでしょうか? さて、それは縁の内側の「実効ルール」に依存します。そして、基盤となるセルオートマトンルール
[画像]
から[画像]を含むすべてのケースを削除することで、その実効ルールを確認できます。
[画像]
答えは、それがまさにルール122の初等セルオートマトンであり、[画像]が[画像]を表し、[画像]が[画像]を表すということです。ルール122は、ペアの同一セルが隣接する場合、ルール90をエミュレートし、単純なネストされたパターンを生成するという特徴があります。
[画像]
元のセルオートマトンにも、そのパターンの類似体が現れます。
[画像]
しかし、ある時点でパターンは「右から中断」され、その後、「縁」がそれを侵食し続けます。パターンが周期的になる唯一の方法は、縁が左に移動するのをやめることであり、それが起こる唯一の方法は、縁内のパターンが「すべて[画像]」(または実効ルール122では「すべて[画像]」)になることです。したがって、これはルール122パターンが単純に消滅する(そしてすべて[画像]になる)かどうかという問題に還元されます。しかし、ルールの構造自体から、これが不可能であることがわかります。[画像]セルが一度でも現れると、それ以降のすべてのステップで[画像]セルが存在しなければなりません。
したがって、このケースのパターンは複雑に見えますが、最終的に常に安定し、基盤となるセルオートマトンは常に「入力を倍増する」ことをバグなしで確実に実行しなければなりません。
セルオートマトンの挙動が「視覚的に単純」であれば、バグを示さないことをすぐに判断できます。そして、視覚的に複雑であれば、バグが存在する可能性があると懸念するかもしれません。しかし、それでも、その複雑さにもかかわらず、私たちが懸念している挙動の特徴(ここでは、任意の入力の成功した倍増)が、バグなしで常に確実に発生するケースがあります。
しかし、形式的証明についてはどうでしょうか?
上記で議論したチューリングマシンに戻りましょう。ルールを持つマシンを考えます。
[画像]
このマシンを n のシーケンスで実行すると、常に n + 1 を計算しているように見えます。
[画像]
そして実際、このマシンの実際の挙動を見ると、それが常に n + 1 を計算しなければならないことを理解するのはそれほど難しくありません。しかし、形式的に証明できるでしょうか?
証明を簡略化するために、チューリングマシンの挙動とそれについて述べたいステートメントの両方を包含できる表記法が必要です。そして、それを取得するための基本的な方法は、すべてをシンボリックな式(はい、Wolfram Language のように)で表現することです。チューリングマシンのテープを連結リストとして表現すると便利です。 successive cells are tied together by a (right-associative) binary operator (here ·), and with its “ends” indicated by markers (here ⊲ and ⊳):
[画像]
これを実質的に実行長エンコードすると便利です。
[画像]
ヘッドの位置は、それが置かれているセルの直後に「連結リスト」の一部として与えることで示します。
[画像]
チューリングマシンの進化の例は次のようになります([画像]は停止状態に相当するものを示します)。
[画像]
このチューリングマシンの進化のこの特定の例は、ある意味で次を示すものと考えることができます。
[画像]
または
[画像]
そしてこの設定で、チューリングマシンが入力 n を与えられたときに常に n + 1 を計算することを示すために、私たちは「代数のような」公理の形でマシンのルールを指定できます(ここで s は任意の「サブテープ」を表し、[画像]は[画像]または[画像]のいずれかであるテープ上のセルを表します)。
[画像]
また、ヘッドが右端に到達したとき(そしてマシンが停止したとき)に何が起こるかを述べる公理も必要です。
[画像]
次に、実行長エンコーディングがどのように機能するかを定義する公理が必要です。
[画像]
さて、この設定で、マシンが入力 n を与えられたときに常に n + 1 を計算することを示すために証明する必要があるものは何でしょうか? 2つのケースについて話すのが最も簡単です。第一に、n のバイナリ数字が0で終わる場合、マシンは最終的にその0を1に置き換える必要があります。第二に、n のバイナリ数字が m 個の1のシーケンス(上記で[画像]m と示される)で終わる場合、マシンはこのシーケンスを[画像]・[画像]m に置き換える必要があります。しかし、実際にはこれらの2つのケースは1つにマージでき、証明する必要がある最終的なステートメントは(m ≥ 0 の場合)次のようになります。
[画像]
これを証明するために、公理から、有効なシンボリック変換のみを使用して生成する方法を見つける必要があります。そして、実質的にWolfram LanguageのFindEquationalProofを使用してこれを行うことができます。
[画像]
ここでは、元の公理は緑で示されています。それらから導出された定理は青で示されています。証明したい最終定理は、下部にある「出力」として取得されます。証明のほとんどで、私たちは2つの定理を構造的に組み合わせることで別の定理を導出しています(代入[画像]またはビスブスティテューション[画像]のいずれかによって)。しかし、追加の不可欠な部分が1つあります。最後の[画像]は数学的帰納法の適用を示しています。帰納法の入力は、「ベースケース」定理(左側に示されている)であり、それに加えて主張[画像]と、右側の証明から証明された定理[画像]です。数学的帰納法(一般的な公理と見なすことができます)は、[画像]が[画像]を意味し、[画像]を示した場合、すべての整数 m に対して[画像]が成り立つと述べています。
したがって、これは、チューリングマシンの操作の公理から開始して、すべての入力 n に対してマシンが n + 1 を正しく計算し、バグがないことを証明できたことを意味します。すべてをシンボリックに表現することを使用することで、すべての n に適用される有限のシンボリック証明に、すべての n に関する実質的に無限のステートメントのコレクションを削減することができました。
2状態チューリングマシンの中には、n + 1 を正しく計算するものが17台あり、3つのクラスに分類されます。私たちが今研究したマシン(マシン453)は、これらのクラスの1つの例です。そして、上記で概説した方法を使用して、これらのすべてのクラス(マシン453、445、1512によって例示される)の証明を生成できます。
[画像]
したがって、はい、これらのすべてのマシンが n + 1 をバグなしで正しく計算することを正式に証明できます。ここでの証明はそれほど複雑ではありませんが、結局のところ、これらの特定のマシンは操作が非常に単純です。そして、バグのない3状態マシンでさえ、証明はまだかなり管理可能です。しかし、さらに進もうとすると、後で議論するように、必然的に無限に長い証明に遭遇することになります。(ちなみに、上記で議論したセルオートマトンプログラムの証明を作成しようとすると、視覚的に明白でない場合は常にこのようになります)。
ここで示している証明は、FindEquationalProof によって見つけられた 特定の証明にすぎないことに言及する価値があります。それらはユニークではなく、可能な限り単純ではないかもしれません。しかし、それらはチューリングマシンで可能なシンボリック証明の種類をよく示しています。
では、バグのあるマシンで証明を作成しようとするとどうなるでしょうか? それを見るためには、上記のような証明をどのように構築するかを話す必要があります。基本的な考え方は、公理から始めて、定理に到達する方法を見つけることです。実質的に、私たちは可能な定理のマルチウェイグラフを形成しています。そして、私たちの証明は、このグラフ内のパスのようなサブグラフに相当します。
マルチウェイグラフは次のように始まります。上部には元の公理があります。
[画像]
そして、さらに数ステップ進めると(そしてグラフを視覚的に再配置すると)、このマルチウェイグラフから上記のケースの証明を正確に「引き出す」ことができます。
[画像]
さて、バグのあるマシンについてはどうでしょうか?たとえば、最初に使った例です。このマシンのマルチウェイグラフの開始部分は、前のものと似ています。
[画像]
しかし今、どれだけ進んでも、証明は見つかりません。
[画像]
なぜなら、実際には証明しようとしている結果は真実ではなく、証明が存在しないからです。そして、チューリングマシンの十分な数のケースをテストすると、バグを明示的に見つけることができるため、これはわかっています。
そして結局、証明を作成しようとしても、チューリングマシンを実行するよりも根本的な利点はありません。どちらの場合も、潜在的に無限の計算労力を費やす必要があります。それは、その労力をチューリングマシンのケースを列挙して実行することに直接費やすか、それともマルチウェイグラフを構築して証明を見つけることに費やすかの選択にすぎません。
これまでの証明のスタイルは、等式論理に基づき、提供された公理から目的の定理を構造的代入(および帰納法)によって構築することに基づいていると考えることができます。別の方法は、型理論を使用することです(Leanのような証明支援ツールが行うように)。そして、型の表現を構築し、それを持つ何かの例を与えることによって、その型が可能であることを証明します。ここでは、証明したい型が「存在する」ということは、基本的にすべての n に対して私たちのチューリングマシンが n + 1 を計算するという定理のステートメントです。証明支援ツールを呼び出してステップを検証できるLLMを使用すると、最終的に証明を生成できます。それはあまり啓発的ではありませんが、証明の視覚的な表現を与えることができます。
[画像]
計算の不可約性とバグ
これまでに、私たちが「バグ」と考えることができるいくつかの最小限の例を見てきました。非常に単純なプログラムでさえ行う可能性のある予期せぬことです。しかし、これらの「予期せぬこと」の根本的な源は何でしょうか?
最終的には計算の不可約性であり、実質的にそれを実行しない限り、プログラムが何をするかを知ることができないことです。そして重要なのは、計算の不可約性は原理的に可能なことだけでなく、計算の等価性の原理によれば、それは遍在しており、明らかに単純ではない本質的にあらゆるシステムに影響を与えるということです。
計算の不可約性が存在する場合、システムの挙動は一般的に、還元不可能な量の計算作業によってのみ予測できることを意味します。したがって、有限の計算作業で、システムが私たちを驚かせ、特にシステムが予期せずバグとみなすものを発生させる可能性があります。
システムにバグがあるかどうかは、あるレベルでは無限の質問です。一般的に、無限の可能な入力すべてからの出力をチェックする必要があるかもしれません。そして、特定のケースでシステムが停止して出力するかどうかさえわからないかもしれません。そして実際、計算システムに関するこれらの無限の質問は、原理的に決定不能である可能性があることが1世紀前から知られています。しかし、問題は、これが単に原理的な問題ではなく、実践的な問題であり、非常に単純なプログラムの幅広い範囲に影響を与えるということです。
しかし、問題があるプログラムを使わないのはなぜでしょうか? 挙動を予測でき、バグがないことを確信できるプログラムです。さて、問題は次のとおりです。プログラムが何をするかを完全に予測できる場合、それを実行する意味は何でしょうか? プログラムを実行せずに、実質的にすぐに「答えを書き留める」ことはできませんか? 言い換えれば、プログラムを実行する価値があるためには、その挙動の一部で予測できない部分がなければなりません。そして、計算の等価性の原理から得られる直感があります。予測できないものが1つでもあれば、予測できないものがたくさんある傾向があります。つまり、システムは計算の不可約性に満ちている傾向があります。
ある意味で、計算の不可約性は計算を強力にしています。しかし、それはまた、それを予測不可能にもしています。そして実際には、意図的かどうかにかかわらず、プログラムには「内部に計算の不可約性の火花」があり、それが何とか制御されて望むことを行うということが非常に一般的です。
プログラムがワイルドなことをしても構わないかもしれません。少なくともあるプロパティ(無限ループに入らないなど)を満たす限り。特定のプロパティを満たしてほしいかもしれません。計算の不可約性の重要な特徴は、それが存在する場所には、計算の可約性のポケットも必ず存在することです。つまり、計算の不可約性がシステムのすべてを予測できないと言っても、システムについて予測できることは常にあります。そして、それらのうちのいくつかが望むプロパティと一致する場合、システムは、少なくともこれらのプロパティに関して、「バグを示さない」ことを知ることができるかもしれません。
上記でいくつかの単純なチューリングマシンの例で見たように、シンボリック証明を構築して、特定のプログラムが特定のことを行い、したがって特定の種類のバグを持たないようにすることができます。これは計算の不可約性とどのように関係するでしょうか? 証明は、計算の可約性のポケットを利用して、無限のものの有限の要約を提供すると考えることができます。しかし、計算の不可約なシステムが行うすべてのことの(静的な)有限の要約は提供できません。そして、計算の不可約なプロセスに関する証明は、プロセス内のステップをより多く話そうとするにつれて、必然的に長くなります。
混乱する状況になる可能性があります。プログラムを研究し、その操作に関するあらゆる種類の事実を発見します(「これは決してそれをしない」、「これは一定のままである」など)。そして、十分な事実があれば、バグがないことを保証できると思うかもしれません。しかし、計算の不可約性がある場合、実際にはそれを行うには無限の事実が必要になります。そして実際には、あなたが焦点を当てている特定のプロパティが、確立された事実によって「バグがないことが保証される」かどうかは、場合によるかもしれません。
十分なケースをテストしましたか? ルーリロジー的帰納法の失敗
科学的帰納法は自然科学の礎です。世界で何かが十分に何度も起こるのを見ると、それが常にそう起こると仮定します(そしてそれに関する「科学法則」があると)。しかし、ルーリロジーではどうでしょうか? 科学的帰納法を適用できますか? チューリングマシンをたくさんテストします。特定の行動パターンを観察します。そのパターンは常に存在しますか? 科学的帰納法は「はい」と言うでしょう。しかし、「バグ」がある場合、それはそうではありません。そして、ルーリロジーでは、計算の不可約性のおかげで、常に驚きや、私たちが推測したどんな法則にも違反する「バグ」の可能性があります。
特に、現在わかっていることから、根底にあるものが非常に計算的であるように見えることを考えると、科学的帰納法がそもそも機能した理由を疑問に思うかもしれません。答えは、自然科学と科学法則の根本的な性質に関係しています。あるレベルでは、科学がやろうとしていることは、世界で起こっていることを取り、少なくともその側面の一部を、私たちの心が把握できる「物語」で説明することです。そして、そのような物語は、定義上、計算の可約性のポケットに依存しています。根底にあるものには、あらゆる種類の計算の不可約性が含まれる可能性があります。しかし、それは私たちが「科学を行う」ときに集中することではありません。私たちは、科学法則や物語で「要約」できる計算的に可約な規則性を見つけます。
現実的には、これは場所によってうまくいく場合とそうでない場合があります。物理学は大きな成功例です。生物学はそうではありません。私たちの物理学プロジェクトでは、多くの計算の不可約性があることがわかります。それは、私たちのような観察者に関連する物理法則が、それを大部分回避しているだけです。生物学では、再び計算の不可約性があります。実際、生命がそのように行動できるためには、それが不可欠であるように思われます。そして今、「内部を見る」ために、たとえば医学を行う場合、私たちは計算の不可約性に直面せざるを得ません。これは、実験における再現性の遍在的な失敗として現れ、実質的に科学的帰納法の失敗となります。(確率を不確実性ではなく確率として話すことで科学的帰納法を救おうとすることができますが、最終的には常に計算の不可約性に直面しなければなりません)。
しかし、プログラムについてはどうでしょうか? さて、プログラムの詳細が重要である限り、計算の不可約性に遭遇する可能性があります。そして、上記で議論したように、私たちが調べているものが可約性のポケットにすぎず、「行動の全スペクトル」を見ていない場合にのみ、それを回避できます。
さて、プログラムをテストするために多くの具体的なケースを見ているとしましょう。私たちは「可約性のポケットに閉じ込められている」のか、それとも実際に「行動の全スペクトル」を見ているのかを知るにはどうすればよいでしょうか? 実践における典型的なアプローチは、可能な入力のランダムなサンプルを取ること(または既知の入力の周りにランダムな「ファズ」を導入すること)です。これは機能するでしょうか? さて、それは「ランダム性」がどれほど「良い」か、そしてバグの分布と密度に依存します。
たとえば、私たちの「ランダム性」が数値アルゴリズムから来た場合、 successive numbers の特定の種類のシーケンスしか発生しない可能性があります。テストしているプログラムは、これらのケースでは「バグ」を示さないかもしれませんが、他のケースでは示すかもしれません。そして一般的に、ランダム性とプログラムの間には一種の競争があります。プログラムはランダム性を「デコード」するのに「十分に計算的に強い」のでしょうか、それともそれらのケースで特別なことを行うのでしょうか? それとも、ランダム性はプログラムの挙動を、少なくとも体系的に「バグ」を回避しないようにサンプリングするのでしょうか?
もちろん、サンプリングが「体系的にバグを回避しない」としても、バグが「特別なコーナー」にしか存在しないため、それらにヒットしないだけかもしれません。しかし、ランダム性が「十分に計算的に強い」場合、それから「隠れる」「特別なコーナー」は存在しません。
それでも、存在するバグの密度を考えると、サンプルの数がバグにヒットするには十分でない可能性があります。(ある程度の均一性と独立性を仮定すると、より多くのサンプルを採取した場合にバグにヒットする確率がどのように増加するかを計算するために単純な確率的引数を使用できます)。
では、バグの密度はどのくらいになると予想されますか? さて、まれでない限り、それを「バグ」と呼ぶことはないでしょう。しかし、プログラムの世界では、どれほどまれなことがあり得るでしょうか? 答えは、想像できる限りまれであるということです。それは、特定のクラスのプログラムの最も長い有限寿命が何であるかという「ビジービーバー」問題に非常に似ています。その場合、無限なのは有限寿命です。ここでは、「バグ」の確率の小ささです。(「最も見つけにくいバグ」を持つチューリングマシンを、気まぐれなイタチマシンと呼ぶかもしれません)。
しかし、実際にはどうなるでしょうか? さて、少なくともルーリロジーを行う上で、私の首尾一貫した経験は、まれな現象が常に現れるということです。ある種のシステムの多くのインスタンスをサンプリングし、一貫した挙動を見ることは非常に一般的です。そして、その挙動が常に発生しなければならないと結論付けるために科学的帰納法を使用する傾向がかなりあります。しかし、非常に規則的に、より多くのサンプルを採取し、特に網羅的にサンプリングすると、驚きがあります。時には数千、数万、数百万、数兆のケースを見る必要があります。しかし、その後、予期せぬものを見ます。それは、システムがどのように振る舞うと考えられていたかと比較して、「バグ」と考えることができるものです。
いくつかの典型的なルーリロジー的驚き
計算宇宙は驚きに満ちています。そして、ルーリロジーでそれを探求してきた私の(ほぼ)半世紀の間、私は非常に多くの驚きを見てきました。実際、私の経験では、ルーリロジーを行って驚きがないことは非常にまれです。ある意味で、それは謙虚な経験ですが、刺激的な経験でもあります。物事がどのように機能するかを知っていると想像します。そして、予期せぬことが起こります。そして、計算宇宙が想像していたよりもはるかに豊かであることを認識します。
私の非常に初期の、そして非常に重要なルーリロジー的驚きの1つは、最も単純なセルオートマトンに関するものでした。可能な(静止した)ルールを列挙すると、それらはすべて非常に規則的なことを行っているように見えました。しかし、その後、非常に予期せず、ルール30がそのすべての複雑さとともに現れました。
[画像]
チューリングマシンについても同様のストーリーですが、大きな驚きを見つけるにはさらに進む必要があります。そして今、(2状態、3色)マシン596440が最終的に驚くべき複雑なことを行います。
[画像]
(上記の議論で見たような)「入力」を変更するだけで得られる驚きについてはどうでしょうか? 例として、3色全量コード1329セルオートマトンを見てみましょう。多くの入力(つまり初期条件)では、それは小さな範囲の事柄を行います。
[画像]
しかし、初期条件916で突然何かが変わります。
[画像]
さらに進むと、別の驚きがあります。大きくなり続けるパターンです。
[画像]
そして、突然、入力97,439で、このルールができるとは決して推測できなかったことが起こります。
[画像]
あるシステムを見ているときに、それを十分に長く実行した場合に「最終的にどうなるか」を疑問に思うことは非常に一般的です。たとえば、停止するのか、それともただ永遠に続くのか? 計算の不可約性の現象は、原理的にはそれを判断するのが非常に難しい可能性があることを示していますが、驚くべきことは、実際には判断が難しいことがどれほど多いかということです。やや極端な例として、組み合わせ子式s[s[s]][s][s][s[s[k[k]]]]の標準的な評価を考えてみましょう。1000ステップ後、出力が大きくなり続けているように見えます。
[画像]
100,000ステップ後、物事が跳ね回っているのがわかりますが、何も停止する兆候はありません。
[画像]
しかし、突然、137,356,329ステップ後に、実際に停止します。
[画像]
これは少し異なる種類の例です。2Dセルオートマトン(外全量9近傍コード746、[画像]から開始)を実行すると、大まかに円形のパターンを生成しているように見えます(ただし、約4%の異方性があります)。
[画像]
しかし、突然、約3000ステップ後、パターンは円形性を破る「くちばし」を伸ばします。
別の種類の例として、多くの可能な移動があるシステムを考えてみましょう。これはマルチウェイグラフで表すことができます。ここでは、セルが常に8つの隣接セルのうちちょうど2つが既に黒であるという制約の下で、単一の黒いセルをすべての可能な方法で successive に追加しています。このようなシステムの「可能な履歴」のマルチウェイグラフの最初の数ステップは次のとおりです。
[画像]
そして、このグラフから、成長が常に続くと思い込むかもしれません。しかし、さらにマルチウェイグラフを進めると、驚きがあります。9ステップ後に生成された特定のクラスターは、成長させることができません。
[画像]
これは、パズルやゲームで起こることに似ています。特別な結果につながる移動の薄いセットがあります。ここでは停止状態です。
[画像]
ある意味で、ルーリロジーは「バグ」が規則であり、例外ではない分野です。そして実際、計算宇宙における計算の不可約性の遍在性は、私たちの期待を破る「驚き」が存在することが本質的に避けられないことを意味し、それを「バグ」と呼ぶかもしれません。
数学における「バグ」
「バグ」がルーリロジーでそれほど一般的であるなら、数学ではどうでしょうか? ある数学システムを研究していて、多くの例が特定の方法で機能することを発見したとしましょう。あなたは、物事が常にそのように機能するという仮説を立てるかもしれません。そして、おそらくそれは本当に機能します。あるいは、どこかに反例が存在するかもしれません。それは、あなたの仮説における実質的なバグです。
たとえば、x**n – 1 の形式の多項式の因数を見てみましょう。
[画像]
多くのケースを試します。それらはすべて係数が ±1 の結果を与えるようです。しかし、x105 – 1 を試すと、突然何かが変わります。係数が2になります。
[画像]
別の例です。3m + 2 と 3m + 1 の形式の素数の累積差を見てみましょう。最初の100,000個の素数での結果をプロットすると、この差は常に正であるように見えます。
[画像]
しかし、それはそのようには続きません。23,338,590,792番目の素数で反転し、負になります。
特に素数、数論などに関連するこのような結果はたくさんあります。そして、実際、それらのいくつかは最初の「バグ」を見つけるために天文学的に遠くまで行く必要があります。
しかし、純粋数学の主流では、このような問題はそれほど一般的ではありません。そしてある意味で、これは数学と呼ばれる活動の根本的な性質を反映しているようです。
ゲーデルの定理から、整数を含む算術方程式に関する質問でさえ、任意の計算と同等であり、したがって原理的にはルーリロジーで見られるすべての現象にさらされる可能性があることがわかっています。しかし、他の場所で詳しく説明したように、通常実践されている純粋数学は、実質的に「人間レベル」の質問に集中する傾向があり、これはルーリロジーの一般的な計算の不可約性を回避する計算の可約性のポケットに存在します。
そして実際、これは、私たちが関心のある数学が管理可能な長さの証明で固定できると期待できる理由です。そして、完全に形式化されたシンボリック証明の段階に達した場合、通常はチェックが容易です。もちろん、プログラム検証と同様に、私たちが言いたいことと形式化との間のリンクには再びバグが含まれる可能性があります。しかし、純粋数学の実践では、これらのことは想像以上に重要ではありません。なぜなら、純粋数学の中核は、証明の詳細というよりも、人間の数学的理解のフレームワークを提供する抽象構造の作成にあります。
しかし、数学がルーリロジー風のバグに常に遭遇しないということは、実際には何を意味するのでしょうか? ある意味で、それは純粋数学の開発が常に人間の理解を強調してきたという事実の直接的な反映です。数学的な構造に関する真実を知るだけが目標であれば、異なる、強力なアプローチがあります。それは実験数学です。そして実際、真剣な実験数学は、方法論的にはルーリロジーと似ていますが、純粋なルールやプログラムだけでなく、数学の構造を操作します。そして、ルーリロジーと同様に、実験数学は計算の不可約性に直接さらされており、それに伴うすべての驚きと「バグ」があります。
実践におけるバグ
では、バグのないプログラムを作成したいとしましょう。どうすればよいでしょうか? 基本的に、プログラムが常に望むことを行うことを保証する唯一の方法は、それができるすべてを理解することです。しかし、そこには一種のパラドックスがあります。プログラムが何をするかを本当にすべて理解できる場合、それは基本的にプログラムが計算的に可約なことを行っていることを意味し、おそらく最終的に結果を得るためにプログラムをすべてのステップで実行する必要はなかったでしょう。
しかし、まあ、あるレベルでは、プログラムが行っていることの特定の側面を省略する必要があります。では、プログラムが望むことを行うための最良のチャンスは何でしょうか? 言語設計が鍵だと私は信じています。なぜなら、言語設計はすべて、人間が望むことを行い、私たちが理解できるプリミティブを提供することだからです。
書くことができるプログラムは無限にあります。それぞれが何かをします。しかし、圧倒的な確率で、それらが行うことは人間が実際に望むことではありません。うまく設計された言語が行うことは、プリミティブとして人間が通常実際に望む計算作業の塊を提供することです。それらは、ある意味で、人間の思考の計算的定式化の成功のためのフレームワークを定義します。
そして、これは、十分にうまく設計された言語でプログラムを書けば、言語自体の構造が、バグと見なされるものなしに、望むことを行うプログラムを作成するように導くことを意味します。さて、私は過去数十年の大部分をWolfram Languageをこれらのことを達成する言語にすることに費やしてきました。
そして実際、Wolfram Languageでは、驚くほど複雑なタスクを、驚くほど小さく、単純で、「理解可能な」プログラムで表現することが可能です。実質的に、何が起こったかというと、計算の不可約性の大部分が言語のプリミティブに詰め込まれ、残ったのは私たち人間がアクセスでき、自然な思考パターンにマッピングされる部分です。
私はそれを何度も見てきました。Wolfram Languageでは、望むことを行い、バグと見なされるものがない短いプログラムです。プログラムに余分な複雑さがある場合、それはおそらくあなたがバグと見なすものを導入するでしょう。つまり、すべての可能なプログラムの空間では、人間として私たちが望むプログラムは、Wolfram Languageで短いプログラムとして表現できるものです。
しかし、言語がどれほどうまく設計されていても、実際に書く必要があるプログラム(つまり、少なくともいくらかの還元不可能な計算を達成しているという意味で)を書くときはいつでも、予期しないことや予見できないことを行う可能性があり、それをバグと見なすかもしれません。
では、それについて何をすることができますか? 私の生涯の経験では、実際には最も重要なことは、プログラムが何をしているのかを、可能な限り完全かつ人間がアクセス可能な方法で「内部を見る」ように努めることです。上記のセルオートマトンの例では、パターン全体を視覚化することが重要でした。そして実際、多くのケースで基本的な人間の視覚認識は、システムが常に「正しいことをする」と完全に確信を与えるのに十分でした。この「視覚的理解」に基づいて、形式的な「正しさの定理」を構築できることは間違いありません(通常は多少の努力が必要です)。しかし、それをシステムの記述から純粋に、最初に「それが内部で何をするか実際に見る」ことなく行うと、計算の不可約性の問題に遭遇し、通常は計り知れないほど困難になります。
しかし、一般的に計算を「内部から見る」にはどうすればよいでしょうか? 1Dセルオートマトンは、計算プロセスが「時空間配列」で展開され、すぐに視覚的知覚力にアクセス可能な画像として提示できる、特に簡単なケースです。1Dチューリングマシンもほぼ同じ方法で、特に(重要な情報を失わないように注意深く)それらの時空間挙動を圧縮する場合はそうです。このような即時の「時空間」プレゼンテーションを持たない他の種類のシステムでは、物事はより複雑になる可能性があり、そのようなシステムの挙動をうまく視覚化するにはある種の芸術が必要です。
従来のソフトウェアでは、さらに複雑になる可能性があります。実行中のプログラムの内部からの詳細なテレメトリの視覚化は、しばしば有益です。しかし、「プログラムの部分を個別に引き出す」実質的な方法はありません。なぜなら、変数の値などにエンコードされた複雑な共有状態があるからです。そして、これはWolfram Languageに深く組み込まれているシンボリックパラダイムの大きな強みの1つです。なぜなら、このパラダイム内では、プログラムの非常に小さな断片でさえ単独で実行でき、少なくとも「プログラムが何をしているかを詳細に見る」ための素材を提供してくれるからです。
プログラムにバグがある場合、尋ねるべき質問の1つは「それらのバグはどのようにして入ったのか?」ということです。実際には、それらは単純な人間の弱点(オフバイワンエラー、依存関係を見逃すなど)の結果であることが非常に多いです。タイプチェックのようなものは、少なくとも最も明白なエラーがすぐにキャッチされるまで物事を制約することがあります(ただし、プログラマーの柔軟性が低下するコストがかかります)。そして、最新のAIは、典型的な人間のミスステップのパターンに従うバグを見つけるのに通常はかなり優れています。
しかし、ここで主に議論してきたのは、より深い種類のバグに相当するものです。それらは、人間に関連するパターンに従わないバグです。それらは、ある意味で、計算自体の性質から生じるバグです。はい、それらは実際には人間またはAIプログラマーによってそこに置かれる可能性があります。しかし、それらは、網羅的な検索や適応進化によって、有限の制約セットでプログラムが構築された場合でも現れる可能性があります。(このような状況では、「制約」を「正しさの証明」にすることができると想像するかもしれませんが、上記で議論したように、完全な証明を作成できることは、プログラムが「計算的に重要」なことを達成することと実質的に互換性がありません)。
それらを従来の「プログラム」とは見なさないかもしれませんが、現代のAIや、例からトレーニングされたニューラルネットのようなものについて疑問に思うかもしれません。期待値は間違いなくそこでは低くなります。特定の、正確な(あるいはしばしば再現可能な)出力を期待しません。ただし、特に反復的な改善がある場合、制約が(少なくとも高い確率で)正確に満たされる段階に達する可能性があります。
しかし最終的には(訓練された野生動物の状況と少し似ていますが)、何も確実であるとは期待できないと思います。はい、機械学習のプロセスは、定義した制約とトレーニング目標を満たすように見える方法で「還元不可能な計算の塊」をまとめることができます。圧倒的な確率で構築されるのは「理解可能なメカニズム」ではありません。そして必然的に、計算の不可約性の1つの部分が「噴出」し、システムが予期しない方法で動作する可能性があります。現実的なニューラルネットで実際に起こることは、視覚化したり「人間レベルで理解したり」するのが非常に困難になります。そして実際、何が起こっているかの核心は、ここで研究した非常に単純なシステムでさえ、私たちがここで見たものと基本的に同じになります。
しかし、バグをいくつか許容するとどうなるでしょうか? プログラムが、プリミティブが計算したいものによく適合する言語で書かれている場合、バグを許容してもプログラムが短くなる可能性は低いです。しかし、プログラムがより低レベル、たとえばチューリングマシンとして書かれている場合、バグをいくつか許容するとプログラムが短くなる可能性があると予想できます(上記で見たように)。そのような場合、私たちは「生の計算を制御する」ことを試みていると考えることができ、私たちがやろうとしていることに近似的に適合する「計算の塊」を見つける方が、正確に適合する塊を見つけるよりも簡単になる傾向があります。
では、ある方法で動作すると考えているプログラムを実行しているとしましょう。しかし、そうではありません。代わりに、バグと見なせるものがあります。さて、工学を行っている場合、これを失敗と見なすでしょう。しかし、科学を行っている場合、それを成功と見なすかもしれません。なぜなら、実質的に予期しなかった何かを発見したからです。そして実際、ルーリロジーの進歩の多くは、まさに一連の「バグ」の発見、あるいは少なくとも通常の直感に対するバグの発見であると考えることができます。しかし今、ルーリロジーから学んだことで、これを転換し、どこにあっても普遍的で根本的なバグの現象の基礎のいくつかを理解し始めることができます。
感謝
Wolfram Instituteの数名のメンバーに協力していただいたことに感謝します。Richard Assar、Júlia Campolim、Nik Murzin、Willem Nielsenです。また、過去40年以上にわたり半ミリオン以上のバグ(その大部分は現在修正されています!)を処理し、バグの現象に対する私の直感を開発するのに役立ったWolfram Software Quality Assuranceチームにも感謝します。長年にわたりルーリロジーで私と一緒に働いてくれたすべての人々にも感謝します。そして、ルーリロジー的な驚きに対する私の繰り返しの反応を目撃した人々にも感謝します。「計算上の動物は私たちよりも賢いと認識しなければならない!」