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

Теоретический минимум

Класс примитивно-рекурсивных функций определяется путем указания конкретных исходных функций (они называются базисными) и фиксированного множества операций над ними, применяемых для получения новых функций из ранее заданных.
В качестве базисных функций обычно берутся следующие:
•Функция следования ;
•Функция тождества (функция проекции, или функция выбора аргументов);
•Функция константы .
Допустимыми операциями над функциями являются операции:
•суперпозиции (подстановки);
•примитивной рекурсии.
Эти три функции и две операции образуют базис Клини
Для начала, рассмотрим каждую из функций.
1) функция – следование: , где – число, непосредственно следующее за натуральным числом . Например, и т.д.
2) функция - тождество: , где n – кол-во переменных, а i – номер переменной, по которой берется тождество. Функция тождества – функция, равная одному из своих аргументов. Например, .
3) функция - константа: , где n – число переменных, q – значение, которое принимает функция. Функция константа принимает всюду одно значение. Например, .
Далее рассмотрим операции.
1) операция примитивной рекурсии
Если мы имеем функцию одной переменной , то схема рекурсии называется «рекурсия без параметров» и задается системой уравнений:


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


Функция, заданная такими уравнениями, кратко задается схемой вида

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

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

Примеры
Пример 1. Доказать примитивную рекурсивность функции .
Будем строить рекурсию по первой переменной. Применяем операцию примитивной рекурсии:


Теперь наша задача - переписать все, используя только три основные функции:


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


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


В итоге получаем:
Примечание. Далее - произведение двух чисел
Пример 3. Доказать примитивную рекурсивность факториала .
Применяем операцию примитивной рекурсии:


В итоге получаем:

Задачи для тренировки
Задача 1. Докажите примитивную рекурсивность функции
Задача 2. Докажите примитивную рекурсивность для псевдоразности .
Примечание. Псевдоразность
Задача 3. Докажите примитивную рекурсивность функции
Примечение.

Частично-рекурсивные функции​

Теоретический минимум

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

Оператор минимизации.
Пусть имеется функция , принадлежащая множеству частичных арифметических функций (ЧАФ). Пусть существует какой-то механизм ее вычисления, причем значение функции не определено тогда и только тогда, когда этот механизм работает бесконечно, не выдавая никакого определенного результата.
Фиксируем какие-нибудь значения для первых аргументов функции и рассмотрим уравнение:
Чтобы найти решение (натуральное) этого уравнения, будем вычислять при помощи указанного выше "механизма" последовательно значения для . Наименьшее значение , для которого получится , обозначим через
Описанный процесс нахождения выражения будет продолжаться бесконечно в следующих случаях:
• Значение не определено;
• Значения для определены, но отличны от , а значение – не определено;
• Значения определены для всех и отличны от .
Во всех этих случаях значение выражения считается неопределенным. В остальных случаях описанный процесс обрывается и дает наименьшее решение уравнения . Это решение, как сказано, и будет значением выражения .
Например, функция разности c помощью оператора минимизации будет записана так:

Подсчет значений функции в этом случае будет проходить по двум сценариям.
Пример 4. Пусть . Последовательно, начиная с , перебираем возможные значения для нахождения :
• при получим выражение , его значение «ложь»;
• при получим выражение , его значение «ложь»;
• при получим выражение , его значение «истина», следовательно, процесс обрывается, и получаем результат: .
Пример 5. Пусть . Последовательно, начиная с , перебираем возможные значения для нахождения :
• при получим выражение , его значение «ложь»;
• при получим выражение , его значение «ложь»;
• при получим выражение , его значение «ложь»;
и т.д. – т.е. при увеличении ситуация, при которой выражение будет иметь значение «истина», так и не наступит, а значит значение функции так и не будет найдено.
Пример 5 – это иллюстрация случая, при котором оператор минимизации не дает результата именно тогда, когда такой результат не может быть получен в принципе, по той причине, что в заданной точке функция действительно не определена. Это третий случай, в котором процесс поиска выражения продолжается бесконечно.
Напротив, значение выражения не определено, так как уже при значение терма для любого не определено. В то же время уравнение имеет решение , но оно не совпадает со значением выражения .
Этот пример показывает, что для частичных функций выражение , строго говоря, не есть наименьшее решение уравнения . Если же функция всюду определенная и уравнение имеет решения, то есть наименьшее решение для этого уравнения. Отсюда возникает закономерное желание использовать под оператором минимизации только всюду определенные функции. Наилучший способ убедиться в том, что функция всюду определена – использовать заведомо примитивно-рекурсивные функции (или функции, примитивная рекурсивность которых уже доказана ранее или вытекает из способа их задания). В этом случае значения будет неопределенно только в одном из трех случаев, а именно если значения определены для всех и отличны от . Для этого имеющуюся функцию нужно преобразовать таким образом (путем переноса слагаемых, умножения обеих частей, и т.д.) чтобы по обе стороны равенства стояли примитивно рекурсивные (а значит всюду определенные) выражения. В общем виде, под оператором минимизации получим некое рекурсивное уравнение, части которого зависят от переменных . Это уравнение принимает значение «истина» или «ложь» при последовательно выбираемых значениях параметра .
Итак, для того, чтобы задать частично-рекурсивную функцию в виде элементарной схемы ее вычисления, необходимо расширить введенный ранее базис Клини за счет появления новой операции: операции минимизации. Здесь важно понимать, что в расширенном базисе Клини в итоге могут оказаться заданы также и примитивно-рекурсивные функции – но для примитивно-рекурсивных функций использование этого оператора, по сути, является избыточным.

Пример 6. Нигде неопределенная функция . Построим рекурсивное уравнение: . Результат операции минимизации не определен даже для точки .
Пример 7. Функция, определенная в одной точке, . Построим рекурсивное уравнение: . Результат операции минимизации определен только для точки , при остальных значениях вычисление (подбор нужного значения ) никогда не будет закончено.
Пример 8. Применить оператор минимизации для функции .
Будем проводить минимизацию по каждому элементу. Т.е. вместо каждый раз будем подставлять , а будет стоять справа. Каждое из этих уравнений надо будет решить сначала в общем виде, а затем подобрать , либо доказать невычислимость.
1)
Решаем уравнение относительно и получаем:

Теперь проанализируем исходное уравнение и полученное решение.
Из исходного уравнения видно, что при может принимать любое значение, но нам нужно минимальное, т.е . Это первое решение.
из решения можно увидеть, что при условии, что и кратно разности . Это второе решение. Оба решения найдены.
2)
решение полностью аналогичное первому пункту.
3)
решаем уравнение относительно z и получаем:
при . В противном случае решений нет.
4)
В этом случае - может быть любое, если равенство выше выполняется, поэтому выбираем наименьшее, т.е , в противном случае решений нет.

Задачи для тренировки
Применить оператор минимизации для функций:
Задача 4.
Задача 5.
Задача 6.

О, а я уже начал это забывать потихоньку.

BA3a, я оказывается тоже :huh: но семинары полистал, вспомнил) сегодня наверно еще парочку примеров добавлю, а после экзамена добавлю теорию по ЧРФ

Silver MC's, если найти конспекты, то и я за какое-то время вспомню. Но найти их — не такая уж и простая задача.

Update 1. Добавил еще 2 примера и три задачи для самостоятельного решения. Просьба, ответ здесь не писать. Для проверки - напишите в ЛС. Спасибо :huh:

Update 2. Добавил теорию, примеры и задачи по частично-рекурсивным функциям

Подскажите пожалуйста как решить если можно с объяснением