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

вычислений. В языках с ламбда-исчислением этого не нужно. Сама структура программы однозначно определяет оптимальное число параллельных ветвей вычислений. § 16. Основные результаты 1. Из теорем 5.5, 5.6, следствий из них, а также теорем 5.11 и 5.12 следует, что класс частично рекурсивных функций совпадает с классом функций частично вычислимых по Маркову и классом частично вычислимых по Тьюрингу функций. Более общее: с помощью детальных рассмотрений показано, что формализации, предложенные Тьюрингом, Марковым (нормальные алгоритмы), а также Клини (частично рекурсивные функции) и другими, эквивалентны, т.е. в каждом случае получается один и тот же класс функций. Всюду определенные функции, попадающие в этот класс, являются общерекурсивными функциями. Частичные функции этого класса совпадают с классом частично рекурсивных функций. Согласно основной гипотезе теории алгоритмов (принцип нормализации) любой алгоритм вполне эквивалентен нормальному алгоритму. Тогда совокупность частично рекурсивных функций совпадает с совокупностью частичных функций, вычислимых посредством нормального алгоритма. 2. Изучалось обширное множество конкретных функций, интуитивно алгоритмических. Все они оказались частично рекурсивными функциями, т.е. были найдены наборы инструкций для них в какой-нибудь стандартной формализации (нормальные алгоритмы или Тьюринговская схема). 3. Доказательство указанных результатов обладает следующей общей структурой. В каждом случае тот факт, что один формализованный класс функций содержится в другом, доказывается предъявлением и обоснованием однообразной процедуры, согласно которой для любого набора инструкций J одной формализации указывается набор инструкции J' другой формализации, приводящей к той же функции. Эта единообразная процедура оказывается в каждом случае алгоритмической (в неформальном смысле этого слова). Вплоть до 30-х годов 20-го столетия понятие алгоритма считалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Были известны многие алгоритмы для решения конкретных задач. Среди них алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем и ряд других алгоритмов. Указанные алгоритмические проблемы решены путем построения конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале XX в. были 176