Математическая логика и теория алгоритмов

были придуманы в течение многих тысячелетий, могут быть заданы посредством нормального алгоритма (машины Тьюринга). Имеются и другие соображения, подтверждающие правильность основной гипотезы. В § 6 данной главы были рассмотрены различные операции над нормальными алгоритмами (аналогичные операции можно рас­ смотреть и для алгоритмов (машин) Тьюринга), причем каждый раз оказывалось, что результирующий алгоритм снова является нормаль­ ным алгоритмом. Заметим, что внутри самой теории алгоритмов основная гипо­ теза не применяется. В теории алгоритмов исследуется нормальный алгоритм, машина Тьюринга, машины Поста и т.п., устанавливается связь между ними и т.д. Основная гипотеза только утверждает (посту­ лирует) универсальность понятия нормального алгоритма. Иначе можно сказать, что основной тезис применяется в теории алгоритмов только в рекламных целях: "Любой алгоритм можно представить как нормальный алгоритм". Основную гипотезу можно рассматривать как уточнение поня­ тия любого алгоритма через более специальное, но строгое понятие нормального алгоритма (машины Тьюринга). Никогда не бывает больших дел без больших трудностей. Ф. Вольтер § 12. Проблема алгоритмической неразрешимости Под м а с с о в о й п р о б л е м о й будем понимать бесконечное мно­ жество однотипных задач. Массовую проблему можно обозначать, например, через {aj}, где Оу- некоторая единичная задача. Переход от расплывчатого понятия алгоритма к строгому опре­ делению специальных алгоритмов (нормальный алгоритм, или алго­ ритм Тьюринга) позволяет уточнить вопрос об алгоритмической разреш;имости того или иного круга задач. 245