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

(по времени) этих вычислений. В языках с ламбда-исчислением этого не нужно. Сама структура программы однозначно определяет опти­ мальное число параллельных ветвей вычислений. Тызначишь то,чтотынасамом деле. Надень парик смиль онами кудрей, Стань находули, новдуше своей Тыбудешь всетаким, каков тывсамом деле. И. В. Гете Самое непостижимое вэтом ирето, чтоонпостижим. А, Эйнштейн § 18. Основные результаты 1. Из теорем 6.5 и 6.6, следствий из них, а также теорем 6.11 и 6.12 следует, что класс частично рекурсивных функций совпадает с классом функций частично вычислимых по Маркову и классом час­ тично вычислимых по Тьюрингу функций. Более общее: с помощью детальных рассмотрений показано, что формализации, предложенные Тьюрингом, Марковым (нормальные алгоритмы), а также Клини (частично рекурсивные функции) и другими, эквивалентны, т.е. в каждом случае получается один и тот же класс функций. Всюду определенные функции, попадающие в этот класс, являются общерекурсивными функциями. Частичные функции этого класса совпадают с классом частичнорекурсивных функций. Согласно основной гипотезе теории алгоритмов (принцип нормализации) любой алгоритм вполне эквивалентен нормальному алгоритму. Тогда сово­ купность частично рекурсивных функций совпадает с совокупностью частичных функций, вычислимых посредством нормального алго­ ритма. 263