Full employment theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In computer science and mathematics, a full employment theorem is a theorem which states that no algorithm can optimally perform a particular task done by some class of professionals. The name arises because such a theorem ensures that there is endless scope to keep discovering new techniques to improve the way at least some specific task is done.

For example, the full employment theorem for compiler writers states that there is no such thing as a provably perfect size-optimizing compiler, as such a proof for the compiler would have to detect non-terminating computations and reduce them to a one-instruction infinite loop. Thus, the existence of a provably perfect size-optimizing compiler would imply a solution to the halting problem, which cannot exist, making the proof itself an undecidable problem. This also implies that there may always be a better compiler since the proof that one has the best compiler cannot exist. Therefore, compiler writers will always be able to speculate that they have something to improve. Similarly, Gödel's incompleteness theorems have been called full employment theorems for mathematicians. In theoretical computer science this field of study is known as Kolmogorov complexity, or the smallest program which outputs a given string.

Tasks such as virus writing and detection, and spam filtering and filter-breaking are also subject to Rice's theorem.

Additional examples


  • Solomonoff, Ray, "A Preliminary Report on a General Theory of Inductive Inference", Report V-131, Zator Co., Cambridge, Ma. Feb 4, 1960.
  • p. 401, Modern Compiler Implementation in ML, Andrew W. Appel, Cambridge University Press, 1998. ISBN 0-521-58274-1.
  • p. 27, Retargetable Compiler Technology for Embedded Systems: Tools and Applications, Rainer Leupers and Peter Marwedel, Springer-Verlag, 2001. ISBN 0-7923-7578-5.
  • Notes from a course in Modern Programming Languages at the University of Pennsylvania See p. 8.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Full_employment_theorem&oldid=789003942"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Full_employment_theorem
This page is based on the copyrighted Wikipedia article "Full employment theorem"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA