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