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

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

Литература

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

Ссылки

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