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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Методические указания и задания

К лабораторным работам по курсам

“ДИСКРЕТНЫЕ СТРУКТУРЫ“,

“ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ“

Донецк - 2009

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ГОСУДАРСТВЕННОЕ ВЫСШЕЕ УЧЕБНОЕ ЗАВЕДЕНИЕ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Методические указания и задания

к лабораторным работам

по курсам “Дискретные структуры”,

“ Теория алгоритмов и вычислительных процессов “

( для студентов, обучающихся по направлениям

“Программная инженерия”, “Компьютерные науки”)

Рассмотрено на заседании кафедры

прикладной математики и информатики

протокол № 14 от 29.06.09.

Утверждено на заседании

учебно-издательского совета ДонНТУ

протокол № 5 от 21.12.09

Донецк - 2009

УДК 004.021

Методические указания и задания к лабораторным работам по курсам “Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов, обучающихся по направлениям “Программная инженерия”, “Компьютерные науки”) / разраб.: Назарова И.А., Коломойцева И.А. – Донецк: ДонНТУ, 2009 – 38с.

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

- теория рекурсивных функций;

- машины Тьюринга;

- композиция машин Тьюринга;

- нормальные алгоритмы Маркова.

Составители: Назарова И.А., к.т. н., доцент

Коломойцева И.А., ст. преп.

Рецензент: Губенко Н.Е., к.т. н., доцент

Лабораторная работа №1

РЕКУРСИВНЫЕ ФУНКЦИИ

Цель работы: получить практические навыки в записи алгоритмов с использованием аппарата рекурсивных функций.

Теоретическая справка

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

Арифметическиефункции – функции, области определения и значений которых целые неотрицательные числа, то есть натуральный ряд + число ноль.

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

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

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

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

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

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

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

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

;

.

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

Частные случаи:

при n= 1 имеем ,

при n= 2 имеем .

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

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

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

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

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

Пример 3. Константа 1 может быть получена суперпозицией двух простейших функций: константы «ноль» и функции «последователь»:

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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