ВУЗ:
Составители:
результату применения алгоритма Δ можно узнать, является ли заданный
алгоритм Г самоприменимым или нет.
Доказательство проведем от противного. Допустим, что алгоритм Δ
построен. Тогда путем некоторого изменения системы подстановок
алгоритма Δ можно построить новый алгоритм Δ′, который всякую запись
несамоприменимого алгоритма по-прежнему перерабатывает в слово L, а ко
всякой
записи самоприменимого алгоритма неприменим (остановка никогда
не наступает). Это приводит к противоречию. Действительно, если Δ′
самоприменим, то он применим к собственной записи в виде слова
(остановка наступает). Но по построению алгоритма Δ′ это свидетельствует
как раз о том, что Δ′ несамоприменим. Если же Δ′ несамоприменим, то по
построению он применим
к своей записи, так как он применим к любой
записи несамоприменимого алгоритма. Но это как раз означает, что Δ′
самоприменим.
Полученное противоречие показывает, что алгоритм Δ′ не может быть
построен. Отсюда вытекает, что проблема распознавания самоприменимости
алгоритмически неразрешима.
Итак, решая какую-либо задачу, приходится считаться с тем, что
алгоритм для
ее решения может существовать, а может и не существовать.
Поэтому важно как построение самого алгоритма, так и доказательство
невозможности его построения. Иначе говоря, есть такие проблемы, которые
нельзя решать только с помощью формальных рассуждений и вычислений и
которые требуют творческого мышления (интуиции, предвосхищения и так
далее).
В заключение раздела отметим
, что нормальные алгоритмы Маркова
являются хорошей моделью логических алгоритмов. Покажем, что любой
логический алгоритм можно свести к вычислительному, т.е. любую
алгоритмическую проблему можно свести к вычислению некоторой
целочисленной функции от целочисленных значений аргументов.
Страницы
- « первая
- ‹ предыдущая
- …
- 22
- 23
- 24
- 25
- 26
- …
- следующая ›
- последняя »
