完全雇用定理

コンピュータサイエンスと数学において、完全雇用定理とは、ある種の専門家が行う特定のタスクを最適に実行するアルゴリズムは存在しないという定理を指すために、しばしば冗談めかして使用される用語です。この定理の名前の由来は、少なくとも特定のタスクの実行方法を改善するための新しい手法を発見し続ける余地が無限にあることを保証している定理だからです。

たとえば、コンパイラ作成者に対する完全雇用定理は、証明可能に完璧なサイズ最適化コンパイラなど存在しないと述べています。そのようなコンパイラの証明は、終了しない計算を検出し、それを 1 命令の無限ループに縮小する必要があるためです。したがって、証明可能に完璧なサイズ最適化コンパイラの存在は、存在し得ない停止問題の解を意味します。これはまた、最良のコンパイラを持っているという証明は存在し得ないため、より優れたコンパイラが常に存在する可能性があることも意味します。したがって、コンパイラ作成者は常に、改善すべき点があると推測することができます。実際のコンピュータ サイエンスにおける同様の例としては、検索と最適化におけるただ飯はないという考え方があります。これは、効率的な汎用ソルバーは存在し得ず、したがって、最もよく知られている解決策を改善できる可能性のある特定の問題が常に存在するというものです。

同様に、ゲーデルの不完全性定理は数学者にとって完全雇用定理と呼ばれています。ウイルスの作成と検出、スパムのフィルタリングとフィルタの破りなどのタスクもライスの定理の対象となります。

• ソロモノフ、レイ、「帰納的推論の一般理論に関する予備報告」、レポート V-131、ザター社、マサチューセッツ州ケンブリッジ、1960 年 2 月 4 日。
• p. 401、ML における最新のコンパイラ実装、Andrew W. Appel、Cambridge University Press、1998 年 。ISBN  0-521-58274-1。
• p . 27、組み込みシステム向けの再ターゲット可能なコンパイラテクノロジ: ツールとアプリケーション、Rainer Leupers および Peter Marwedel、Springer-Verlag、2001 年。ISBN 0-7923-7578-5。 
• ペンシルバニア大学の現代プログラミング言語のコースのノート。8 ページを参照してください。