5 Контрольные вопросы

1)Как применять и конструировать машины Тьюринга?

2)Как конструировать машины Тьюринга?

Практическая работа № 14. Применение рекурсивных функций при построении алгоритма.

1 Цель работы

Научиться:

- применять схему примитивной рекурсии;

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

2 Теоретическая часть

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

Простейшие функции:

1. оператор сдвига ;

2. оператор аннулирования ;

3. оператор проектирования если

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

Даны функции Функция называется суперпозицией функций Если функции интуитивно вычислимы, то и функция интуитивно вычислима.

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

Дана функция Рассмотрим функцию , равную наименьшему значению переменной y, при котором . Переход от функции к функции называют применением - оператора.

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

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

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

3 Практическая часть

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

Задача 3.2 Показать, что функцию можно получить применением - оператора. Пусть Тогда Введем обозначение Тогда Например,

4 Практическое задание

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

вариант	1	2	3	4	5	6
n	5	6	7	8	9	10
m	3	4	5	6	5	7

5 Контрольные вопросы

1) Что такое примитивная рекурсия?

2) Что такое - оператор?

3) Что такое общерекурсивная функция?