Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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




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

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

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

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

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

Суперпозицией функций и называют функцию:

;

.

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

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

Примитивно-рекурсивные функции являются всюду определенными.

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

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

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

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

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

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

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

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

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

Дополнительное свойство:

.

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

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

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

– антисигнум, функция обратная .

.

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

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

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

Действительно, .

Отношение примитивно-рекурсивно.

Действительно, .

Отношение примитивно-рекурсивно.

Действительно, .

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

Зафиксируем набор значений аргументов и рассмотрим уравнение относительно y: ; чтобы найти решение этого уравнения, натуральное , будем вычислять последовательность значений:

для ..

Наименьшее целое неотрицательное значение , удовлетворяющее этому уравнению: обозначим:

.

Говорят, что функция получена из функции операцией минимизации, если:

.

Оператор минимизации работает бесконечно в одном из следующих случаев:

1) значение не определено;

2) значение для определены, но не равны нулю, а значение – не определено;

3) значение определены для всех , но не равны нулю.

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

Пример 9. Определение операции «вычитание»:

.

Пример 10. Определение операции «деление»:

.

Пример 11. Определение операции « извлечение корня »:

.

Пример 21. Определение операции « логарифм »:

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

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

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

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

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

 







Дата добавления: 2015-09-18; просмотров: 1242. Нарушение авторских прав

codlug.info - Студопедия - 2014-2017 год . (0.009 сек.) русская версия | украинская версия