Эффективный метод
- Эффективный метод или процедура в логике, математике и информатике — это интуитивно «эффективный» метод решения задач из определенного класса.
- Определение эффективного метода включает рассмотрение его применимости к определенному классу задач.
- Один метод может быть эффективным для одного класса задач и неэффективным для другого класса.
- Формально эффективный метод для определенного класса задач должен удовлетворять определенным критериям.
- Алгоритмы являются эффективным методом вычисления значений функции.
- Несколько предложенных определений эффективной вычисляемости привели к появлению понятия рекурсивной или эффективной вычислимости.
- Тезис Черча-Тьюринга утверждает, что эти два понятия совпадают: любая теоретико-числовая функция, которая эффективно вычисляется, является рекурсивно вычислимой.
Полный текст статьи: