Просмотр исходного текста страницы Элементарные рекурсивные функции

Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]].

== Программа курса ==
Предикаты и операции над предикатами. Класс BA ограниченно арифметических
предикатов. Принадлежность классу BA простейших арифметических предикатов.
Позитивное представление предикатов класса BA. Каноническая форма ограниченно
арифметических предикатов. Принадлежность классу BA предикатов вида P_1=P_2.
Замкнутость класса BA относительно операций ограниченной квантификации 
(Qx)_{x\le P}. Критерий принадлежности предиката классу BA.

Диадическое представление чисел, операция конкатенации. Класс R рудиментарных
предикатов. Доказательство включения R\subseteq BA. Рудиментарность
простейших словарных предикатов. Позитивное представление рудиментарных 
предикатов. Рудиментарность предикатов вида T_1=T_2. Замкнутость класса R 
относительно операций ограниченной квантификации (Qx)_{x\le T}.

Операция ограниченной минимизации. Класс M. Доказательство равенства 
M_*= BA. 

Операция ограниченного суммирования. Класс S функций, элеменарных по Сколему.
Операция суженного ограниченного суммирования, класс S'. Доказательство
равенства S'=S.

Операция ограниченной рекурсии. Классы Гжегорчика, классы {\cal E}f. 
Принадлежность классу {\cal E}^0 простейших функций. Замкнутость классов
{\cal E}f относительно некоторых операций.

== Литература ==
# Марченков С.С. Элементарные рекурсивные функции. М.: МЦНМО, 2003.
# Кузнецов А.В. К теореме о канонической форме для ординально-рекурсивных функций. В книге: Гудстейн Р.Л. Математическая логика. М.: ИЛ, 1961, с. 149—154.
# Смальян Р. Теория формальных систем. М.: Наука, 1981.
# Косовский Н.К. Элементы математической логики и ее приложения к теории субрекурсивных алгоритмов. Л., Из-во Ленинград. ун-та, 1981.
# Гжегорчик А. Некоторые классы рекурсивных функций. В книге: Проблемы математической логики. М., Мир, 1970, с. 9—49.

== Ссылки ==

* Программа курса ([[Media:Elem_p.pdf|pdf]])

[[Категория:Спецкурсы кафедры МК]]