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

                  2. ФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ

                                § 1. Описание класса функций

       С развитием науки и практики появились задачи, для которых не были
найдены методы их решения. Возник вопрос: отсутствие алгоритма решения
для данного класса задач есть результат недостаточного знания о задачах это-
го класса или решающего алгоритма для данного класса не существует?
       Для решения этой проблемы было введено понятие вычислимой
функции.
       Будем рассматривать функции               f   от одного или нескольких аргумен-
тов, заданные на множестве N 0 � {0,1,2,3,..., n,...} всех неотрицательных
целых чисел или на некоторых его подмножествах (частичные функции) и
принимающие значения в множестве N . Область определения Df функ-

ции f – это подмножество множества N 0n � N 0 � N 0 � ... � N 0 :

                  Df � {( x1 ,..., x n ) � N 0n : f ( x1 ,..., x n ) � N � определено}.

       Значение функции f ( x1 ,..., xn ) на наборе (m1 ,..., m n ) � N 0n определено,
если f (m1 ,..., mn ) � m , где m � N 0 , в противном случае функция f счита-
ется неопределенной на заданном наборе.
       Под числовыми функциями будем понимать функции, значениями ко-
торых и значениями их аргументов являются неотрицательные целые числа.
       Опишем класс числовых функций, совпадающий с множеством всех
вычислимых функций.
       Назовем исходными следующие числовые функции:
1) нуль-функция: o( x) � x при каждом x � N 0 ;
2) функция следования: s ( x) � x � 1 при каждом x � N 0 ;

3) функция выбора аргумента: I m( n ) ( x1 , x2 ,..., xn ) � xm при всех ( x1 , ..., x n ) � N 0n ,

m � 1, n , n � 1,2,3...
                                                19