Теорема о полной занятости - Full employment theorem

В информатике и математике теорема о полной занятости - это термин, который часто юмористически используется для обозначения теоремы, в которой говорится, что ни один алгоритм не может оптимально выполнить конкретную задачу, выполняемую некоторым классом профессионалов. Название возникло из-за того, что такая теорема гарантирует, что есть бесконечные возможности для продолжения открытия новых методов для улучшения способа выполнения хотя бы какой-то конкретной задачи.

Например, теорема о полной занятости для разработчиков компиляторов утверждает, что не существует такой вещи, как доказуемо совершенный компилятор, оптимизирующий размер, поскольку такое доказательство для компилятора должно было бы обнаруживать нескончаемые вычисления и сводить их к бесконечным вычислениям с одной инструкцией. петля . Таким образом, существование доказуемо совершенного компилятора, оптимизирующего размер, означало бы решение проблемы остановки , которой не может быть. Это также означает, что всегда может быть лучший компилятор, поскольку доказательства того, что у вас лучший компилятор, не существует. Поэтому разработчики компиляторов всегда могут предположить, что им есть что улучшить. Аналогичным примером в практической информатике является идея отсутствия бесплатного обеда в поиске и оптимизации , которая утверждает, что не может существовать эффективного решателя общего назначения, и, следовательно, всегда будет какая-то конкретная проблема, лучшее известное решение которой может быть улучшено.

Точно так же теоремы Гёделя о неполноте для математиков называются теоремами о полной занятости. Такие задачи, как написание и обнаружение вирусов , а также фильтрация спама и взлом фильтров, также подчиняются теореме Райса .

Рекомендации

• Solomonoff, Ray, " Предварительный отчет по общей теории индуктивного вывода ", Report V-131, Zator Co., Кембридж, штат Массачусетс. 4 февраля 1960 г.
• п. 401, Современная реализация компилятора в ML , Эндрю В. Аппель, Cambridge University Press, 1998. ISBN  0-521-58274-1 .
• п. 27, Retargetable Compiler Technology for Embedded Systems: Tools and Applications , Rainer Leupers and Peter Marwedel, Springer-Verlag, 2001. ISBN  0-7923-7578-5 .
• Заметки из курса современных языков программирования в Университете Пенсильвании. См. Стр. 8.