Элементарные рекурсивные функции — различия между версиями

Текущая версия на 13:10, 18 февраля 2019

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

Программа курса

Предикаты и операции над предикатами. Класс 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 относительно некоторых операций.

Литература

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

Ссылки

• Программа курса (pdf)