Задача разрешимости: различия между версиями

Например, проблема ''«дано два числа ''x'' и ''y'', делится ли ''x'' на ''у''?»'' является проблемой разрешимости. Ответ может быть дан либо «да» либо «нет» и зависит от значений ''x'' и ''y''. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы разрешимости ''«дано два числа ''x'' и ''y'', делится ли нацело ''x'' на ''у''?»'' должна определять совокупность действий, которые следует предпринять для проверки делимости нацело ''x'' на ''у'' для данных ''x'' и ''y''. Один из таких алгоритмов [[деление столбиком]] изучается в начальной школе. Остаток равный нулю означает ответ «да», иначе «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.