Věta o plné zaměstnanosti - Full employment theorem

v počítačová věda a matematika, a věta o plné zaměstnanosti je termín používaný, často vtipně, k označení věty, která uvádí, že žádný algoritmus nemůže optimálně provést konkrétní úkol provedený nějakou třídou profesionálů. Název vzniká, protože taková věta zajišťuje, že existuje nekonečný prostor pro objevování nových technik ke zlepšení způsobu, jakým je prováděn alespoň nějaký konkrétní úkol.

Například věta o plné zaměstnanosti pro autory překladačů uvádí, že neexistuje prokazatelně dokonalý kompilátor optimalizující velikost, protože takový důkaz pro kompilátor by musel detekovat nekončící výpočty a omezit je na jeden pokyn nekonečná smyčka. Existence prokazatelně dokonalého kompilátoru optimalizujícího velikost by tedy znamenala řešení zastavení problému, který nemůže existovat. To také znamená, že vždy může existovat lepší kompilátor, protože důkaz, že jeden má nejlepší kompilátor, nemůže existovat. Tvůrci překladačů proto vždy budou moci spekulovat, že mají co vylepšovat. Podobným příkladem v praktické informatice je myšlenka žádný oběd zdarma při hledání a optimalizaci, který uvádí, že žádný efektivní univerzální řešič nemůže existovat, a proto vždy bude existovat nějaký konkrétní problém, jehož nejznámější řešení by mohlo být vylepšeno.

Podobně, Gödelovy věty o neúplnosti byly nazývány teorémy plné zaměstnanosti pro matematiky. Úkoly jako virus psaní a detekce a spam filtrování a rozbití filtru rovněž podléhají Riceova věta.

Reference

• Solomonoff, Ray, "Předběžná zpráva o obecné teorii indukčního závěru ", Zpráva V-131, Zator Co., Cambridge, Ma. 4. února 1960.
• p. 401, Moderní implementace kompilátoru v MLAndrew W. Appel, Cambridge University Press, 1998. ISBN  0-521-58274-1.
• p. 27, Technologie Retargetable Compiler pro vestavěné systémy: nástroje a aplikace, Rainer Leupers a Peter Marwedel, Springer-Verlag, 2001. ISBN  0-7923-7578-5.
• Poznámky z kurzu moderních programovacích jazyků na University of Pennsylvania Prosáknout. 8.