Cтраница 3
Такая граница для функции, определенной при помощи примитивной рекурсии, была введена еще Гжегорчиком [3] в понятии ограниченной рекурсии. [31]
Другое отличие заключается в том, что тыорингово программирование примитивной рекурсии основано на повторном ( можно сказать - циклическом) применении исходной программы. [32]
Оно является примером рекурсивного определения, не сводящегося к примитивной рекурсии. [33]
Покажем теперь, что класс & замкнут относительно операции примитивной рекурсии, при условии что мы заранее знаем элементарную границу для функции, определенной уравнением рекурсии. [34]
Число рекурсий, используемых для определения функции в схеме примитивной рекурсии, нельзя использовать в качестве сигнализирующих функций, так как этими схемами невозможно задать все частично рекурсивные функции, и, таким образом, мы не имеем допустимой нумерации всех алгоритмов. [35]
Легко проверить, что это определение - конкретизация схемы примитивной рекурсии. [36]
Дважды рекурсивная функция, которая не может быть определена только примитивными рекурсиями и подстановками. [37]
Суть доказательства состоит в том, что явные определения и примитивные рекурсии остаются таковыми и после введения, параметров. [38]
Наша ближайшая цель - описать операторы трех типов - простейшие, примитивной рекурсии и - оператор - и показать, что класс вычислимых функций замкнут относительно этих операторов. [39]
При построении произвольной рекурсивной функции из базисных с помощью композиции, примитивной рекурсии и минимизации операция минимизации может быть использована не более одного раза. [40]
Функцию, рекурсивное определение которое дается некоторой примитивной рекурсией или последовательностью примитивных рекурсий, мы кратко называем рекурсивной функцией. [41]
Точнее, эта схема определяет f ( n, а) примитивной рекурсией, исходя из функций а и р В качестве исходных примитивно рекурсивных функций мы берем функцию следования S ( x) t тождественную функцию / (), явно определяемую равенством 1 ( х) х, и нулевую функцию Z ( x), определяемую равенством Z ( x) Q. Говорят, что функция является примитивно рекурсивной, если она исходная или определяется с помощью подстановки или примитивной рекурсии из уже определенных примитивно рекурсивных функций. [42]
Таким образом, оба эти понятия тоже могут быть определены с помощью примитивной рекурсии. [43]
Отсюда следует, что если функции fug МНР-вычислимы, то определяемая через примитивную рекурсию функция тоже МНР-вычислима. [44]
Используя данные функции в качестве исходных, путем применения простых операций суперпозиции, примитивной рекурсии и минимизации можно получить любую сколь угодно сложную числовую функцию. [45]