Introduction to Generalized Recursion Theory

2024/2025

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Faculty of Mathematics

Course type:

Optional course (faculty)

When:

3, 4 module

Instructors

Rybakov, Mikhail

Shamkanov, Daniyar S.

Программа дисциплины

Аннотация

Вторая половина XX в. отмечена появлением различных обобщений классической теории рекурсий (или теории алгоритмов). Во-первых, учёные стали варьировать предметную область и допускать вычисления, которые имеют дело не только с конструктивными объектами, т.е. с натуральными числами, словами и т.п. Во-вторых, введены инфинитарные обобщения вычислительных процессов. Теперь «вычисления» требуют трансфинитного числа шагов. Наконец, изучаются непервопорядковые вычислимые объекты, например, функции на функциях. В нашем курсе мы обсудим обобщение теорий рекурсий в первых двух направлениях. Опираясь на элементарные формальные системы, мы введём перечислимые отношения на произвольных реляционных структурах, а разрешив себе трансфинитные «вычисления», изучим теорию гиперэлементарных и индуктивных отношений, которые в случае стандартной модели арифметики образуют первый уровень аналитической иерархии.

Цель освоения дисциплины

• Получить представление об обобщённой теории рекурсий. Знать, что такое трансфинитные вычисления, гиперэлементарные и индуктивные отношения, а также другие базовые понятия. Уметь обосновывать основные факты и решать задачи.

Планируемые результаты обучения

• Познакомиться с (обобщенными) элементарными системами Смаллиана.
• Увидеть связь между индуктивной определимостью и (инфинитарной) вычислимостью.
• Освоить простые понятия теории гиперарифметических множеств и получить первое представление об аналитической иерархии.

Содержание учебной дисциплины

• Элементарные и обобщенные элементарные формальные системы.
• Монотонные индуктивные определения и их замыкающие ординалы.
• Совпадение представимых и индуктивных отношений.
• Структура гиперэлементарных множеств в случае гиперэлементарности базовых отношений реляционной структуры.
• Кодирование и универсальные формальные системы.

Элементы контроля

• ДЗ1
• ДЗ2
• ДЗ3
• Коллоквиум

Промежуточная аттестация

• 2024/2025 4th module
  0.23 * ДЗ1 + 0.23 * ДЗ2 + 0.23 * ДЗ3 + 0.31 * Коллоквиум

Список литературы

Рекомендуемая основная литература

• Mathematical logic. Pt.2: Recursion theory, Godel's theorems, set theory, model theory, Cori, R., 2004

Рекомендуемая дополнительная литература

• Математическая логика, теория алгоритмов и теория множеств, , 1973

Авторы

• Рыбаков Михаил Николаевич
• Минаев Андрей Алексеевич
• Шамканов Данияр Салкарбекович