This HTML5 document contains 27 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

Prefix	IRI
dcterms	http://purl.org/dc/terms/
dbo	http://dbpedia.org/ontology/
foaf	http://xmlns.com/foaf/0.1/
n6	https://global.dbpedia.org/id/
dbt	http://dbpedia.org/resource/Template:
rdfs	http://www.w3.org/2000/01/rdf-schema#
n10	http://world.std.com/~rjs/
rdf	http://www.w3.org/1999/02/22-rdf-syntax-ns#
owl	http://www.w3.org/2002/07/owl#
wikipedia-en	http://en.wikipedia.org/wiki/
dbc	http://dbpedia.org/resource/Category:
dbp	http://dbpedia.org/property/
prov	http://www.w3.org/ns/prov#
xsdh	http://www.w3.org/2001/XMLSchema#
wikidata	http://www.wikidata.org/entity/
dbr	http://dbpedia.org/resource/
n13	https://web.archive.org/web/20050402183906/http:/www.cis.upenn.edu/~cis570/slides/

Statements

Subject Item

dbr:Full-employment_theorem

rdfs:label

Full-employment theorem

rdfs:comment

In computer science and 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.

dcterms:subject

dbc:Mathematical_theorems dbc:Theoretical_computer_science

dbo:wikiPageID

5723289

dbo:wikiPageRevisionID

1090287865

dbo:wikiPageWikiLink

dbc:Mathematical_theorems dbr:Spam_(electronic) dbr:Gödel's_incompleteness_theorems dbr:Rice's_theorem dbr:Computer_virus dbr:No_free_lunch_in_search_and_optimization dbr:Mathematics dbr:Halting_problem dbc:Theoretical_computer_science dbr:Infinite_loop dbr:Computer_science

dbo:wikiPageExternalLink

n10:z138.pdf n13:lecture01.pdf

owl:sameAs

n6:4k1rP wikidata:Q5508180

dbp:wikiPageUsesTemplate

dbt:ISBN dbt:Short_description

dbo:abstract

In computer science and 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. Thus, the existence of a provably perfect size-optimizing compiler would imply a solution to the halting problem, 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, 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 have been called full employment theorems for mathematicians. Tasks such as virus writing and detection, and spam filtering and filter-breaking are also subject to Rice's theorem.

prov:wasDerivedFrom

wikipedia-en:Full-employment_theorem?oldid=1090287865&ns=0

dbo:wikiPageLength

2506

foaf:isPrimaryTopicOf

wikipedia-en:Full-employment_theorem