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

Наоборот, если есть метод вычисления функгщи ф(«), то, стало быть, имеется и метод преобразования исходно!'о слова (предло­ жения). Действительно, по записи слова (предложения) можно найти соответствующий ему номер а , затем вычислить Р=ф(а) и по Р опре­ делить результирующее слово (предложение). Таким образом, всякое преобразование слов юш предложений алфавита А в слова или предложения тото же алфавита можно свести к вычислению значения некоторой функции, и наоборот. Ранее среди всевозможных преобразований с;юв алфавита пас интересовали преобразования, которые используют механическую процедуру, т.е. преобразования с помощью алгоритмов. В следую­ щем параграфе займемся изучением функций, значения которых вычисляются с помощью некоторых "механических" процедур, и уста­ новим связь с вычислимостью при помощи нормальных алг'оритмов. § 15. Примитивно-рекурсивные и общерекуршвпые функции Рекурсивное определение функции ~ это, грубо говоря, опреде­ ление, в котором значения функции для да1П1Ых аргументов непо­ средственно определяются значениями этой же функции для "более простых" аргументов или значениями "более простых" функций. (Понятое "более простой" следует уточнить: например, нростейп1ей функцией можно считать функцию-константу). Такой гюдход к рас­ смотрению функций удобен тем, что регсурсивные определения можно рассматривать ка1с алгоритмы. Здесь, как и при определении вычислимости по Маркову или Тьюрингу, будем рассматривать только арифметические фупкгщи. Теперь приступим к строг-ому определению примитивно- рекурсивных и обя;ерекурсивных функций. 253