Задача разрешимости: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
мНет описания правки |
→Преамбула: стилевые правки |
||
Строка 3:
Например, проблема ''«даны два числа: ''<math>x</math> и <math>y</math>''; делится ли ''<math>x</math>'' на ''<math>y</math>''?»'' является проблемой разрешимости. Ответ может быть дан либо «да», либо «нет» и зависит от значений <math>x</math> и <math>y</math>. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы из примера выше должна определять совокупность действий, которые следует предпринять для проверки делимости нацело <math>x</math> на <math>y</math> для данных чисел. Один из таких алгоритмов — [[деление столбиком]] — изучается в начальной школе. Остаток, равный нулю, означает ответ «да», в противном случае — «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.
Не все математические задачи могут быть сформулированы как проблемы разрешимости. Вычисление [[Умножение|произведения]] двух чисел, поиск наиболее быстрого алгоритма умножения чисел и [[Оптимизация (математика)|оптимизационные задачи]], в частности [[задача коммивояжёра]] в классической постановке, не являются проблемами разрешимости, поскольку их невозможно сформулировать так, чтобы
Исследования в области [[теория рекурсии|теории рекурсии]] часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.
| |||