Cтраница 2
Эти рекурсивные равенства имеют вид примитивной рекурсии. [16]
Следовательно, она определяется через примитивную рекурсию. [17]
Эти соотношения являются естественным обобщением схемы примитивной рекурсии. Нетрудно показать, что данные функции могут быть получены из функций i / / j, ф, Ф3, Q с помощью примитивной рекурсии и суперпозиции. [18]
Доказать, что, применяя оператор примитивной рекурсии к общерекурсивным функциям, мы получим общерекурсивную функцию. [19]
Этому словесному предписанию можно придать вид одновременной примитивной рекурсии, которая приведена ниже. Предварительно введем некоторые обозначения. [20]
Эта рекурсия тоже может быть сведена к примитивной рекурсии. [21]
Общее правило, позволяющее допускать рекурсивные равенства любых примитивных рекурсий в качестве исходных формул выводов, называется схемой примитивной рекурсии. [22]
Таким образом, любая функция, получаемая примитивной рекурсией из Рекурсивных функций, сама Рекурсивна. [23]
И хотя эта рекурсия не является ни примитивной рекурсией, ни рекурсией пробега, ее можно ( тем же самым приемом, что и рекурсию пробега) свести к примитивной рекурсии. [24]
Функцию, рекурсивное определение которое дается некоторой примитивной рекурсией или последовательностью примитивных рекурсий, мы кратко называем рекурсивной функцией. [25]
Суть этого доказательства состоит в том, что примитивные рекурсии обобщенной арифметики переходят в возвратные рекурсии обыкновенной арифметики, ибо геделев-ская нумерация сохраняет отношение порядка, хотя и нарушает отношение непосредственного следования. [26]
Добавив к элементарному исчислению со свободными переменными схему примитивной рекурсии и схему индукции вместе с аксиомами равенства и аксиомой 0 О, мы получим формализм рекурсивной арифметики. [27]
Имеются ли рекурсии, которые не сводимы к примитивной рекурсии, в частности, может ли рекурсия быть использована для определения функ-ции, не являющейся примитивно-рекурсивной. [28]
Рассмотрим лишь случай получения функции с помощью оператора примитивной рекурсии. [29]
Первые два равенства из (2.1) образуют обычную схему примитивной рекурсии. [30]