British Museum algorithm とは

大英博物館のアルゴリズムは、すべての可能性を一つずつチェックし、最小から始めて解決策を見つける一般的なアプローチです。この用語は、可能性の数が膨大な概念的で実用的ではない技術を指しています。
たとえば、理論的には、特定の問題を次のように解決する最小のプログラムを見つけることができます。長さ1文字のすべてのソースコードを生成します。それぞれが問題を解決しているかどうかを確認してください。 (注:停止の問題はこのチェックを面倒にしますが、これはダブテールでは克服することができます)。そうでない場合は、2文字、3文字などのプログラムをすべて生成してチェックします。これは概念的には最小のプログラムですが、 (多くの場合、宇宙の生涯よりも)長い時間を取ること。
最適化、定理証明、言語認識などが可能であるか不可能であることを示すために同様の議論を行うことができる。
Newell、Shaw、Simonはこの手続きを大英博物館アルゴリズムと呼んだ
"…大英博物館のすべての本を再現するためには、サルをタイプライターの前に置くことが賢明であるように思えたからです。"