Теорема о полной занятости

Теорема, подразумевающая, что ни один алгоритм не может оптимально выполнить задачу, выполняемую людьми.

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

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

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

Ссылки

Соломонов, Рэй, «Предварительный отчет об общей теории индуктивного вывода», Отчет V-131, Zator Co., Кембридж, Массачусетс. 4 февраля 1960 г.
стр. 401, Современная реализация компилятора в ML , Эндрю В. Аппель, Cambridge University Press, 1998. ISBN 0-521-58274-1 .
стр. 27, Технология перенацеливаемых компиляторов для встраиваемых систем: инструменты и приложения , Райнер Лойперс и Питер Марведель, Springer-Verlag, 2001. ISBN 0-7923-7578-5 .
Заметки из курса современных языков программирования в Университете Пенсильвании. См. стр. 8.