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

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

Содержание

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

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

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

Определение:
Если некоторая функция [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]

Источник

Операция примитивной рекурсии

Как доказать что функция примитивно рекурсивная. dark fb.4725bc4eebdb65ca23e89e212ea8a0ea. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-dark fb.4725bc4eebdb65ca23e89e212ea8a0ea. картинка Как доказать что функция примитивно рекурсивная. картинка dark fb.4725bc4eebdb65ca23e89e212ea8a0ea. Как доказать что функция примитивно рекурсивная. dark vk.71a586ff1b2903f7f61b0a284beb079f. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-dark vk.71a586ff1b2903f7f61b0a284beb079f. картинка Как доказать что функция примитивно рекурсивная. картинка dark vk.71a586ff1b2903f7f61b0a284beb079f. Как доказать что функция примитивно рекурсивная. dark twitter.51e15b08a51bdf794f88684782916cc0. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-dark twitter.51e15b08a51bdf794f88684782916cc0. картинка Как доказать что функция примитивно рекурсивная. картинка dark twitter.51e15b08a51bdf794f88684782916cc0. Как доказать что функция примитивно рекурсивная. dark odnoklas.810a90026299a2be30475bf15c20af5b. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-dark odnoklas.810a90026299a2be30475bf15c20af5b. картинка Как доказать что функция примитивно рекурсивная. картинка dark odnoklas.810a90026299a2be30475bf15c20af5b.

Как доказать что функция примитивно рекурсивная. caret left.c509a6ae019403bf80f96bff00cd87cd. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-caret left.c509a6ae019403bf80f96bff00cd87cd. картинка Как доказать что функция примитивно рекурсивная. картинка caret left.c509a6ae019403bf80f96bff00cd87cd.

Как доказать что функция примитивно рекурсивная. caret right.6696d877b5de329b9afe170140b9f935. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-caret right.6696d877b5de329b9afe170140b9f935. картинка Как доказать что функция примитивно рекурсивная. картинка caret right.6696d877b5de329b9afe170140b9f935.

Будем говорить, что (n+1) – местная функция f получается из n – местной функции g и (n+2) – местной функции h с помощью операции примитивной рекурсии, если при любых значениях x1, x2,…, xn выполняются равенства:

Эти равенства называют схемой примитивной рекурсии. И тот факт, что функция f получается из функций g, h c помощью операции примитивной рекурсии, записывается следующим образом: f=R(g,h).

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

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

Множество всех примитивно рекурсивных функций обозначим через Pn.p.

Пример 5 Доказать, что функция f(x,y)= x+y примитивно рекурсивна.

Действительно. Справедливы следующие тождества

Отсюда следует, что x+y = R(g(x) = x, h(x,y,z) = z+1). Так как функции g, h – простейшие функции, то x + y Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p.

Пример 6 Доказать, что функция f(x,y) = x?y примитивно рекурсивна.

Действительно. Справедливы следующие тождества:

f(x,y+1) = x(y+1) = xy+x = f(x, y) + x

Отсюда следует, что

Как следует из примера 1 функция h(x,y,z) = x+z Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p. А это значит, что xy Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p.

Рассмотрим функцию x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y = Как доказать что функция примитивно рекурсивная. image1919. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1919. картинка Как доказать что функция примитивно рекурсивная. картинка image1919.

Пример 7 Показать, что функция f(x,y) = x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y примитивно рекурсивна.

В начале заметим, что функция x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 примитивно рекурсивна. Действительно:

0 Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 = 0 = g(x)

(x+1) Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 = x = h(x,y)

Следовательно, x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 = R(g(x) = 0, h(x,y) = x). Итак, x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p.

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

x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.0 = x = g(x)

x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.(y+1) = (x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y) Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.1 = h(x, y, x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y)

для любых x и y. Данные тождества показывают, что

x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y = R(g(x) = 0, h(x,y,z) = z Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.α).

Так как функция h(x,y,z) = z Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.α Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p., то x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y Как доказать что функция примитивно рекурсивная. image1522. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1522. картинка Как доказать что функция примитивно рекурсивная. картинка image1522.Pn.p.

Так как любая примитивно рекурсивная функция является числовой функцией, то, очевидно, что x – y Как доказать что функция примитивно рекурсивная. image1923. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1923. картинка Как доказать что функция примитивно рекурсивная. картинка image1923.Pn.p.

Пример 8 Покажем, что Как доказать что функция примитивно рекурсивная. image1925. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1925. картинка Как доказать что функция примитивно рекурсивная. картинка image1925.– примитивно рекурсивная функция.

Действительно. Нетрудно показать, что Как доказать что функция примитивно рекурсивная. image1927. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1927. картинка Как доказать что функция примитивно рекурсивная. картинка image1927.=(x Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.y)+(y Как доказать что функция примитивно рекурсивная. image1917. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1917. картинка Как доказать что функция примитивно рекурсивная. картинка image1917.x). Теперь полученный результат следует из примера 5 и примера 7.

Операция минимизации. Будем говорить, что n-местная функция g(x1,x2,…,xn) полученная из (n+1)-местной функции f(x1,x2,…,xn,y) с помощью операции минимизации или оператора наименьшего числа, если для любых x1, x2,…, xn, y равенство g(x1,x2,…,xn) = y выполняется тогда и только тогда, когда:

Используется следующее обозначение:

Про функцию g говорят, что она получена из функции f при помощи операции минимизации.

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

Класс частично рекурсивных функций обозначим Prp.

Обозначим через Pp ­­– класс рекурсивных функций, т.е. всех числовых функций из Prp.

Пример 9 Доказать, что частично числовая функция Как доказать что функция примитивно рекурсивная. image1929. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1929. картинка Как доказать что функция примитивно рекурсивная. картинка image1929.частично рекурсивна.

Вначале заметим, что данная функция получается из функции Как доказать что функция примитивно рекурсивная. image1931. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1931. картинка Как доказать что функция примитивно рекурсивная. картинка image1931.с помощью операции минимизации, т.е. Как доказать что функция примитивно рекурсивная. image1933. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1933. картинка Как доказать что функция примитивно рекурсивная. картинка image1933.= My Как доказать что функция примитивно рекурсивная. image1935. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1935. картинка Как доказать что функция примитивно рекурсивная. картинка image1935..

Согласно примерам 2 и 4 функция Как доказать что функция примитивно рекурсивная. image1931. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1931. картинка Как доказать что функция примитивно рекурсивная. картинка image1931.примитивно рекурсивна. А это значит, что Как доказать что функция примитивно рекурсивная. image1929. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image1929. картинка Как доказать что функция примитивно рекурсивная. картинка image1929.– частично рекурсивная функция.

Данный пример показывает, что класс Prp существенно шире, чем класс Pp. Можно сказать, что и класс Pp существенно шире, чем класс Pnp, т.е.

Источник

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

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

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

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

Свойства x=y и Как доказать что функция примитивно рекурсивная. 85cdb885219f13a0f124e1b0a7536b63. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-85cdb885219f13a0f124e1b0a7536b63. картинка Как доказать что функция примитивно рекурсивная. картинка 85cdb885219f13a0f124e1b0a7536b63.примитивно рекурсивны ( x=y тогда и только тогда, когда Как доказать что функция примитивно рекурсивная. 400e86e7430d66d01840d2cd8069c44d. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-400e86e7430d66d01840d2cd8069c44d. картинка Как доказать что функция примитивно рекурсивная. картинка 400e86e7430d66d01840d2cd8069c44d.).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

Как доказать что функция примитивно рекурсивная. ris11 2. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 2. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 2.;
Как доказать что функция примитивно рекурсивная. ris11 3. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 3. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 3.;
Как доказать что функция примитивно рекурсивная. ris11 4. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 4. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 4..

Как доказать что функция примитивно рекурсивная. ris11 5. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 5. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 5.(17)

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

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

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

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

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

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

Как доказать что функция примитивно рекурсивная. ris11 9. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 9. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 9.(19)

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

1) Как доказать что функция примитивно рекурсивная. ris11 10. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 10. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 10.(20)
2) Как доказать что функция примитивно рекурсивная. ris11 11. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 11. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 11.(21)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как доказать что функция примитивно рекурсивная. ris11 20. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 20. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 20.(23)
Как доказать что функция примитивно рекурсивная. ris11 21. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 21. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 21.(24)
Как доказать что функция примитивно рекурсивная. ris11 22. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 22. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 22.(25)
Как доказать что функция примитивно рекурсивная. ris11 23. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-ris11 23. картинка Как доказать что функция примитивно рекурсивная. картинка ris11 23.(26)

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

Источник

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

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

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

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

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

ОПРЕДЕЛЕНИЕ

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

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

Упражнение. Показать, что если f(x1, x2) является примитивно-рекурсивной функцией, если она выражается через примитивно-рекурсивные функции 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) = Как доказать что функция примитивно рекурсивная. image008. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image008. картинка Как доказать что функция примитивно рекурсивная. картинка image008.(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( Как доказать что функция примитивно рекурсивная. image012. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image012. картинка Как доказать что функция примитивно рекурсивная. картинка image012.(x1, x2, x3), Как доказать что функция примитивно рекурсивная. image010. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image010. картинка Как доказать что функция примитивно рекурсивная. картинка image010.( x1, x2, x3)), где f — это примитивно-рекурсивная функция из предыдущего примера.

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

e(0) = S(0);

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

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

4. Функции sg(x) и Как доказать что функция примитивно рекурсивная. image014. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image014. картинка Как доказать что функция примитивно рекурсивная. картинка image014.(x), определяемые как:

sg(x) = Как доказать что функция примитивно рекурсивная. image016. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image016. картинка Как доказать что функция примитивно рекурсивная. картинка image016.и Как доказать что функция примитивно рекурсивная. image014. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image014. картинка Как доказать что функция примитивно рекурсивная. картинка image014.(x) = Как доказать что функция примитивно рекурсивная. image018. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image018. картинка Как доказать что функция примитивно рекурсивная. картинка image018., задаются следующими схемами:

sg(0) = 0; Как доказать что функция примитивно рекурсивная. image014. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image014. картинка Как доказать что функция примитивно рекурсивная. картинка image014.(x) = 1;

sg(x+1) = 1. Как доказать что функция примитивно рекурсивная. image014. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image014. картинка Как доказать что функция примитивно рекурсивная. картинка image014.(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)+ Как доказать что функция примитивно рекурсивная. image014. Как доказать что функция примитивно рекурсивная фото. Как доказать что функция примитивно рекурсивная-image014. картинка Как доказать что функция примитивно рекурсивная. картинка image014.(y-(mod(x, y)+1)).

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

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

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

ТЕОРЕМА 8.1

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

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

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *