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