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

Версия 18:48, 31 октября 2013

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

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

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

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

Операция ограниченной минимизации. Класс M. Доказательство равенства Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): {\rm M}_*={\rm BA} .

Операция ограниченного суммирования. Класс S функций, элеменарных по Сколему. Операция суженного ограниченного суммирования, класс Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): {\rm S}' . Доказательство равенства Невозможно разобрать выражение (Преобразование в PNG прошло с ошибкой — проверьте правильность установки latex и dvips (или dvips + gs + convert)): {\rm S}'={\rm 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)