Элементарные рекурсивные функции
Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.
Программа курса
Предикаты и операции над предикатами. Класс 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.
Ссылки
- Программа курса (pdf)
