Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 29 стр.

       f ( x,2) � h( x,1, f ( x,1)) � f ( x,1) � 1 � x � 2,
       f ( x, y ) � h( x, y � 1, f ( x, y � 1)) � x � y � 1 � 1 � x � y.
      Таким образом, построена функция (таблица ее значений), которая
равна сумме двух слагаемых.
      В дальнейшем, если нужно доказать примитивную рекурсивность
некоторой функции, можно использовать не только элементарные ре-
курсивные функции, но и те функции, примитивная рекурсивность кото-
рых уже доказана. Например, можно использовать функцию из выше
рассмотренного примера.
      Так как исходные функции являются всюду определенными и опе-
рации подстановки и примитивной рекурсии сохраняют всюду опреде-
ленность, то из определения примитивно-рекурсивной функции следует,
что каждая примитивно рекурсивная функция является всюду опреде-
ленной.

                § 2. Правило взятия μ-оператора. Классы функций

      Рассмотрим еще одну операцию, называемую �-оператором. Пусть
g ( x1 ,..., xn , y ) – произвольная числовая функция. Зафиксируем значения
x1 , x2 ,..., xn и через �y[ g ( x1 ,..., xn , y ) � 0] обозначим наименьшее число y
такое, что:
      1) для всех t , 0 � t � y , g ( x1 ,..., xn , t ) определено и больше нуля;
      2) g ( x1 ,..., xn , y ) определено и равно нулю.
Если же одно из этих условий не выполнено, т. е. для некоторого t
g ( x1 ,..., xn , t ) не определено или же не для всех z g ( x1 ,..., xn , z ) определено и
больше нуля, будем считать, что выражение �y[ g ( x1,..., xn , y ) � 0] не опре-
делено.



                                               29