Просмотр исходного текста страницы Основы теории алгоритмов

Полугодовой спецкурс. Лектор — профессор [[Марченков Сергей Серафимович]].

== Программа курса ==

Машины Тьюринга. Вычислимые функции. Тезис Черча.

Разрешимые и перечислимые множества, теоретико-множественные операции над
ними. Эквивалентные определения перечислимых множеств. Связь между вычислимыми
функциями и перечислимыми множествами.

Универсальные функции. Построение вычислимой универсальной функции. Всюду
определенные продолжения вычислимых функций.

Существование рекурсивно перечислимого неразрешимого множества. Рекурсивно
перечислимые рекурсивно неотделимые множества.

Иммунные и простые множества. Простое множество Поста.

Существование главной универсальной функции. Номера композиции функций в
главной нумерации. Неразрешимость множества номеров нетривиального семейства 
функций в главной нумерации. Изоморфизм главных нумераций.

Теорема о неподвижной точке и ее следствия. 

<math>m</math>-сводимость и ее свойства. Существование <math>m</math>-полного перечислимого множества.

Вычисления с оракулом. Сводимость по Тьюрингу и ее свойства. Формализация
относительной вычислимости функций.

Операции суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции.
Относительная примитивная рекурсивность. Операции ограниченного суммирования
и мультиплицирования. Предикаты и представляющие функции. Операции ограниченной
квантификации и минимизации. Возвратная рекурсия.

== Литература ==

# Верещагин Н.К., Шень А. Вычислимые функции. М.: МЦНМО, 1999. 174 с.
# Мальцев А.И. Алгоритмы и рекурсивные функции. М.: Наука, 1986. 392 с.
# Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. М.: Мир, 1972. 624 с.

== Ссылки ==

* Программа курса ([[Media:Osnov_p.pdf|pdf]])

[[Категория:Спецкурсы кафедры МК]]