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