Ефективний метод
Ефективний метод[1] або ефективна процедура у логіці, математиці та інформатиці, особливо у металогіці та теорії обчислюваності — це процедура вирішення проблеми з певного класу. Ефективний метод іноді також називають «механічним» методом або процедурою.[2]
Визначення ефективного методу передбачає більше, ніж сам метод. Для того, щоб метод називався ефективним, він повинен розглядатися відповідно до класу проблем. Через це один метод може бути ефективним стосовно одного класу проблем і «не бути» ефективним щодо іншого класу. Метод формально називається ефективним для класу задач, якщо він відповідає наступним критеріям:
- Він складається з кінцевого числа точних, кінцевих інструкцій;
- Коли він застосовується до проблеми свого класу:
- Він завжди закінчується (завершується) після кінцевого числа кроків;
- Він завжди дає правильну відповідь;
- В принципі, він може бути використаний людиною без будь-яких засобів, крім написання матеріалів.
- Для досягнення успіху слід лише суворо[en]дотримуватися його інструкцій. Іншими словами, це не вимагає винахідливості[en].[3]
Іноді також необхідно, щоб метод ніколи не приймав результат за відповідь, коли він застосовується до проблем, що не належать до його класу. Додавання цієї вимоги зменшує набір класів, для яких існує ефективний метод.
Алгоритм — це ефективний методом для обчислення значень функції. Функції, для яких існує ефективний метод, іноді називають ефективно обчислюваними.
Кілька незалежних зусиль, щоб дати офіційну характеристику ефективного обчислення, призвели до різноманіття запропонованих визначень (зазальна рекурсія, машини Тюрінга, лямбда-числення), які раніше були еквівалентними. Отже, рекурсивна або ефективна обчислюваність — поняття, що зафіксоване цими визначеннями.
У тезі Черча сказано, що ці два поняття збігаються. Обчислювана функція — це будь-яка арифметична функція, яка ефективно піддається підрахунку. Оскільки це не математичне твердження, його неможливо довести за допомогою математичного доказу.
- Алгоритмічна розв'язність
- Проблема вибору
- Функціональна проблема
- Ефективні результати в теорії чисел[en]
- Рекурсивний набір
- Алгоритмічно нерозв'язна задача
- ↑ Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
- ↑ Copeland, B.J.; Copeland, Jack; Proudfoot, Diane (June 2000). The Turing-Church Thesis. AlanTuring.net. Turing Archive for the History of Computing. Архів оригіналу за 27 березня 2013. Процитовано 23 березня 2013.
- ↑ The Cambridge Dictionary of Philosophy, effective procedure
- S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, ISBN 0-486-42533-9, pp. 233 ff., esp. p. 231.
|
Це незавершена стаття з логіки. Ви можете допомогти проєкту, виправивши або дописавши її. |