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

                      3. РЕКУРСИВНЫЕ ФУНКЦИИ


                         § 1. Элементарные функции.
               Правила подстановки и примитивная рекурсия


     Всякий алгоритм однозначно ставит в соответствие исходным дан-
ным (в случае если, он определен на них) результат. Поэтому с каждым ал-
горитмом однозначно связана функция, которую он вычисляет. Исследо-
вание проблемы остановки машины Тьюринга показывает, что не для вся-
кой функции существует вычисляющий ее алгоритм. Поэтому в 30-х годах
ХХ века была создана теория рекурсивных функций. В этой теории, как и
вообще в теории алгоритмов, принят конструктивный, финитный подход,
основной чертой которого является то, что все множество исследуемых
объектов (в нашем случае функции) строится из конечного числа исход-
ных объектов – базиса – с помощью простых операций, эффективная вы-
полнимость которых достаточно очевидна. Операции над функциями в
дальнейшем будем называть операторами.
     Пусть имеется некоторый алгоритм α. Областью применимости ал-
горитма α называют совокупность тех объектов, к которым он применим.
     Говорят, что алгоритм α вычисляет функцию f , если его область при-
менимости совпадает с областью определения функции f , и алгоритм α пе-
рерабатывает всякий элемент x из своей области применимости в f (x) .
     Американскими математиками Клини, а впоследствии Черчем были
строго определены математические функции, называемые примитивно-
рекурсивными. Черч высказал гипотезу о том, что множество всех рекурсив-
ных функций совпадает с множеством всех вычислимых функций. Это пред-
положение получило название тезиса Черча. Гипотеза Черча не может быть
доказана, поскольку использует нестрогое понятие вычислимой функции.

                                    25