Доказать что следующие функции примитивно рекурсивны
Перейти к содержимому

Доказать что следующие функции примитивно рекурсивны

Примеры решения задач

  1. Доказать, что следующие функции примитивно рекурсивны: а) б)в)(функция “сигнум”).

Решение. а) Имеем: оЭто схема примитивной рекурсии. Так как функцияпримитивно рекурсивна, то функциятоже. б) Схема примитивной рекурсии для функции выглядит так:s(oТак как функцияпримитивно рекурсивна, тотоже. в) Имеем: Следовательно, функцияпримитивно рекурсивна.

  1. Доказать, что функция рекурсивна.

Доказательство. Пусть Так как функцияполучается из примитивно рекурсивных функций с помощью оператора минимизации, то функциярекурсивна. Ясно, чтоИзвестно, что функцияпримитивно рекурсивна (см. предыдущее упражнение). Следовательно, функциярекурсивна. Это влечёт рекурсивность функцииа она совпадает с функцией

  1. Выяснить, что из себя представляет функция Мгде функция “сигнум” (см. предыдущую задачу).

Решение. Пусть МТогдаПоэтомуа остальные значения функциине определены.

Задачи для самостоятельного решения

  1. Доказать, что следующие функции примитивно рекурсивны: а)б)в)

Указания: а) б) в)

  1. Доказать, что функция является рекурсивной.

Указание:

  1. Доказать, что если функция примитивно рекурсивна, то функция– тоже. Используя это утверждение и результат задачи

1 в), доказать примитивную рекурсивность функции Указания:4.4. Вычислимые и перечислимые функции и множества В предыдущем разделе были определены понятия рекурсивной функции и функции, вычислимой на машине Тьюринга и были изложены соображения в пользу того, что эти классы совпадают. Будем называть такие функции вычислимыми. Рассмотрим более внимательно эти функции и множества натуральных чисел, связанные с ними. Изложение результатов будем вести неформально, чтобы облегчить читателю восприятие материала. Аргументывычислимой функция– натуральные числа, значение функции – также натуральное число. Существование невычислимых функций уже отмечалось ранее: оно следует из соображений мощностей: вычислимых функций, так же, как и машин Тьюринга, счётное число, а всех функций на множестве натуральных чисел штук. Интересный пример невычислимой функции придуман в 1962 г. Т.Радо. Пример. Предположим, что среди некоторых машин Тьюринга проводится “соревнование по трудолюбию”. Участником соревнования является машина Тьюринга с состояниями(причём последнее состояние используется только для остановки), которая, будучи запущена на пустой ленте, останавливается за конечное число шагов. Результат соревнования – количество единиц на ленте после остановки машины. Обозначим это число черезДокажем, что– невычислимая функция. Пусть – произвольная вычислимая функция. Введём функциюТак как функциявычислима, тотакже вычислима. Пусть– машина Тьюринга, которая вычисляет функциюи– количество состояний машиныПусть– машина Тьюринга, которая пишетединиц на пустой ленте (для этого нужносостояния), а затем работает какТогда– участник соревнования ссостояниями, поэтомуОтсюда следует, чтоиЗначит, примы имеемиИтак, при больших(чётных и нечётных) имеет место неравенствоЗначит, функциярастёт быстрее любой всюду определённой вычислимой функции, поэтому не является вычислимой. Функция растёт очень быстро. Известно, что(см. Г.Б.Эндертон, Элементы теории рекурсии, в сб. Справочная книга по математической логике, т. 3).

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

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

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

[math]\mathbb \rightarrow \mathbb[/math] , [math]\mathrm(x) = x'[/math] , где [math]x’ = x + 1[/math] .

[math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] , [math]\mathrm (x_1, \ldots, x_n) = x_i[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] и [math]\mathrm, \ldots, \mathrm: \mathbb^ \rightarrow \mathbb[/math] , то [math]\mathrm\langle<>\mathrm,\mathrm, \ldots, \mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] . При этом [math]\mathrm\langle<>\mathrm,\mathrm, \ldots, \mathrm\rangle (x_1, \ldots, x_m) = \mathrm(\mathrm(x_1, \ldots, x_m), \ldots \mathrm(x_1, \ldots, x_m))[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] и [math]\mathrm:\mathbb^ \rightarrow \mathbb[/math] , то [math]\mathrm\langle<>\mathrm,\mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] , при этом [math]\mathrm\langle<>\mathrm,\mathrm\rangle (x_1, \ldots, x_n,y) = \left\ \mathrm(x_1, \ldots, x_n) & y = 0\\ \mathrm(x_1, \ldots, x_n,y-1,\mathrm\langle<>\mathrm,\mathrm\rangle(x_1, \ldots, x_n,y-1)) & y \gt 0 \end\right.[/math]

Если [math]\mathrm: \mathbb^ \rightarrow \mathbb[/math] , то [math]\mu \langle<>\mathrm\rangle: \mathbb^ \rightarrow \mathbb[/math] , при этом [math]\mu \langle<>\mathrm\rangle (x_1, \ldots, x_n)[/math] — такое минимальное число [math]y[/math] , что [math]\mathrm(x_1, \ldots, x_n,y) = 0[/math] . Если такого [math]y[/math] нет, результат данного примитива неопределен.

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

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

Определение:
Примитивно рекурсивными (англ. Primitively recursive) называют функции, которые можно получить с помощью правил [math]1[/math] — [math]5[/math] .

Заметим, что если [math] \mathrm [/math] — [math]n[/math] -местная примитивно рекурсивная функция, то она определена на всем множестве [math] \mathbb^ [/math] , так как [math] \mathrm [/math] получается путем правил преобразования из всюду определенных функций, и правила преобразования не портят всюду определенность. Говоря неформальным языком, рекурсивные функции напоминают программы, у которых при любых входных данных все циклы и рекурсий завершатся за конечное время. Если же говорить формально, то это свойство рекурсивных функций называется тотальностью.

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

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

  • В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с помощью проекторов поставить требуемый аргумент на последнее место.
  • В правиле подстановки можно использовать функции с разным числом аргументов. Например, подстановка [math] \mathrm(x,y) =\mathrm(\mathrm(y),\mathrm(x,x,y)) [/math] эквивалентна [math] \mathrm(x,y,z) = \mathrm(\mathrm(\mathrm(x,y)),\mathrm(\mathrm(x,y),\mathrm(x,y),\mathrm(x,y))) [/math] , но если [math] \mathrm [/math] не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.

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

n-местный ноль

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

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

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

Теперь вместо функции [math]\mathrm(x)[/math] будем использовать константу [math]\textbf 0[/math] , обозначив ее как [math]\mathrm(x)[/math] .

Константа [math] \textbf M [/math]

[math] \textbf M^n [/math] — [math]n[/math] -местная константа, получается аналогичным к [math] \textbf 0^n [/math] образом.

Сложение

[math] \mathrm(x, y) = \mathrm\langle<>\mathrm,\mathrm\rangle(x,y)[/math] , где

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

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

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

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

[math]=\left\ 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] x \leqslant y [/math] , то [math] \mathrm(x,y) = 0 [/math] , иначе [math] \mathrm(x,y) = x — y [/math] .

Рассмотрим сначала вычитания единицы [math] \mathrm>(x) = x — 1 [/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,y) = 1 [/math] если [math] x = y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

[math] \mathrm(x,y) = 1 [/math] если [math] x \leqslant y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

[math] \mathrm(x,y) = 1 [/math] если [math] x \lt y [/math] , иначе [math] \mathrm(x,y) = 0 [/math]

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

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

[math] \mathrm(y) = \mathrm(y-1,\mathrm(y-1)) [/math] , где [math] \mathrm(y-1,\mathrm(y-1)) = \mathrm(x,y-1) [/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(x,y) = \Bigl \lfloor \dfrac \Bigr \rfloor [/math] , если [math] y \gt 0 [/math] . Если же [math] y = 0 [/math] , то значение функции нас не интересует, и можно определить её как угодно.

Сначала определим [math] \mathrm(x,y) [/math] — функция равна максимальному числу меньшему или равному [math] x[/math] , которое нацело делится на [math] y [/math] .

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

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

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

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

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

С помощью описанных выше арифметических операций можно выразить проверку на простоту числа и поиск [math] n [/math] -ого простого числа. Рассмотрим список из натуральны чисел [math] [x_1,\ldots,x_n] [/math] , тогда ему в соответствия можно поставить число [math] p_1^ \cdot p_2^ \cdot \ldots \cdot p_n^ [/math] , где [math]p_i[/math] — [math]i[/math] -тое простое число. Как видно из представления,создания списка, взятие [math] i [/math] — того элемента и остальные операции являются простыми арифметическими операциями, а следовательно примитивно рекурсивными. Поэтому будем считать что у примитивно рекурсивной функций аргументы и результат могут быть списками из натуральных чисел.

Теоремы

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

Если для вычислимой функции [math] \mathrm [/math] существует примитивно рекурсивная функция [math] \mathrm [/math] , такая что для любых аргументов [math] args [/math] максимальное количество шагов, за которое будет посчитана [math] \mathrm(x) [/math] на МТ равно [math] \mathrm(args) [/math] , то [math] \mathrm [/math] примитивно рекурсивная функция.

Каждому состоянию МТ поставим в соответствие список из четырех чисел [math] [L,R,S,C] [/math] , где:

  • [math] L [/math] — состояние МТ слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту МТ. Младшие разряды находятся возле головки. Пробелу соответствует ноль, чтобы число было конечным.
  • [math] R [/math] — состояние МТ справа от головки, представлено аналогично [math] L [/math] только возле головки МТ находятся старшие разряды.
  • [math] S [/math] — номер текущего состояния.
  • [math] C [/math] — символ на который указывает головка ленты.

Тогда всем переходам соответствует функция [math] \mathrm([L,R,S,C]) [/math] принимающая состояние МТ и возвращающая новое состояние. Покажем что она примитивно рекурсивная . При применении перехода в [math] C [/math] записывается новый символ,затем из-за сдвига головки в [math] L [/math] и [math] R [/math] в конец добавляется новая цифра или удаляется старая, затем в [math] C [/math] записываетcя символ после сдвига, и в конце перехода в [math] S [/math] записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через простые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода — примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций [math] \mathrm [/math] следует что и [math] \mathrm [/math] также является примитивно рекурсивной функцией.

Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их [math]\mathrm [/math] и [math] \mathrm [/math] .

Рассмотрим функцию двух аргументов [math] \mathrm([L,R,S,C],t) [/math] которая принимает состояние МТ , число шагов [math] t [/math] и возвращает состояние МТ после [math] t [/math] шагов. Покажем что [math]\mathrm[/math] — примитивно рекурсивная функция.

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

[math] \mathrm([L,R,S,C],t+1) = \mathrm([L,R,S,C],t+1,\mathrm([L,R,S,C],t)) [/math] , где [math] \mathrm([L,R,S,X],y,[L1,R1,S1,C1]) = \mathrm([L1,R1,S1,C1]) [/math]

См. также

  • Лямбда-исчисление
  • Частично рекурсивные функции

Источники информации

  • Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд., испр., М.: МЦНМО, 2012
  • Википедия — Рекурсивная функция
  • Wikipedia — Primitive recursive function

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

На этой странице вы найдете готовые примеры заданий по проверки примитивной рекурсивности функции .

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

Спасибо за ваши закладки и рекомендации

Задачи и решения о рекурсивных функциях

Задача 1. Пользуясь определением примитивно рекурсивной функции, показать что числовая функция $f(x)$ примитивно рекурсивна. $f(x)=x!$

Задача 2. Доказать примитивную рекурсивность следующей функции $f(x,y)=x\cdot y$.

Задача 3. Доказать, что заданная функция, определенная для натуральных аргументов и принимающая натуральные значения, является примитивно рекурсивной. $f(x,y)=x^y+x$.

Подробно решаем задачи по дискретной математике

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

Введем базис простых операций:

  • Константа 0
  • Функция следования $x’=x+1$ (иногда обозначается $S(x)=x+1$)
  • Функция проекции $I_m^n(x_1,x_2. x_n)=x_m$

Оператором суперпозиции (оператором подстановки) $S_m^n$ называется подстановка в функцию от $m$ переменных $m$ функций от $n$ одних и тех же переменных. Суперпозиция дает новую функцию от $n$ переменных.

Оператор примитивной рекурсии $R_n$ определяет $(n+1)$ – местную функцию $f$ через $n$ – местную функцию $g$ и $(n+2)$ – местную функцию $h$ так:

$$ f(x_1. x_n,0)=g(x_1. x_n),\\ f(x_1. x_n,y+1)=h(x_1. x_n, y, f(x_1. x_n,y). $$

Эта пара равенств называется схемой примитивной рекурсии и обозначается, как

Данная схема определяет функцию $f$ рекурсивно не только через другие функции, но и через значения самой $f$ в предшествующих точках. Существенным в операторе примитивной рекурсии является то, что независимо от числа переменных в $f$ рекурсия ведется только по одной переменной $y$, а остальные $n$ переменных $x_1. x_n$ на момент применения схемы рекурсии зафиксированы и играют роль параметров.

Функция называется примитивно-рекурсивной, если она может быть получена из константы 0, функции $x’$ и функции $I_m^n$ с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии.

Основные примитивно-рекурсивные функции: сложение $a+b$, умножение $ab$, возведение в степень $a^b$, симметрическая разность $|a-b|$.

Доказать что следующие функции примитивно рекурсивны

На этом шаге мы рассмотрим примитивно рекурсивный предикат .

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

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

  • D φ = D p = D , т.е. их областb определения совпадают;
  • для любого набора (x 1 , . x n ) из области определения D

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

Действительно, в качестве представляющей функции первого предиката можно взять функцию вида φ 1 (x) = sg|x-y| , (18) где

является ПРФ . Покажем, что данная функция — ПРФ .

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

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

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

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

Покажем, что эти функции являются ПРФ .

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

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

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

где в последнем равенстве f(x,y) = i(f(x,y)) , т.е. получили функцию сходную с функцией в первом случае, следовательно, в качестве ПРО данной функции можно взять последовательность функций:

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

Очевидно, данная функция является ПРФ .

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

и очевидно, она удовлетворяет исходным условиям и является ПРФ .

Определение . Функция f(x 1 , . x n ) называется ПРФ относительно совокупности функций и предикатов Ψ = , если она ПРФ относительно совокупности функций φ 1 , . φ m , Ψ 1 , . Ψ k , где Ψ i , 1

Определение . Предикат p(x 1 , . x n ) называется ПРФ относительно совокупности функций и предикатов Ψ = , если представляющая функция предиката p является примитивно рекурсивной относительно совокупности функций φ 1 , . φ m , Ψ 1 , . Ψ k , где Ψ i , 1

Теорема 2. Логические операции над предикатами сохраняют свойства примитивной рекурсивности предикатов. Доказательство . Приведем в виде таблицы истинностные значения логических операций: конъюнкции, дизъюнкции, импликации и отрицания.

Таблица 1. Результаты логических операций
p(x) q(x) p(x)∧q(x) p(x)Vq(x) p(x)->q(x)
0 1 0 0 0 1
0 1 1 0 1 1
1 0 0 0 1 0
1 0 1 1 1 1

Пусть φ p (x) — представляющая функция предиката р(х) ; φ q (x) — представляющая функция предиката q(x) , где в общем случае x = (x 1 , . x n ) .

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

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

На следующем шаге мы рассмотрим операцию навешивания ограниченного квантора над предикатами .

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

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