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

не требуется, чтобы для Vxi,Vx2,...,Vx „ существовал у такой, что g(xi,x2,.-.,x „,y)=0, т.е. при некоторых значениях Х\,Хъ.--,х„ может и не существовать у такого, что g (XBX2 ,...,X „,y)=0. Очевидно, что всякая общерекурсивная функция является частично рекурсивной, но не наоборот. Можно доказать следующие важные теоремы. Теорема 6.11. Всякая частично-рекурсивная функция (общере­ курсивная) является частично вычислимой (вычислимой) по Маркову функцией. Теорема 6.12. Всякая частичная функция, частично вычис­ лимая (вычислимая) по Маркову, является частично-рекурсивной (общерекурсивной) функцией. § 17. Ламбда-исчисление Прежде чем ввести ламбда-исчисление, укажем возможную область ее использования в вычислительных моделях. Различают следующие вычислительные модели: императивную (процедурную) вычислительную модель (импе­ ратив — повеление, требование), когда имеется последовательная еистема команд. Языки программирования, такие как АЛГОЛ, ФОРТРАН, С и т.п. основываются на этой вычислительной модели и объединяются под названием императивные или процедурные языкй; логическиевычислительные модели, основанные на вычисле­ ниях с помощью логики предикатов. Примеры таких языков ПРОЛОГ, ДЕЙТАЛОГ; функциональные вычислительные модели, в которых програм­ ма рассматривается как множество определений функций.. В основу 259