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

 

3.1. Теоретические сведения о рекурсивных функциях

 

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

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

Элементарные функции:

1. Ноль – функция без аргументов, всегда возвращает ноль –
2. Инкремент – функция повышения значения переменной на единицу, возвращает x+1 –
3. Проекция – возвращает i-тую проекцию вектора переменных (то есть i-тую переменную) -

 

 

Операторы:

1. Суперпозиция – оператор, позволяющий передавать функции в качестве параметра значение, возвращённое другой функцией.
   Пример:
2. Примитивная рекурсия – оператор, позволяющий вычислять значение на основе . При применении оператора примитивной рекурсии к функции задаются две функции и такие, что:
   
   
3. Оператор минимизации – оператор, осуществляющий последовательный перебор всех возможных значений переменной пока её значение не будет удовлетворять некоторому условию. Формально – для заданной находит . Если , то оператор минимизации зацикливается и функция не выполняется. На практике используется оператор минимизации вида

3.2. Дерево структурного анализа

 

 

3.3. Доказательство ЧРФ

 

Пусть . Тогда:

 

Докажем действия. Введём функции для каждой операции

 

 

 

 

 

 

Докажем константы:

 

 

Применим оператор минимизации: