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

сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать суш,ествование разрешаюш,его алгоритма - это можно сделать, используя интуитивное понятие алгоритма. Другое дело - доказать несуш,ествование алгоритма - для этого нужно знать точно - что такое алгоритм. Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса с помош,ью нормального алгоритма или машины Тьюринга. Был сформулирован тезис (тезис Черча), утверждаюш,ий, что любой алгоритм может быть реализован с помош,ью нормального алгоритма или на подходящей машине Тьюринга. Разные подходы привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Черча для решения алгоритмических проблем. Поскольку понятие рекурсивной функции строгое, то с помош,ью обычной математической техники можно доказать, что решаюш,ая некоторую задачу функция не является рекурсивной, что эквивалентно отсутствию для данной задачи разрешаюш,его алгоритма. Аналогично, несуш,ествование разрешаюш,ей машины Тьюринга для некоторой задачи равносильно отсутствию для нее разрешаюш,его алгоритма. Указанные результаты составляют основу проблемы алгоритмической (не)разрешимости, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости. В настояш,ее время теория алгоритмов образует теоретический фундамент вычислительных наук. Применение теории алгоритмов осуш,ествляется как в использовании самих результатов (особенно это касается использования разработанных алгоритмов), так и в обнаружении новых понятий и уточнении старых. С ее помош,ью проясняются такие понятия как доказуемость, эффективность, разрешимость и другие. Известные советские математики Успенский В. А. и Семенов А. Л. в обзоре основных достижений теории алгоритмов пишут: ''Алгоритмические концепции играют е процессе обучения и воспитания современного человека фундаментальнуюроль, сравнимую лишь с ролью письменности'". Также важным является приложение раздела теории алгоритмов, именно, ламбда-исчисления к программированию. Пожалуй, наиболее продуктивной формализацией понятия «функция» стала математическая теория, известная сегодня под названием ламбда-исчисления. Практически все ранее созданные формализации языков функционального программирования (включая абстрактные машины и средства оптимизации вычислений) базируются на фундаменте ламбда-исчисления в той или иной его форме. Ламбда-исчисление 177