2024/2025
Введение в обобщённую теорию рекурсий
Статус:
Дисциплина общефакультетского пула
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
3, 4 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Язык:
русский
Кредиты:
3
Программа дисциплины
Аннотация
Вторая половина XX в. отмечена появлением различных обобщений классической теории рекурсий (или теории алгоритмов). Во-первых, учёные стали варьировать предметную область и допускать вычисления, которые имеют дело не только с конструктивными объектами, т.е. с натуральными числами, словами и т.п. Во-вторых, введены инфинитарные обобщения вычислительных процессов. Теперь «вычисления» требуют трансфинитного числа шагов. Наконец, изучаются непервопорядковые вычислимые объекты, например, функции на функциях. В нашем курсе мы обсудим обобщение теорий рекурсий в первых двух направлениях. Опираясь на элементарные формальные системы, мы введём перечислимые отношения на произвольных реляционных структурах, а разрешив себе трансфинитные «вычисления», изучим теорию гиперэлементарных и индуктивных отношений, которые в случае стандартной модели арифметики образуют первый уровень аналитической иерархии.
Цель освоения дисциплины
- Получить представление об обобщённой теории рекурсий. Знать, что такое трансфинитные вычисления, гиперэлементарные и индуктивные отношения, а также другие базовые понятия. Уметь обосновывать основные факты и решать задачи.
Планируемые результаты обучения
- Познакомиться с (обобщенными) элементарными системами Смаллиана.
- Увидеть связь между индуктивной определимостью и (инфинитарной) вычислимостью.
- Освоить простые понятия теории гиперарифметических множеств и получить первое представление об аналитической иерархии.
Содержание учебной дисциплины
- Элементарные и обобщенные элементарные формальные системы.
- Монотонные индуктивные определения и их замыкающие ординалы.
- Совпадение представимых и индуктивных отношений.
- Структура гиперэлементарных множеств в случае гиперэлементарности базовых отношений реляционной структуры.
- Кодирование и универсальные формальные системы.
Промежуточная аттестация
- 2024/2025 4th module0.23 * ДЗ1 + 0.23 * ДЗ2 + 0.23 * ДЗ3 + 0.31 * Коллоквиум
