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