![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
3.4. Докажите разрешимость следующих предикатов на множестве целых неотрицательных чисел:
а) x = y;
б) ;
в) x < y;
г) x – четное число.
За последние пятьдесят лет было предложено много математических уточнений интуитивного понятия «алгоритм». Подход, основанный на МНР, является одним из них. Между этими подходами имеются большие различия, и в то же время все эти подходы эквивалентны между собой в том же смысле, что каждое уточнение алгоритма приводит к одному и тому же классу вычислимых функций.
Возникает теперь вопрос: насколько хорошо неформальное интуитивное понятие вычислимой функции отражено в различных формальных описаниях? Этот вопрос подвергался математиками серьезному обсуждению, в результате которого было высказано утверждение, известное под названием «тезис Черча»: каждая функция, вычислимая посредством процесса, алгоритмический характер которого интуитивно ясен, является вычислимой функцией. Применительно к нашему изложению этот тезис можно перефразировать следующим образом: всякая функция, для которой существует алгоритм (в интуитивном смысле) вычисления ее значений, является МНР-вычислимой функцией.
Сразу же заметим, что это утверждение не является теоремой, подлежащей математическому доказательству; оно имеет статус утверждения, принимаемого как постулат, справедливость которого подтверждается рядом свидетельств. Во-первых, таким свидетельством является то, что, как уже отмечалось, многие независимые уточнения интуитивного понятия вычислимой функции привели к одному и тому же классу функций. Во-вторых, никому не доводилось найти функцию, которую можно признать вычислимой в интуитивном смысле и которая не была бы МНР-вычислимой. Исходя из этих соображений и собственного опыта, большинство математиков приняли тезис Черча.
Дата публикования: 2015-03-26; Прочитано: 553 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!