Эффективный метод

В логике , математике и информатике , особенно в металогике и теории вычислимости , эффективный метод ^[1] или эффективная процедура — это процедура решения задачи любым интуитивно «эффективным» средством из определенного класса. ^[2] Эффективный метод иногда также называют механическим методом или процедурой. ^[3]

Определение эффективного метода включает в себя больше, чем сам метод. Для того, чтобы метод можно было назвать эффективным, его нужно рассматривать по отношению к классу проблем. Из-за этого один метод может быть эффективным по отношению к одному классу проблем и неэффективным по отношению к другому классу.

Метод формально называется эффективным для класса задач, если он удовлетворяет следующим критериям:

• Он состоит из конечного числа точных, конечных инструкций.
• При применении к проблеме из своего класса:
  • Он всегда завершается ( теряется ) после конечного числа шагов.
  • Он всегда дает правильный ответ.
• В принципе, это может сделать человек без каких-либо вспомогательных средств, кроме письменных принадлежностей.
• Его инструкции нужно только строго соблюдать, чтобы добиться успеха. Другими словами, для успеха не требуется никакой изобретательности . ^[4]

При желании можно также потребовать, чтобы метод никогда не возвращал результат, как если бы это был ответ, когда метод применяется к проблеме извне его класса. Добавление этого требования сокращает набор классов, для которых существует эффективный метод.

Эффективным методом вычисления значений функции является алгоритм . Функции, для которых существует эффективный метод, иногда называют эффективно вычисляемыми .

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

Тезис Чёрча -Тьюринга утверждает, что эти два понятия совпадают: любая теоретико-числовая функция , которая эффективно вычислима, является рекурсивно вычислимой . Поскольку это не математическое утверждение, оно не может быть доказано математическим доказательством . ^{[ требуется цитата ]}

• Разрешимость (логика)
• Проблема решения
• Проблема с функцией
• Эффективные результаты в теории чисел
• Рекурсивный набор
• Неразрешимая проблема

• SC Kleene (1967), Математическая логика . Переиздано, Dover, 2002, ISBN 0-486-42533-9 , стр. 233 и далее, особенно стр. 231. 

Эта статья, связанная с логикой, является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е