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

     Позже американские математики Пост и впоследствии Тьюринг вве-
ли понятие математической машины, которую называют машиной Поста
или машиной Тьюринга (см. главу 1 «Машина Тьюринга»). Тьюринг вы-
сказал гипотезу (известную также как тезис Тьюринга) о том, что для вся-
кой вычислимой функции может быть построена машина Тьюринга. Этот
тезис также не может быть доказан, так как включает нестрогое понятие
вычислимой функции.
     Доказано, что для всякой рекурсивной функции может быть по-
строена машина Тьюринга и, обратно, всякая машина Тьюринга вычисляет
рекурсивную функцию.
     Известны также другие способы уточнения понятия алгоритма, на-
пример, нормальный алгоритм Маркова.
     Практический опыт показывает, что тезисы Черча и Тьюринга явля-
ются верными, не имеется ни одного опровержения этих утверждений.
     Дадим элементарное определение рекурсивных функций.
     Рекурсивные функции – это функции, определенные некоторым спе-
циальным образом. Из названия следует, что их вычисление содержит об-
ращение к самим себе (при меньших значениях аргументов). Подразумева-
ется, что рекурсивные функции являются арифметическими функциями,
т. е. область их определения и область значений является подмножеством
множества N 0 или совпадает с ним.
     Введем следующие правила для получения новых функций из уже
имеющихся, которые упоминались в разделе 2:
     1) нуль функция: o( x) � x при каждом x � N 0 ;
     2) функция следования: s ( x) � x � 1 при каждом x � N 0 ;        (3)

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

     при всех ( x1 , ..., x n ) � N 0n , m � 1, n , n � 1,2,3...


                                              26