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