Определение. Предикат M(x) называется разрешимым, если его характеристическая функция, задаваемая формулой
cM(x) = 1, если M(x) истинно;
cM(x) = 0, если M(x) ложно
вычислима.
Определение. Предикат M(x) называется неразрешимым, если он не является разрешимым. В контексте разрешимости предикаты часто называются проблемами.
Имея точное определение вычислимости, удалось доказать, что некоторые проблемы неразрешимы.
· Теорема Черча о неразрешимости логики предикатов. Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.
· Проблема остановки неразрешима [13, с. 108]. Не существует никакого общего алгоритма, позволяющего установить, остановится ли некоторая конкретная программа (на любом языке программирования), запущенная после введения в неё некоторого конкретного набора данных. Смысл этого утверждения для теоретического программирования очевиден: не существует совершенно общего метода проверки программ на наличие в них бесконечных циклов. В терминах ламбда-исчисления утверждение о неразрешимости проблемы остановки можно сформулировать в таком виде: "Не существует алгоритма, с помощью которого можно было бы узнать имеет ли данное ламбда-выражение нормальную форму или нет".
· Не существует никакого общего алгоритма, позволяющего установить, вычисляет ли некоторая конкретная программа (на любом языке программирования) постоянную нулевую функцию [13, с. 110]. То же самое справедливо и для любой другой конкретной вычислимой функции. И как следствие, можно утверждать, что вопрос о том, вычисляют ли две данные программы одну и ту же одноместную функцию, также неразрешим. Тем самым, мы получаем, что в области тестирования компьютерных программ, мы имеем принципиальные ограничения.
Диофантовы уравнения [13, с. 114]. Современная математика вообще изобилует разрешимыми и неразрешимыми проблемами. Одна из проблем связана с диофантовыми уравнениями.
Пусть p(x1, x2,..., xn) - многочлен от переменных x1, x2,..., xn с целыми коэффициентами. Тогда уравнение
p(x1, x2,..., xn) = 0,
для которого мы ищем только целые решения называется диофантовым уравнением. Диофантовы уравнения не обязательно имеют решения. Например, не имеет решения уравнение x2-2 = 0.
Десятая проблема Гильберта, сформулированная в 1900 году, состоит в том, чтобы установить, существует ли алгоритм, с помощью которого можно было бы проверить, имеет ли данное диофантово уравнение решение. В 1970 году советский математик Ю. Матиясевич доказал, что такого алгоритма не существует. Доступное доказательство этого можно найти в [21].
Отметим также, что знаменитую теорему Гёделя о неполноте можно легко доказать, используя теорию алгоритмов. Элементарное доказательство этого приведено в [31]. Занимательному изложению вопросов вычислимости, вплоть до получения доказательства теоремы Гёделя, посвящена книга Р. Смаллиана [28].