Ефективний процес

Ефективний метод або ефективна процедура у логіці, математиці та інформатиці, особливо у металогіці та теорії обчислюваності — це процедура вирішення проблеми з певного класу. Ефективний метод іноді також називають «механічним» методом або процедурою.

Визначення

Визначення ефективного методу передбачає більше, ніж сам метод. Для того, щоб метод називався ефективним, він повинен розглядатися відповідно до класу проблем. Через це один метод може бути ефективним стосовно одного класу проблем і «не бути» ефективним щодо іншого класу. Метод формально називається ефективним для класу задач, якщо він відповідає наступним критеріям:

• Він складається з кінцевого числа точних, кінцевих інструкцій;
• Коли він застосовується до проблеми свого класу:
  • Він завжди закінчується (завершується) після кінцевого числа кроків;
  • Він завжди дає правильну відповідь;
• В принципі, він може бути використаний людиною без будь-яких засобів, крім написання матеріалів.
• Для досягнення успіху слід лише ^[en]дотримуватися його інструкцій. Іншими словами, це не вимагає ^[en].

Іноді також необхідно, щоб метод ніколи не приймав результат за відповідь, коли він застосовується до проблем, що не належать до його класу. Додавання цієї вимоги зменшує набір класів, для яких існує ефективний метод.

Алгоритми

Алгоритм — це ефективний методом для обчислення значень функції. Функції, для яких існує ефективний метод, іноді називають ефективно обчислюваними.

Обчислювальні функції

Кілька незалежних зусиль, щоб дати офіційну характеристику ефективного обчислення, призвели до різноманіття запропонованих визначень (зазальна рекурсія, машини Тюрінга, лямбда-числення), які раніше були еквівалентними. Отже, рекурсивна або ефективна обчислюваність — поняття, що зафіксоване цими визначеннями.

У тезі Черча сказано, що ці два поняття збігаються. Обчислювана функція  — це будь-яка арифметична функція, яка ефективно піддається підрахунку. Оскільки це не математичне твердження, його неможливо довести за допомогою математичного доказу.

Див. також

• Алгоритмічна розв'язність
• Проблема вибору
• (Функціональна проблема)
• ^[en]
• (Рекурсивний набір)
• Алгоритмічно нерозв'язна задача

Список літератури

1. , Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971
2. ; Copeland, Jack; Proudfoot, Diane (June 2000). . AlanTuring.net. Turing Archive for the History of Computing. Архів оригіналу за 27 березня 2013. Процитовано 23 березня 2013.
3. The Cambridge Dictionary of Philosophy, effective procedure

• S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, , pp. 233 ff., esp. p. 231.