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

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

Определение [ править ]

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

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

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

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

Алгоритмы [ править ]

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

Вычислимые функции [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

^ Хантер, Джеффри , Металогика: введение в метатеорию стандартной логики первого порядка , University of California Press, 1971
^ Ганди, Робин (1980). «Тезис Черча и принципы механизмов» . Симпозиум Клини . Проверено 19 апреля 2024 г.
^ Коупленд, Би Джей ; Коупленд, Джек; Праудфут, Дайан (июнь 2000 г.). «Тезис Тьюринга-Черча» . АланТуринг.нет . Архив Тьюринга по истории вычислений . Проверено 23 марта 2013 г.
^ Кембриджский философский словарь, эффективная процедура

С. К. Клини (1967), Математическая логика . Перепечатано, Дувр, 2002 г., ISBN 0-486-42533-9 , стр. 233 и далее, особенно. п. 231.

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

[metalogic-1] Хантер, Джеффри , Металогика: введение в метатеорию стандартной логики первого порядка , University of California Press, 1971

[2] Ганди, Робин (1980). «Тезис Черча и принципы механизмов» . Симпозиум Клини . Проверено 19 апреля 2024 г.

[alanturingnet-3] Коупленд, Би Джей ; Коупленд, Джек; Праудфут, Дайан (июнь 2000 г.). «Тезис Тьюринга-Черча» . АланТуринг.нет . Архив Тьюринга по истории вычислений . Проверено 23 марта 2013 г.

[4] Кембриджский философский словарь, эффективная процедура

[1]

[2]

[3]

[4]