Упражнение. 3.4. Докажите разрешимость следующих предикатов на множестве целых неотрицательных чисел:

3.4. Докажите разрешимость следующих предикатов на множестве целых неотрицательных чисел:

а) x = y;

б) ;

в) x < y;

г) x – четное число.

За последние пятьдесят лет было предложено много математических уточнений интуитивного понятия «алгоритм». Подход, основанный на МНР, является одним из них. Между этими подходами имеются большие различия, и в то же время все эти подходы эквивалентны между собой в том же смысле, что каждое уточнение алгоритма приводит к одному и тому же классу вычислимых функций.

Возникает теперь вопрос: насколько хорошо неформальное интуитивное понятие вычислимой функции отражено в различных формальных описаниях? Этот вопрос подвергался математиками серьезному обсуждению, в результате которого было высказано утверждение, известное под названием «тезис Черча»: каждая функция, вычислимая посредством процесса, алгоритмический характер которого интуитивно ясен, является вычислимой функцией. Применительно к нашему изложению этот тезис можно перефразировать следующим образом: всякая функция, для которой существует алгоритм (в интуитивном смысле) вычисления ее значений, является МНР-вычислимой функцией.

Сразу же заметим, что это утверждение не является теоремой, подлежащей математическому доказательству; оно имеет статус утверждения, принимаемого как постулат, справедливость которого подтверждается рядом свидетельств. Во-первых, таким свидетельством является то, что, как уже отмечалось, многие независимые уточнения интуитивного понятия вычислимой функции привели к одному и тому же классу функций. Во-вторых, никому не доводилось найти функцию, которую можно признать вычислимой в интуитивном смысле и которая не была бы МНР-вычислимой. Исходя из этих соображений и собственного опыта, большинство математиков приняли тезис Черча.