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