Théorème du plein emploi

Théorème du plein emploi (Redirigé à partir du théorème du plein emploi) Aller à la navigation Aller à la recherche En informatique et mathématiques, un théorème de plein emploi est un terme utilisé, souvent avec humour, faire référence à un théorème qui stipule qu'aucun algorithme ne peut effectuer de manière optimale une tâche particulière effectuée par une classe de professionnels. Le nom apparaît parce qu'un tel théorème garantit qu'il y a une portée infinie pour continuer à découvrir de nouvelles techniques pour améliorer la façon dont au moins une tâche spécifique est effectuée..

Par exemple, le théorème du plein emploi pour les auteurs de compilateurs stipule qu'il n'existe pas de compilateur d'optimisation de taille dont la perfection soit prouvée, en tant que telle, une preuve pour le compilateur devrait détecter les calculs sans fin et les réduire à une boucle infinie à une instruction. Ainsi, l'existence d'un compilateur d'optimisation de taille dont on peut prouver qu'il est parfait impliquerait une solution au problème d'arrêt, qui ne peut exister. Cela implique également qu'il peut toujours y avoir un meilleur compilateur puisque la preuve que l'on a le meilleur compilateur ne peut pas exister. Par conséquent, les auteurs de compilateurs pourront toujours supposer qu'ils ont quelque chose à améliorer. Un exemple similaire en informatique pratique est l'idée qu'il n'y a pas de repas gratuits dans la recherche et l'optimisation, qui stipule qu'aucun solveur polyvalent efficace ne peut exister, et donc il y aura toujours un problème particulier dont la meilleure solution connue pourrait être améliorée.

De la même manière, Les théorèmes d'incomplétude de Gödel ont été appelés théorèmes de plein emploi pour les mathématiciens. Tâches telles que l'écriture et la détection de virus, et le filtrage du spam et la rupture de filtre sont également soumis au théorème de Rice.

Références Solomonoff, Rayon, "Un rapport préliminaire sur une théorie générale de l'inférence inductive", Rapport V-131, Zator Co., Cambridge, Maman. Fév 4, 1960. p. 401, Implémentation d'un compilateur moderne en ML, André W. appel, la presse de l'Universite de Cambridge, 1998. ISBN 0-521-58274-1. p. 27, Technologie de compilateur retargetable pour les systèmes embarqués: Outils et Applications, Rainer Leupers et Peter Marwedel, Springer Verlag, 2001. ISBN 0-7923-7578-5. Notes d'un cours de langages de programmation modernes à l'Université de Pennsylvanie Voir p. 8. Catégories: Théorèmes mathématiquesInformatique théorique