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