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

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