misle.ru страница 1
скачать файл
Семинар №6

Тема: Машины Тьюринга.
Задачи: 1. Освоить понятие примитивно-рекурсивной функции.

2. Научиться доказывать пр.рекурсивность функций.



Время: 1 пара (2x45 мин).

Место проведения: НГУ, ауд.307а.

Метод: семинар.

Ход семинара:


Учебные
вопросы,
время

Действия
семинариста

Действия
обучаемых

0. проверяю дом. задание
(10 мин)

Необходимый разбор домашнего задания. Коллоквиум? Контрольная работа.

Вопросы.

1. определение примитивной рекурсии
(10 мин)

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

Вспоминают лекции, записывают. Вопросы.

2. примеры п.р.ф.
(40 мин)

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

Доказать, что перечисленные функции не могут быть получены из O и операторами S и R.






3. п.р. предикаты
(15 мин)

Конъюнкция, дизъюнкция, отрицание предикатов. Оператор ограниченной минимизации.




4. Окончание
(5 мин)

Записываю на доске д/з: 1-4. Объявляю о теме следующего семинара: Оператор минимизации. Частично-рекурсивные функции.

Записывают задачи на дом.

.

Конспект:

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

Базовые функции:


  1. s(x) := x+1;

  2. 0 – нульместная функция;

  3. (x1,…,xn) := xm, (mn)

Операторы:



  1. Суперпозиция ;

  2. Примитивная рекурсия ;

  3. Ограниченная минимизация ;

  4. Минимизация.

Рекурсивные предикаты.






Задачи:
скачать файл


Смотрите также: