В логике , математике и информатике , особенно в металогике и теории вычислимости , эффективный метод [1] или эффективная процедура — это процедура решения задачи любым интуитивно «эффективным» средством из определенного класса. [2] Эффективный метод иногда также называют механическим методом или процедурой. [3]
Определение эффективного метода включает в себя нечто большее, чем сам метод. Чтобы метод можно было назвать эффективным, его необходимо рассматривать применительно к классу задач. Из-за этого один метод может быть эффективен по отношению к одному классу задач и неэффективен по отношению к другому классу.
Метод формально называется эффективным для определенного класса задач, если он удовлетворяет следующим критериям:
При желании также может потребоваться, чтобы метод никогда не возвращал результат, как если бы это был ответ, когда метод применяется к проблеме вне его класса. Добавление этого требования уменьшает набор классов, для которых существует эффективный метод.
Эффективным методом вычисления значения функции является алгоритм . Функции, для которых существует эффективный метод, иногда называют эффективно вычислимыми .
Несколько независимых попыток дать формальную характеристику эффективной вычислимости привели к множеству предложенных определений ( общерекурсивные функции , машины Тьюринга , λ-исчисление ), которые позже оказались эквивалентными. Понятие, отраженное в этих определениях, известно как рекурсивная или эффективная вычислимость .
Тезис Чёрча -Тьюринга утверждает, что эти два понятия совпадают: любая теоретико-числовая функция , которая эффективно вычислима, вычислима рекурсивно . Поскольку это не математическое утверждение, его нельзя доказать математическим доказательством . [ нужна цитата ]
{{cite journal}}: Требуется цитировать журнал |journal=( помощь )