Full employment theorem
Encyclopedia
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. 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 a better compiler since the proof that you've got 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.
Less formally, combative tasks such as virus
writing and detection, and spam
filtering and filter-breaking appear to be candidates for full employment.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
and mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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. 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
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
and reduce them to a one-instruction infinite loop
Infinite loop
An infinite loop is a sequence of instructions in a computer program which loops endlessly, either due to the loop having no terminating condition, having one that can never be met, or one that causes the loop to start over...
. Thus, the existence of a provably perfect size-optimizing compiler would imply a solution to the halting problem
Halting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
, which cannot exist, making the proof itself an undecidable problem
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
. This also implies that there may always a better compiler since the proof that you've got 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
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
have been called full employment theorems for mathematicians. In theoretical computer science
Theoretical computer science
Theoretical computer science is a division or subset of general computer science and mathematics which focuses on more abstract or mathematical aspects of computing....
this field of study is known as Kolmogorov complexity
Kolmogorov complexity
In algorithmic information theory , the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object...
, or the smallest program which outputs a given string.
Less formally, combative tasks such as virus
Computer virus
A computer virus is a computer program that can replicate itself and spread from one computer to another. The term "virus" is also commonly but erroneously used to refer to other types of malware, including but not limited to adware and spyware programs that do not have the reproductive ability...
writing and detection, and spam
Spam
Spam may refer to:* Spam , a canned pork meat product* Spam , unsolicited or undesired electronic messages* E-mail spam, unsolicited or undesired email messages* "Spam" , a comedy sketch...
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 can exist, and hence there will always be some particular problem whose best known solution might be improved.