ВУЗ:
Составители:
В заключение раздела отметим, что понятия вычислимости и
рекурсивности эквивалентны. Понятие вычислимости ввел А. Тьюринг, а
понятие рекурсивности - С. Клини. Оба эти понятия, определенные их
авторами независимо друг от друга, были призваны формализовать
интуитивное представление о вычислимости. Примечательно, что все другие
понятия, введенные с той же целью также независимо друг
от друга
К.Геделем, А. Черчем, Э. Постом, А. Марковым, оказались эквивалентными
друг другу. Это позволило А. Черчу сформулировать свой знаменитый тезис
о том, что все введенные понятия правильно формализуют интуитивное
представление об алгоритме и вычислимости и что их нельзя обобщить.
Поэтому из всех эквивалентных определений можно выбрать одно,
отождествить его
с одним из точных определений и на основании последнего
строить некоторую теорию.
2.8. Комбинаторные системы и машины Тьюринга
Покажем, что можно построить машину Тьюринга, в которой любое
вычисление, приводящее к конечному результату, соответствует выводу
некоторой теоремы в комбинаторной системе и наоборот. Пусть имеется
некоторое входное слово n, заданное унарным
кодом n (см. раздел 2.2). Если
предложить машине Z в качестве исходного задания
n
, то начав вычисление
с конфигурации q
0
n, машина либо выдаст результат, либо будет работать
вечно. Будем считать, что Z заключает все промежуточные результаты
вычислений между двумя маркерами h. Паре (Z, n) поставим в соответствие
полутуэвскую систему П с аксиомой
hnhq
0
. Подстановки в П выберем таким
образом, чтобы ее промежуточные формулы соответствовали
промежуточным конфигурациям МТ Z, а заключительная формула hsh -
заключительной конфигурации МТ Z, означающей, что соответствующее
вычисление завершено.
Страницы
- « первая
- ‹ предыдущая
- …
- 42
- 43
- 44
- 45
- 46
- …
- следующая ›
- последняя »
