доказать что функция примитивно рекурсивная

Примитивно рекурсивные функции

Содержание

Рекурсивные функции [ править ]

Строительные блоки рекурсивных функций [ править ]

Рассмотрим примитивы, из которых будем собирать выражения:

Определение:

Если некоторая функция [math]\mathbb^ \rightarrow \mathbb[/math] может быть задана с помощью данных примитивов(англ. primitive), то она называется рекурсивной (англ. recursive).

Примитивно рекурсивные функции [ править ]

Определение:

Тотальность (англ. Total Function) — функция, определенная для всех возможных входных данных.

Благодаря проекторам мы можем делать следующие преобразования:

Арифметические операции на примитивно рекурсивных функциях [ править ]

n-местный ноль [ править ]

[math] \textbf 0 [/math] — функция нуля аргументов.

[math] \textbf 0^<1>(y) = \mathrm(y) [/math]

[math] \textbf 0^(x_1,\ldots,x_,y) = \mathrm(y) [/math]

Константа [math] \textbf M [/math] [ править ]

Сложение [ править ]

[math] \mathrm(x) = x [/math]

[math] \mathrm(x, y, z) = \mathrm(z) [/math]

[math] \mathrm\langle<>\mathrm,\mathrm\rangle (x,y) = \left\<\begin \mathrm(x) & y = 0\\ \mathrm(x, y-1,\mathrm\langle<>\mathrm,\mathrm\rangle(x, y-1)) & y \gt 0 \end\right.[/math]

[math]=\left\ <\begin x & y = 0\\ \mathrm(\mathrm \langle<>\mathrm,\mathrm\rangle(x, y-1)) & y \gt 0 \end\right.[/math]

[math]=\left\ <\begin x & y = 0\\ \mathrm(\mathrm(x, y-1)) & y \gt 0 \end\right. [/math]

Можно преобразовать в более простой вид.

[math] \mathrm(x,0) = x [/math]

[math] \mathrm(x,y) = \mathrm (\mathrm(x,y-1)) [/math]

Умножения [ править ]

[math] \mathrm(x,0) = \mathrm(x) [/math]

Вычитания [ править ]

[math] \mathrm(0) = \mathrm(0) [/math]

[math] \mathrm(x+1) = x [/math]

Теперь рассмотрим [math] \mathrm_{(x,y) [/math]}

[math] \mathrm_{(x,0) = x [/math]}

Операции сравнения [ править ]

Сначала выразим [math] \mathrm>(x) = \mathrm(x,0) [/math]

[math] \mathrm(0) =\mathrm(0) [/math]

Теперь все остальные функции

[math] \mathrm(x,y) = \mathrm(\mathrm(x,y),\mathrm(y,x)) [/math]

Условный оператор [ править ]

[math] \mathrm(0,x,y) = y [/math]

[math] \mathrm(c,x,y) = x [/math]

Деление [ править ]

Теперь само деления

[math] \mathrm(0,y) = \mathrm(y) [/math]

Остаток от деления выражается так:

Работа со списками фиксированной длины [ править ]

Теоремы [ править ]

Теорема о примитивной рекурсивности вычислимых функций [ править ]

[math] \mathrm([L,R,S,C],t) = [L,R,S,C] [/math]

Источник

Примитивно-рекурсивные функции

Пусть заданы функции:

Соотношения (1) и (2) называются схемой примитивной рекурсии. Соотношение (1) задает граничное условие, а соотношение (2) рекурсивно выражает значения функции f через другое значение этой функции.

Предположим, что функции g и h являются вычислимыми. В этом случае функция f также является вычислимой.

2. Используя соотношение (2) и алгоритм вычисления функции h, можно последовательно вычислить значения

ОПРЕДЕЛЕНИЕ

Функции, получаемые из простейших функций с помощью конечного числа применений операций суперпозиции и примитивной рекурсии, называются примитивно-рекурсивными.

Из приведенного определения следует, что всякая примитивно-рекурсивная функция является всюду определенной функцией. Кроме того, все примитивно-рекурсивные функции вычислимы.

Упражнение. Показать, что если f(x₁, x₂) является примитивно-рекурсивной функцией, если она выражается через примитивно-рекурсивные функции g и h с помощью соотношений

f(0, x) = g(x); (1)

f(y+1, x) = h(x, y, f(y, x)). (2)

Доказательство справедливости приведенного в упражнении утверждения обосновывать примитивную рекурсивность функций, определяемых рекурсивными схемами, в которых рекурсия ведется по произвольной переменной.

Рассмотрим примеры примитивно-рекурсивных функций.

1. Сумма f(x, у) = x + у задается следующей схемой примитивной рекурсии:

f(x, 0) = (x);

f(x, у+1) = S(f(x, у)).

2. Произведение p(x, у) = x ´ у задается схемами:

p(x, 0) = O(x);

p(x, у+1) = x+ p(x, у).

Здесь p выражается через функции O(x) и f( (x₁, x₂, x₃), ( x₁, x₂, x₃)), где f — это примитивно-рекурсивная функция из предыдущего примера.

3. Экспонента e(x) = 2 x может быть задана соотношениями:

e(0) = S(0);

e(x+1) = 2×e(x).

Функции S(0(y)) и 2y — примитивно-рекурсивные. Поэтому функция e(x) также является примитивно-рекурсивной.

4. Функции sg(x) и (x), определяемые как:

sg(x) = и (x) = , задаются следующими схемами:

sg(0) = 0; (x) = 1;

sg(x+1) = 1. (x+1) = 0.

d(0) = 0;

d(x+1) = x.

m (x, 0) = x;

m (x, у+1) = d(m(x, у)).

Функции из примеров 5 и 6 являются аналогами арифметического вычитания для множества целых неотрицательных чисел. Такие функции по определению равны нулю, если вычитаемое больше уменьшаемого.

Используя приведенные ранее функции, можно доказывать примитивную рекурсивность и других известных числовых функций.

Например, рассмотрим функцию mod(x,y), принимающую значение, равное остатку от деления числа x на число y.

Для определенности положим, что при делении на нуль остаток всегда равен 0.

Определим mod(x, y) схемой:

mod(0, y) = 0; (1)

Здесь рекурсия ведется по первой переменной.

В соотношении (2) реализовано очевидное свойство остатка от деления значения x+1 на y, которое можно выразить следующим соотношением:

mod(x+1, y) либо равен mod(x, y)+1, если mod(x, y)

Аналогичными соотношениями можно выразить функцию для целочисленного деления div(x, y).

Для определенности будем считать, что div(x, 0) = x, поскольку функция целочисленного деления не является всюду определенной.

div(0, y) = 0;

div(x+1, y) = div(x, y)+ (y-(mod(x, y)+1)).

Например, для функцииmod(x, y) необходимо образовать вспомогательную функциюg(x, y)= mod( (x, y), (x, y)). Такая функция может быть выражена с помощью схемы примитивной рекурсии.

Поэтому mod также является примитивно-рекурсивной функцией, поскольку получается из примитивно-рекурсивной функции g обратной перестановкой переменных.

При обосновании примитивной рекурсивности некоторых функций могут оказаться полезными свойства, доказываемые в следующих теоремах.

ТЕОРЕМА 8.1

Доказательство

Очевидно, что функция f может быть задана следующей схемой примитивной рекурсии:

Источник

Рекурсивные функции

Примитивно рекурсивные множества

Будем называть множество примитивно рекурсивным, если его характеристическая функция примитивно рекурсивна. (Вариант: если оно является множеством нулей примитивно рекурсивной функции ; это то же самое, так как можно сделать подстановку в функцию .)

Пересечение и объединение примитивно рекурсивных множеств примитивно рекурсивны (сложим или перемножим функции, множествами нулей которых они являются). Дополнение примитивно рекурсивного множества примитивно рекурсивно. Отождествляя множества со свойствами, можно сказать, что конъюнкции, дизъюнкции и отрицания примитивно рекурсивных свойств будут примитивно рекурсивны.

Свойства x=y и примитивно рекурсивны ( x=y тогда и только тогда, когда ).

Теперь можно записать формулу для прибавления единицы по модулю n (для чисел, меньших n ):

После этого функцию x mod n ( остаток от деления на n ) можно определить рекурсивно:

Покажем, что ограниченные кванторы, примененные к примитивно рекурсивным свойствам (множествам ), дают снова примитивно рекурсивные свойства. Это означает, например, что если свойство R(x,y) примитивно рекурсивно, то свойства

А произведение легко определить рекурсивно:

с суммированием можно поступить аналогичным образом.

а суммирование можно ограничить сверху выражением g(x) и воспользоваться примитивной рекурсивностью ограниченной суммы.

Другие виды рекурсии

Мы приведем два примера последнего типа: совместное определение нескольких функций и использование произвольных меньших значений аргумента.

Совместная рекурсия. Пусть две одноместные функции f и g заданы соотношениями:

где a и b некоторые числа, а функции F и G примитивно рекурсивные функции трех аргументов. Покажем, что тогда функции f и g примитивно рекурсивны.

Чтобы доказать это, нам потребуется примитивно рекурсивная нумерация пар такая функция (номер пары мы обозначаем квадратными скобками), которая была бы примитивно рекурсивна вместе с двумя обратными функциями (дающими по номеру пары ее первый и второй члены). Тогда мы сможем написать рекурсивное определение для функции h(n)=[f(n),g(n)] :

где функции p₁ и p₂ дают по номеру пары первый и второй ее члены. Если функция h примитивно рекурсивна, то и функции f и g (композиции h с функциями p₁ и p₂ ) также примитивно рекурсивны.

Заметим в заключение, что аналогичная конструкция применима для большего числа одновременно определяемых функций и для функций от большего числа аргументов.

Все эти функции (и другие аналогичные) сводятся к различным операциям с простыми числами и множителями, которые мы в сущности уже разбирали.

Теперь мы докажем, что функция

Источник

Доказать что функция примитивно рекурсивная

Как нам известно, предикатом называют логическую функцию определенную на заданном множестве объектов. Будем рассматривать в качестве области определения предиката конечный набор, состоящий из натуральных чисел. Таким образом, рассматриваемые предикаты представляют логические функции вида:

В качестве примера предикатов можно привести следующие логические функции:

;
;
.

(17)

По определению операции примитивной рекурсии получаем, что:

Следовательно, ПРО данной функции является последовательность функций:

Функция f(x,y) = |x-y| определяется следующим образом:

(19)

Прежде чем доказать, что функция f(x,y) = |x-y| является примитивно рекурсивной, рассмотрим следующие функции:

1) (20)
2) (21)

1) Рассмотрим функцию (20). По определения операции примитивной рекурсии получаем, что

Следовательно, ПРО для данной функции является последовательность функций:

2) Рассмотрим теперь функцию (21). По определения операции примитивной рекурсии получаем, что:

Исходя из последнего примера, функцию (19), будем представлять следующим образом:

Теперь можно говорить, что выбранная представляющая функция (18), т.е. φ 1 (x) = sg|x-y| для предиката p 1 (x,y) = (x=y) является ПРФ и удовлетворяет исходным условиям, т.е.

Для предиката p 2 (x,y) = (x в качестве представляющей функции можно брать

Тогда нетрудно проверить, что следующие функции являются представляющими функциями для соответствующих логических операций относительно предикатов, представленных в таблице 1:

(23)
(24)
(25)
(26)

В качестве упражнения, проверьте самостоятельно, что представленные функции действительно удовлетворяют требуемому условию как представляющие функции предиката.

Источник

Алгоритмы: частично рекурсивные функции

Леммы о рекурсивных функциях

Лемма 8.1. Рекурсивность табличных функций. Пусть всюду определенная функция f(x) на всех аргументах, кроме конечного числа, равна некоторой константе c (такую функцию назовем табличной). Тогда она является примитивно рекурсивной.

При n_f=0 функция f является постоянной и поэтому примитивно рекурсивной (пример 8.1).

и, следовательно, также примитивно рекурсивна.

Покажем замкнутость класса ч.р.ф. (п.р.ф.) относительно операций суммирования и произведения.

Доказательство Действительно, эти функции задаются следующими примитивно рекурсивными схемами:

Приведем примеры использования леммы 8.2.

и, следовательно, является примитивно рекурсивной.

Доказательство Действительно, g n можно представить как сумму k произведений:

Определим теперь по индукции функции c_n нумерации n-ок чисел при n > 2 и обратные им координатные функции c_ni (1 :

Лемма 8.4. Рекурсивность нумерационных функций. Для любых n >= 2 и 1 все определенные выше функции c_n и c_ni являются примитивно рекурсивными.

(1 также являются пpимитивно pекypсивными.

Фyнкция F n+1 полyчена пpимитивной pекypсией из пpимитивно pекypсивных фyнкций и, следовательно, сама пpимитивно pекypсивна. Спpаведливость леммы тепеpь следyет из того, что для всякого .

Задачи

предикаты равенства и неравенства:

Задача 8.5. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) ( элементы последовательности F(x) называются числами Фибоначчи). Покажите, что функция F(x) примитивно рекурсивна.

(Указание: покажите сначала, что функция g(x)= 2 F(x) 3 F(x+1) примитивно рекурсивна.)

Задача 8.6. Докажите, что если значения общерекурсивной функции f(x) изменить на конечном множестве, то получившаяся функция f ‘ (x) также будет общерекурсивной.

Источник