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

      Пример        8.   Пусть      дана     функция       g ( x, y) � x � y � 3 .   Тогда
�y[4 � y � 3 � 0] � 1, так как 4 � 0 � 3 � 1 � 0, 4 � 1 � 3 � 0 . �y[3 � y � 3 � 0] � 0 , а
�y[ g (0, y ) � 0] , �y[ g (1, y ) � 0] и �y[ g (2, y ) � 0] не определены, потому что
k � 0 � 3 , где k � 0,1,2 в области натуральных чисел не определено.
      Пусть f ( x1 ,..., xn ) � �y[ g ( x1 ,..., xn , y ) � 0] . В этом случае говорят, что

функция f получена из функции g с помощью �-оператора.
      Пример 9. Пусть f 1 ( x) � �y[4 � y � 3 � 0] , тогда f 1 ( x) получается из
g(x, y) � x � y � 3 с помощью � -оператора. Так функция g ( x, y ) � x � y � 3 не
является всюду определенной, то и значения f 1 (0) , f 1 (1) и f 1 (2) не опре-
делены.
      Пример 10. Функция f 2 ( y ) � �y[4 � y � 3 � 0] является нигде не оп-
ределенной, так как для любого натурального числа m в области нату-
ральных чисел 0 � m � 3 не определено. Значит с помощью � -оператора
получена нигде не определенная функция.
      Пример 11. Функция x � y не является всюду определенной (на-
пример, 0 � m не определено), но функция f 3 ( x) � �y[ x � y � 0] , получен-
ная из нее с помощью � -оператора, всюду определенная, причем для лю-
бого m : f 3 (m) � m (все разности m � 0 , m � 1, …, m � (m � 1) определены
и отличны от нуля, а m � m � 0 ). Таким образом, с помощью � -оператора
получена всюду определенная функция.
      Пример 12. Константная функция g 1 ( x, y ) � 5 всюду определена, а
функция f 4 ( x) � �y[ g 1 ( x, y ) � 0] нигде не определена.
      Определение. Функция называется частично рекурсивной, если она
может быть получена из исходных с помощью применения конечного чис-
ла раз подстановок, примитивных рекурсий и �-оператора. Всюду опреде-
ленная частично рекурсивная функция называется общерекурсивной.

                                            30