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

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

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

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

1. Доказать примитивную рекурсивность функции f(x, y) = x + y.
2. Доказать примитивную рекурсивность функции f(x, y) = x ⋅ y.
3. Доказать примитивную рекурсивность функции
4. Доказать примитивную рекурсивность функции f(x) = 2^x.
5. Доказать примитивную рекурсивность функции f(x, y) = x^y.
6. Доказать примитивную рекурсивность функции усеченное вычитание

Содержание отчета:

Выписать в тетрадь практических работ название, цель работы и решения выполненных задач. Сделать вывод к работе.

Критерии оценок:

«5» - выполнено 6 заданий.

«4» - выполнено 5 заданий.

«3» - выполнено 3-4 задания.

«2» - выполнено менее 3 заданий.

Литература.

Могилев А.В., Пак Н.И., Хённер Е.К, Информатика. М.: Академия, 2004.

Игошин В.И. Математическая логика и теория алгоритмов. М.: Академия, 2008.