Подзоров С.Ю. Дополнительные главы теории вычислимости. Учебное пособие по спецкурсу

Новосибирск: НГУ, 2005. – 102 с. Соодержание:
Нумерации.
Вычислимые нумерации.
Вычислимые нумерации конечных семейств и конечных частично упорядоченных множеств.
m-сводимость и 1-сводимость.
Иерархия Ершова.
Табличные сводимости.
Вычислимость с оракулом и сводимость по Тьюрингу.
Универсальные функции и операция скачка.
Арифметическая иерархия.
Конструктивные ординалы.