computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

and

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, a full employment theorem is a term used, often humorously, to refer to 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 In computer programming, an infinite loop (or endless loop) is a sequence of instructions that, as written, will continue endlessly, unless an external intervention occurs ("pull the plug"). It may be intentional. Overview This differs from: * ...

. Thus, the existence of a provably perfect size-optimizing compiler would imply a solution to the

halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a g ...

, which cannot exist. 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. A similar example in practical computer science is the idea of

no free lunch in search and optimization In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same ...

, which states that no efficient general-purpose solver can exist, and hence there will always be some particular problem whose best known solution might be improved. Similarly,

Gödel's incompleteness theorems Gödel's incompleteness theorems are two theorems of mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research i ...

have been called full employment theorems for mathematicians. Tasks such as

virus A virus is a submicroscopic infectious agent that replicates only inside the living cells of an organism. Viruses infect all life forms, from animals and plants to microorganisms, including bacteria and archaea. Since Dmitri Ivanovsky's 1 ...

writing and detection, and

spam Spam may refer to: * Spam (food), a canned pork meat product * Spamming, unsolicited or undesired electronic messages ** Email spam, unsolicited, undesired, or illegal email messages ** Messaging spam, spam targeting users of instant messaging ( ...

filtering and filter-breaking are also subject to

Rice's theorem In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a synta ...

References

* 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. . * 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. Mathematical theorems Theoretical computer science