Элементарные рекурсивные функции — различия между версиями
Root (обсуждение | вклад) (Новая страница: «Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович. == Программа к…») |
Root (обсуждение | вклад) (→Программа курса) |
||
| Строка 5: | Строка 5: | ||
предикатов. Принадлежность классу BA простейших арифметических предикатов. | предикатов. Принадлежность классу BA простейших арифметических предикатов. | ||
Позитивное представление предикатов класса BA. Каноническая форма ограниченно | Позитивное представление предикатов класса BA. Каноническая форма ограниченно | ||
| − | арифметических предикатов. Принадлежность классу BA предикатов вида | + | арифметических предикатов. Принадлежность классу BA предикатов вида P_1=P_2. |
Замкнутость класса BA относительно операций ограниченной квантификации | Замкнутость класса BA относительно операций ограниченной квантификации | ||
| − | + | (Qx)_{x\le P}. Критерий принадлежности предиката классу BA. | |
Диадическое представление чисел, операция конкатенации. Класс R рудиментарных | Диадическое представление чисел, операция конкатенации. Класс R рудиментарных | ||
| − | предикатов. Доказательство включения | + | предикатов. Доказательство включения R\subseteq BA. Рудиментарность |
простейших словарных предикатов. Позитивное представление рудиментарных | простейших словарных предикатов. Позитивное представление рудиментарных | ||
| − | предикатов. Рудиментарность предикатов вида | + | предикатов. Рудиментарность предикатов вида T_1=T_2. Замкнутость класса R |
| − | относительно операций ограниченной квантификации | + | относительно операций ограниченной квантификации (Qx)_{x\le T}. |
Операция ограниченной минимизации. Класс M. Доказательство равенства | Операция ограниченной минимизации. Класс M. Доказательство равенства | ||
| − | + | M_*= BA. | |
Операция ограниченного суммирования. Класс S функций, элеменарных по Сколему. | Операция ограниченного суммирования. Класс S функций, элеменарных по Сколему. | ||
| − | Операция суженного ограниченного суммирования, класс | + | Операция суженного ограниченного суммирования, класс S'. Доказательство |
| − | равенства | + | равенства S'=S. |
| − | Операция ограниченной рекурсии. Классы Гжегорчика, классы | + | Операция ограниченной рекурсии. Классы Гжегорчика, классы {\cal E}f. |
| − | Принадлежность классу | + | Принадлежность классу {\cal E}^0 простейших функций. Замкнутость классов |
| − | + | {\cal E}f относительно некоторых операций. | |
== Литература == | == Литература == | ||
Версия 12:38, 30 января 2014
Полугодовой спецкурс. Лектор — профессор Марченков Сергей Серафимович.
Программа курса
Предикаты и операции над предикатами. Класс 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)
