Full employment theorem

In computer science and mathematics, the term full employment theorem has been used to refer to a theorem showing that no algorithm can optimally perform a particular task done by some class of professionals. For example, the "full employment theorem for compiler writers" states that there is no such thing as a perfect size-optimizing compiler, as such a compiler would have to detect non-terminating computations and reduce them to a one-instruction infinite loop. Thus, the existence of a perfect size-optimizing compiler would imply a solution to the halting problem, which cannot exist. Similarly, Gödel's incompleteness theorems have been called full employment theorems for mathematicians.

The name arises because such a theorem ensures that there is endless scope to keep discovering new techniques to improve the way a specific task is done. However, observe that these same tasks (devising new algorithms, proving theorems, and so on), could also be performed by AI systems. It is then possible that an AI could put human professionals out of work, meaning that a full employment theorem does not guarantee employment. To put the point another way, if one accepts that humans are natural systems subject to the same physical laws as are computers, then any professional will have a finite repertoire of skills to apply and could be bested by a computer with superior resources.

Less formally, combative tasks such as virus writing and detection, and spam filtering and filter-breaking appear to be candidates for full employment.

Additional examples

*No free lunch in search and optimization - no efficient general-purpose solver exists, and hence there is always scope for improving algorithms for better performance on particular problems.

References

* p. 401, "Modern Compiler Implementation in ML", Andrew W. Appel, Cambridge University Press, 1998. ISBN 0521582741.
* p. 27, "Retargetable Compiler Technology for Embedded Systems: Tools and Applications", Rainer Leupers and Peter Marwedel, Springer-Verlag, 2001. ISBN 0792375785.
* [http://www.cis.upenn.edu/~cis570/slides/lecture01.pdf Notes from a course in Modern Programming Languages at the University of Pennsylvania] See p. 8.