Эффективный метод
В логике , математике и информатике , особенно в металогике и теории вычислимости , эффективным методом является [1] или эффективная процедура — это процедура решения проблемы любыми интуитивно «эффективными» средствами из определенного класса. [2] Эффективный метод иногда также называют механическим методом или процедурой. [3]
Определение
[ редактировать ]Определение эффективного метода включает в себя нечто большее, чем сам метод. Чтобы метод можно было назвать эффективным, его необходимо рассматривать применительно к классу задач. Из-за этого один метод может быть эффективен по отношению к одному классу задач и неэффективен по отношению к другому классу.
Метод формально называется эффективным для определенного класса задач, если он удовлетворяет следующим критериям:
- Он состоит из конечного числа точных, конечных инструкций.
- Когда он применяется к задаче из своего класса:
- Он всегда завершается ( завершается ) после конечного числа шагов.
- Он всегда дает правильный ответ.
- В принципе, это может сделать человек без каких-либо вспомогательных средств, кроме письменных принадлежностей.
- следовать его инструкциям Чтобы добиться успеха, нужно только неукоснительно . Другими словами, для достижения успеха не требуется никакой изобретательности . [4]
При желании также может потребоваться, чтобы метод никогда не возвращал результат, как если бы это был ответ, когда метод применяется к проблеме вне его класса. Добавление этого требования уменьшает набор классов, для которых существует эффективный метод.
Алгоритмы
[ редактировать ]Эффективным методом вычисления значения функции является алгоритм . Функции, для которых существует эффективный метод, иногда называют эффективно вычислимыми .
Вычислимые функции
[ редактировать ]Несколько независимых попыток дать формальную характеристику эффективной вычислимости привели к множеству предложенных определений ( общерекурсивные функции , машины Тьюринга , λ-исчисление ), которые позже оказались эквивалентными. Понятие, отраженное в этих определениях, известно как рекурсивная или эффективная вычислимость .
Тезис Чёрча -Тьюринга утверждает, что эти два понятия совпадают: любая теоретико-числовая функция , которая эффективно вычислима, является рекурсивно вычислимой . Поскольку это не математическое утверждение, его нельзя доказать математическим доказательством . [ нужна ссылка ]
См. также
[ редактировать ]- Разрешимость (логика)
- Проблема решения
- Функциональная проблема
- Эффективные результаты в теории чисел
- Рекурсивный набор
- Неразрешимая проблема
Ссылки
[ редактировать ]- ^ Хантер, Джеффри , Металогика: введение в метатеорию стандартной логики первого порядка , University of California Press, 1971
- ^ Ганди, Робин (1980). «Тезис Черча и принципы механизмов» . Симпозиум Клини . Проверено 19 апреля 2024 г.
- ^ Коупленд, Би Джей ; Коупленд, Джек; Праудфут, Дайан (июнь 2000 г.). «Тезис Тьюринга-Черча» . АланТуринг.нет . Архив Тьюринга по истории вычислений . Проверено 23 марта 2013 г.
- ^ Кембриджский философский словарь, эффективная процедура
- С. К. Клини (1967), Математическая логика . Перепечатано, Дувр, 2002 г., ISBN 0-486-42533-9 , стр. 233 и далее, особенно. п. 231.
 | Эта логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее . |