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

10

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

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

В качестве простейших функций в теории рекурсивных функций приняты следующие :

1. – константа «ноль».

2. – « последователь »

3. – функция тождества или выбора аргумента.

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

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

Оператором суперпозиции называется подстановка в функцию от m переменных m функций от n переменных, что дает новую функцию от n переменных. Суперпозицией функций g и называют функцию

Пример 1. Пусть

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

При этом значение X считается фиксированным. Работа операторазаключается в последовательном вычислении значения Более детально алгоритм вычисления функции по схеме примитивной рекурсии показан на блок-схеме ( рис. 2.1.).

Рис. 2.1. Алгоритм вычисления по схеме примитивной рекурсии.

Пример 2. Вычисление функции с помощью оператора примитивной рекурсии.

Пусть требуется вычислить 4!. По схеме примитивной рекурсии имеем:

Видно, что всякий раз при вычислении через значение уже определено.

Определение примитивно-рекурсивной функции

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

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

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

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

Пример 3. Константа a получается путем суперпозиции функций

и :

Пример 4. Операция сложения может быть определена с помощью оператора примитивной рекурсии :

В качестве функции записана функция тождества, функция h во втором равенстве – это . Таким образом, функция получена из простейших и путем применения оператора примитивной рекурсии, что соответствует определению примитивно-рекурсивной функции.

Пример 5. Примитивная рекурсивность операции умножения доказывается с использованием сложения :

Операция вычитания не является примитивно-рекурсивной, т.к. она не всюду определена : результат операции a—b при не определен в области натуральных чисел. Однако примитивно-рекурсивной является так называемое арифметическое вычитание.

Пример 6. Арифметическое вычитание:

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

т.е. операция примитивно–рекурсивна.

Тогда :

следовательно арифметическое вычитание примитивно–рекурсивно.

Пример 7. Функция — аналог функции для натуральных чисел.

Функция примитивно–рекурсивна :

При доказательстве примитивной рекурсивности не обязательно явным образом использовать оператор примитивной рекурсии.

Пример 8. Примитивная рекурсивность функции доказывается с помощью арифметического вычитания :

Справедливость этого равенства проверьте самостоятельно.

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

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

Если все же необходимо явно использовать оператор примитивной рекурсии, следует поступать следующим образом :

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

— определить значение (формулу) исследуемой функции при нулевом значении переменной ( тем самым получив первую формулу схемы примитивной рекурсии );

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

Следует иметь в виду, что если функция не всюду определена (т.е. частичная ), то она не примитивно–рекурсивна.

Примитивно-рекурсивными могут быть не только арифметические функции , но и « арифметизованные » логические функции, отношения, предикаты, различные операторы.

« арифметизованная » логическая функция – это такая арифметическая функция, которая на множестве <0,1> ведет себя как логическая.

Пример 9. Операции на множестве <0,1> примитивно–рекурсивны

Отношение называется примитивно–рекурсивным, если примитивно–рекурсивна его характеристическая функция :

Пример 10. Отношение примитивно–рекурсивно.

Предикат называется примитивно–рекурсивным, если примитивно–рекурсивна его характеристическая функция :

Пример 11. Доказать примитивную рекурсивность предиката « простое число ».

При доказательстве воспользуемся примитивно–рекурсивными функциями ( антисигнум — функция обратная ), .

Утверждение « n — простое число » разобьем на две части :

Из равенства следует : либо a=1, либо b=1.

Примитивная рекурсивность отношения :

Вторую часть утверждения запишем в виде :

Примитивная рекурсивность операции :

Примитивная рекурсивность операции «» ( импликация ) следует из примитивной рекурсивности базисных логических операторов . Следовательно вторая часть утверждения « n — простое число » тоже примитивно–рекурсивна.

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

Пример 12. Примитивная рекурсивность оператора условного перехода

где и — примитивно–рекурсивные функции; P — примитивно–рекурсивный предикат.

Примитивная рекурсивность функции ( и оператора B) следует из равенства :

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

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

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

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

Задача 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|$.

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

Функция Аккермана — одна из самых знаменитых функций в Computer Science. С ней связан как минимум один фундаментальный результат и как минимум один просто важный. Фундаментальный результат, говоря аккуратно и непонятно, таков: существует всюду определённая вычислимая функция, не являющаяся примитивно-рекурсивной. Важный результат заключается в том, что лес непересекающихся множеств (также известный как disjoint set union) работает очень быстро.

Мне очень нравится изучать функцию Аккермана, т.к. всё, что с ней связано, очень красиво и изящно. Вот и записанный выше фундаментальный результат понять намного проще, чем это может показаться.

Из текста ниже вы узнаете, что такое примитивно-рекурсивные функции и как выяснить, что функция Аккермана к таковым не относится. И, конечно, этот текст убедит вас в том, что это невероятно красивая конструкция и невероятно красивое рассуждение!

1. Почему это может быть интересно

Рассуждение о связи между примитивно-рекурсивными функциями и функцией Аккермана является примером решения стандартной в теории вычислимости задачи: дана некоторая модель вычислений, некоторая функция, и необходимо определить, является ли эта функция вычислимой в данной модели.

Другие подобные примеры связаны, например, с алгоритмической разрешимостью, эквивалентностью различных моделей вычислений (машин Тьюринга, частично-рекурсивных функций, нормальных алгорифмов Маркова и так далее). А через них мы связываемся уже с совершенно практической областью определения Тьюринг-полноты языков программирования, эквивалентных преобразований текстов программ и прочих интересностей.

Функция Аккермана как будто специально создана для того, чтобы быть изящным примером решения такого рода вопросов. Скоро вы в этом убедитесь.

2. Функция Аккермана

Определение из Википедии для наших целей подходит плохо, поэтому я использую определение из книжки Верещагина и Шеня «Вычислимые функции». Эта конструкция и идейно, и технически несколько отличается от изначальной, придуманной Аккерманом, но сейчас это не так важно.

Введём последовательность функций одного аргумента. Определим их рекурсивно:

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

Кстати, все аргументы здесь натуральные либо ноль — довольно типичный расклад для теории алгоритмов, да и для дискретной математики вообще.

Такое определение набора функций проще всего записать следующим кодом:

Для определения значения достаточно вычислить значение Foo(i, x) .

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

Во-вторых, по номеру функции: для любых и . Раз все функции строго монотонны по аргументу, а функция со следующим номером применяет функцию с предыдущим номером к этому же аргументу более одного раза — стало быть, итоговое значение получится больше. Чуть подробнее:

Отдельно стоит запомнить, что

3. Примитивно-рекурсивные функции (ПРФ)

ПРФ являются примером «математического исчисления». Исчисление — это способ определять множества объектов через набор аксиом и правил вывода из этих аксиом. В современной математике такой подход распространён широко: его можно встретить и в теории алгоритмов, и в математической логике, и в теории групп, и в куче других мест.

Что такое примитивно-рекурсивная функция? Начнём с «аксиом». Примитивно-рекурсивными функциями являются:

1. Функция, тождественно равная нулю:
2. Функция прибавления единицы:
3. Функция-проекция:

Назовём эти функции базисными. Теперь о «правилах вывода»:

• Подстановка. Если — функция аргументов, а — функции аргументов, то из них можно собрать функцию аргументов : берём аргументов, подставляем их в каждую из функций , получившиеся значения используем как аргументы функции . Типичная подстановка!

• Примитивная рекурсия. Если — функция аргументов, а — функция аргументов, то из них можно собрать функцию, определённую следующим образом:

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

Итак, ПРФ — это базисные функции, а также любые функции, полученные из базисных при помощи операций композиции и примитивной рекурсии.

В терминах ПРФ легко построить описания простых всем известных функций.

Например, сложение двух чисел сделаем через рекурсию по второму слагаемому. Если к числу прибавить ноль, то надо вернуть само это число. В противном случае надо к результату прибавить единицу, из второго слагаемого вычесть единицу и запустить рекурсию:

Теория алгоритмов — часть математики, а поэтому требует строгости. В данном случае оператор примитивной рекурсии требует, чтобы при нулевом втором аргументе вызывалась некоторая функция одного аргумента. Хотелось бы написать , но я не могу, т.к. просто не является функцией. Это вынуждает меня использовать функцию . В случае же рекурсивного вызова правила требуют, чтобы в правой части равенства стояла функция трёх конкретных аргументов: . Из них всех мне нужен только третий аргумент, поэтому я достаю его при помощи функции , а уже затем прибавляю единичку.

Похожим образом можно определить умножение:

Ну и давайте определим что-нибудь поинтереснее. Скажем, последовательность Фибоначчи! Напомню, что она определяется следующим образом:

В данном случае придётся помнить два предыдущих значения, а не одно; значит, придётся выкручиваться!

Введём не одну функцию, а сразу две. Первая функция, пусть это будет , будет производить искомые числа Фибоначчи. А вторая функция, пусть это будет , будет производить числа Фибоначчи со следующим номером, то есть:

В таком случае первые несколько значений функции должны равняться 0, 1, 1, 2, 3, 5; функции , соответственно, 1, 1, 2, 3, 5, 8. Тогда рекурсия должна выглядеть следующим образом:

Осталось только записать это строго:

Соответствующая реализация выглядит следующим образом:

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

4. Функция Аккермана и ПРФ, часть первая

Оказывается, примитивно-рекурсивные функции не могут «безгранично быстро» расти. Точнее говоря: для любой примитивно-рекурсивной функции аргументов найдётся такое , что:

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

Что же, для базисных операций всё понятно:

В первом случае используем то, что тождественный ноль всегда меньше единицы, а даже функция прибавляет к своему аргументу единицу (помним: мы в дискретном мире, тут все аргументы либо натуральные числа, либо ноль). Во втором случае прибавление единицы — в точности результат применения функции , которая по монотонности меньше функции . В третьем случае функция-проекция возвращает один из своих аргументов, который точно меньше, чем максимальный из всех аргументов, увеличенный на единицу.

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

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

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

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

Посмотрим для начала, что будет, когда аргумент рекурсии равняется нулю. Тут всё просто: можем использовать оценку для функции :

Теперь посмотрим, что будет, если последний аргумент равен единице:

Здесь сначала используется уже полученная оценка для , а также оценка для . После этого используется монотонность функции : ясно, что

Продолжая это рассуждение по индукции, получим, что

А свойства введённой последовательности функций гарантируют, что

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

5. Функция Аккермана и ПРФ, часть вторая

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

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

Теперь верно следующее утверждение: введённая функция не является примитивно-рекурсивной.

Действительно, предположим, что эта функция является примитивно-рекурсивной. Тогда по доказанному в пункте 4 существует такой номер , что для всех . Но это точно не так, например:

Таким образом, новая функция не является примитивно-рекурсивной. Этого-то мы и добивались, ура! Её и будем называть функцией Аккермана.

6. А насколько она в действительности велика?

Возвращаясь к практике, нам может быть интересно знать, насколько же всё-таки быстро растёт функция Аккермана, с чем её вообще можно сравнить. Выше мы уже видели, что суммы и произведения определяются некоторыми ПРФ. Через ПРФ можно определить операцию возведения в степень и даже функцию . Более того, любая функция вида

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

Теперь использую её для определения функции :

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

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

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

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

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

Рекурсивные функции строятся аналогичным образом.

Обратите внимание, что все функции в данном параграфе определены на множестве . Если это необходимо, в обозначении функции верхний индекс указывает число переменных. Так, функция зависит от переменных. Таким образом, .

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

Простейшие примитивно-рекурсивные функции Задаются следующим образом.

· Функция следования задается формулой: (или ).

· Функция аннулирования задается формулой: .

· Функция тождества определяется следующим образом: , то есть эта функция произвольному -мерному вектору сопоставляет его -ю координату.

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

· Оператор суперпозиции. Пусть , , , …, – примитивно-рекурсивные функции. Тогда функция

Получена с помощью оператора суперпозиции.

Оператор суперпозиции – это оператор построения сложной функции. Если мы умеем вычислять функции , , …, и , то значения функции могут быть получены последовательным вычислением значений функций , , …, на некотором наборе значений переменных , и вычислением значения функции на наборе значений , , …,

Пример. Функция получается суперпозицией функций 0(X) и S(X): . Аналогичным образом можно получить функции вида для всех значений N.

· Оператор примитивной рекурсии из известных примитивно-рекурсивных функций и позволяет строить новую функцию . Так,

,

.

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

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

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

,

.

Для произвольного получаем (обозначения , , , …, вводятся в предположении, что набор фиксирован):

,

,

,

.

Пример. Даны функции и . Определим функцию , полученную из данных функций по схеме примитивной рекурсии.

Решение. Найдем значения функции .

,

;

;

.

Можно предположить, что .

Докажем последнюю формулу методом математической индукции по переменной .

1. Проверим формулу при .

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

2. Допустим, что предположение индукции верно при , то есть, верна формула .

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

.

Таким образом, на основании метода математической индукции формула доказана для всех .

Теперь строго определим примитивно-рекурсивные функции.

Определение. 1) Простейшие примитивно-рекурсивные функции примитивно-рекурсивны.

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

3) Функция является примитивно-рекурсивной тогда и только тогда, когда это следует из 1) и 2).

Пример. Покажем, что функция примитивно-рекурсивна.

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

.

То есть .

Таким образом, функция получена по схеме примитивной рекурсии () из примитивно-рекурсивных функций, следовательно, сама является примитивно-рекурсивной.

Примитивно-рекурсивными, в частности, являются следующие функции: , , , , , ,

Операция минимизации по -ой переменной функции обозначается следующим образом: , и определяется так.

Рассмотрим уравнение относительно :

. (1)

Это уравнение решается подбором, вместо переменной последовательно подставляются 0,1,2,… При этом возможны случаи.

· На некотором шаге левая часть соотношения (1) не определена. Следовательно, на наборе операция минимизации не определена.

· На каждом шаге левая часть соотношения (1) определена, но равенство не выполняется ни при каких значениях . Следовательно, на наборе операция минимизации не определена.

· Левая часть соотношения (1) определена при , но при равенство не выполняется, а при выполняется. В этом случае число считается значением операции минимизации на наборе .

Пример. [ 13]. Найти функции, получаемые из данной числовой функции с помощью оператора минимизации по каждой ее переменной.

Решение. Минимизируем функцию по переменной . Рассмотрим уравнение

. (2)

1. Если , , то при подстановке получаем верное равенство.

2. Если , то левая часть равенства (2) не определена.

3. Если , , то при подстановке в левой части равенства (2) появляется выражение , не имеющее смысла, и в этом случае операция минимизации не определена.

4. Если , то получаем равенство . Оно имеет смысл при , то есть , что рассмотрено в первом пункте, и при , то есть . При равенство не имеет смысла.

Минимизируем функцию по переменной . Рассмотрим уравнение

.

Это уравнение на самом первом шаге, при подстановке вместо нуля теряет смысл, значит, операция минимизации по второй переменной нигде не определена.

Минимизируем функцию по переменной . Рассмотрим уравнение

. (3)

Если левая часть соотношения (3) имеет смысл и равенство (3) выполнено, то оно выполнено и при подстановке в это соотношение переменной на первом шаге, то есть при . В остальных случаях значение операции минимизации не определено.

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

Определение. Числовая функция называется Общерекурсивной, если она частично-рекурсивна и всюду определена.

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

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

Имеет место следующий тезис.

Тезис Черча. Каждая интуитивно вычислимая функция является частично-рекурсивной.

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

Тезис может быть опровергнут построением примера интуитивно вычислимой, но не частично-рекурсивной функции.