Частично-рекурсивные функции. Функции вычислимые по Тьюрингу и их свойства. Эквивалентность определений рекурсивных функций. Теоремы о вычислимых функциях.
Вычислимые предикаты.
1. Постройте машины Тьюринга, которые правильно вычисляют следующие функции:
a) 
.
2. Докажите, что следующие функции вычислимы по Тьюрингу, построив соответствующие машины Тьюринга:
а) 
3. Показать, что все арифметические функции натурального аргумента вычислимы по Тьюрингу.
4. Докажите, что если машины Тьюринга F и G правильно вычисляют функции 
и 
соответственно, то композиция Н= FG этих машин правильно вычисляет сложную функцию 
.
ность данной функции.
5. Докажите, что функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна.
6. Докажите, что следующие предикаты примитивно
рекурсивны:
а) 
: «
делится на 
»;
б) 
: « делится на 
и на »;
в) 
: «
»;
7. Докажите, что если функции и примитивно рекурсивны, то предикат 
примитивно рекурсивен.
Литература:[2,3,4,7,16,17,19,21,23,24,25]
Учебно-методическая литература:[2]
Дата добавления: 2015-09-12; просмотров: 63 | Поможем написать вашу работу | Нарушение авторских прав |