Определение «проблемы» , чтобы быть алгоритм принимает натуральное число и возвращает 0 или 1 , который возвращает 1 , по меньшей мере , одной п ∈ N . Любое такое n называется «решением» A
Определите «универсальный решатель проблем» как алгоритм принимающий проблему и возвращающий одно из ее решений. Например, U может работать, циклически перебирая все натуральные числа и выполняя свой ввод для них до тех пор, пока не будет получен 1 результат (он должен остановиться только на допустимом вводе)
Я заинтересован в изучении границ производительности на универсальных решениях проблем
Учитывая, что является универсальным решателем проблем, а A - проблемой, обозначим t ( U , A ) время, которое требуется U для получения вывода при принятии ввода A
Универсальный решатель задач называется «эффективным», когда для любого универсального решателя проблем V имеем
Здесь зависит от V, но не зависит от A
Существуют ли эффективные универсальные решения проблем?
РЕДАКТИРОВАТЬ: я понял, что можно изменить определения «проблема» и «универсальный решатель проблем» в нечто более элегантное и по существу эквивалентное. «Проблема» - это алгоритм без ввода, возвращающий 0 или 1 (который останавливается). «Универсальный решатель проблем» - это алгоритм, принимающий проблему и возвращающий ее результат. Это более или менее универсальная машина Тьюринга
Старое определение может быть сведено к новому определению, поскольку, учитывая проблему в старом смысле, мы можем построить проблему B в новом смысле, который просто применяет тривиальный универсальный решатель старых проблем к A (решателю, описанному в тексте выше). )
Новое определение может быть сведено к старому определению, поскольку, учитывая проблему в новом смысле, мы можем построить проблему A в старом смысле, которая просто вычисляет B и сравнивает входные данные с результатом.
Тривиальным примером универсального решения проблем в новом смысле является алгоритм, который просто выполняет ввод
источник