Эффективный метод - Effective method
В логике , математике и информатике , особенно в металогике и теории вычислимости , эффективный метод или эффективная процедура - это процедура для решения проблемы из определенного класса. Эффективный метод иногда также называют механическим методом или процедурой.
Определение
Определение эффективного метода включает больше, чем сам метод. Чтобы метод назывался эффективным, его необходимо рассматривать применительно к классу проблем. Из - за этого, один способ может быть эффективным по отношению к одному классу задач и не быть эффективным по отношению к другому классу.
Формально метод называется эффективным для класса задач, если он удовлетворяет следующим критериям:
- Он состоит из конечного числа точных конечных инструкций.
- Когда он применяется к проблеме из своего класса:
- Он всегда заканчивается ( завершается ) после конечного числа шагов.
- Он всегда дает правильный ответ.
- В принципе, это может сделать человек без каких-либо вспомогательных средств, кроме письменных принадлежностей.
- Чтобы добиться успеха, нужно только неукоснительно выполнять его инструкции . Другими словами, для достижения успеха не требуется изобретательности .
При желании может также потребоваться, чтобы метод никогда не возвращал результат, как если бы это был ответ, когда метод применяется к проблеме извне своего класса. Добавление этого требования сокращает набор классов, для которых существует эффективный метод.
Алгоритмы
Эффективным методом вычисления значений функции является алгоритм . Функции, для которых существует эффективный метод, иногда называют эффективно вычисляемыми .
Вычислимые функции
Несколько независимых попыток дать формальную характеристику эффективной вычислимости привели к множеству предложенных определений ( общая рекурсия , машины Тьюринга , λ-исчисление ), эквивалентность которых позже была показана. Понятие, охватываемое этими определениями, известно как рекурсивная или эффективная вычислимость .
В тезис Черча-Тьюринга утверждает , что эти два понятия совпадают: любое число теоретико-функция , которая эффективно вычисляемыми является рекурсивно вычислимой . Поскольку это не математическое утверждение, его нельзя доказать математическим доказательством .
Смотрите также
- Разрешимость (логика)
- Проблема решения
- Функциональная проблема
- Эффективные результаты в теории чисел
- Рекурсивный набор
- Неразрешимая проблема
использованная литература
- SC Kleene (1967), Математическая логика . Перепечатано, Довер, 2002, ISBN 0-486-42533-9 , стр. 233 и сл., Особенно. п. 231.
 |
Эта статья о логике - незавершенная . Вы можете помочь Википедии, расширив ее . |