Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Основная гипотеза только утверждает (постулирует) универсальность понятия нормального алгоритма. Иначе можно сказать, что основной тезис применяется в теории алгоритмов только в рекламных целях: "Любой алгоритм можно представить как нормальный алгоритм". Основную гипотезу можно рассматривать как уточнение понятия любого алгоритма через более специальное, но строгое понятие нормального алгоритма (машины Тьюринга). § 12. Проблема алгоритмической неразрешимости Под массовой проблемой будем понимать бесконечное множество однотипных задач. Массовую проблему можно обозначать, например, через {Q j }, где Oj - некоторая единичная задача. Переход от расплывчатого понятия алгоритма к строгому определению специальных алгоритмов (нормальный алгоритм, или алгоритм Тьюринга) позволяет уточнить вопрос об алгоритмической разрешимости того или иного круга задач. Массовая проблема {aj} называется алгоритмически разрешимой, если суш,ествует алгоритм (нормальный алгоритм или алгоритм Тьюринга), позволяюш,ий решить каждую задачу этой массовой проблемы, и алгоритмически неразрешимой, если такого алгоритма не суш,ествует. Проблема алгоритмической (не)разрешимости формулируется следуюш,им образом: «каждая ли массовая проблема является алгоритмически разрешимой?» Эта проблема имеет свою историю. Еш,е великий математик и философ Лейбниц (1646-1716) мечтал о создании всеобш,его метода, позволяюш,его решать любую задачу. Хотя всеобщего алгоритма ему не удалось найти, Лейбниц считал, что наступит время, когда такой алгоритм будет найден. Несмотря на долгие и упорные усилия многих крупных специалистов, трудности остались непреодолимыми. Более того, были обнаружены большие трудности даже при попытке создания алгоритмов для некоторых массовых проблем частного вида (не говоря уже о любой задаче). В результате многочисленных, но безрезультатных попыток создания таких алгоритмов стало ясно, что налицо имеются трудности принципиального характера, и возникло сомнение, для каждого ли класса задач возможно построение решающего алгоритма. Оказалось, что для целого ряда массовых проблем невозможно построить разрешающий алгоритм, т.е. алгоритм, который позволил бы решить все задачи данной массовой проблемы. Первые результаты такого рода были обнаружены в математической логике в работах Геделя, Черча, Тьюринга. Ими были указаны (найдены) примеры алгоритмически неразрешимых массовых проблем. 165