Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга.
Машина Тьюринга: принцип действия, описание работы. Построение алгоритмов для реализации на машинах Тьюринга.
Универсальные машины. Первая теорема Шеннона. Вторая теорема Шеннона.
Нормальные алгоритмы и тезис Маркова. Преобразование машин Тьюринга в нормальные алгоритмы.
Понятие алгоритмической разрешимости. Задачи об остановке и печати машин Тьюринга. Самоанализирующие машины Тьюринга.
Алгорифмическая неразрешимость задачи об остановке машины Тьюринга при произвольном входном слове.
Алгорифмическая неразрешимость задачи об остановке машины Тьюринга на пустой ленте.
Алгорифмическая неразрешимость задачи о печатании символа точно один раз.
Алгорифмическая неразрешимость задачи о печатании символа бесконечно много раз.
Алгорифмическая неразрешимость задачи о печатании символа хотя бы один раз.
Тезис Маркова. Нормальные алгоритмы.
Преобразование машин Тьюринга в нормальные алгоритмы.
Понятие эффективной перечислимости. Эффективное распознавание и теорема Поста. Перечисление останавливающихся машин.
Эффективная перечислимость машин Тьюринга.
Эффективная перечислимость нормальных алгоритмов.
Теорема Поста (эффективная распознаваемость подмножества эффективно перечислимого множества).
Эффективная перечислимость останавливающихся машин Тьюринга и невозможность эффективного перечисления не останавливающихся машин Тьюринга.
Сведение числовых систем к натуральным числам. Равномощные множества и кардинальные числа. Парадокс Галилея и трансфинитные числа. Конечные, счетно-бесконечные и несчетные множества чисел.
Счетность множества натуральных, целых, рациональных и алгебраических чисел. Несчетность множества трансцидентных, действительных и комплексных чисел.

Вычислимые действительные числа. Вычислимость алгебраических и существование вычислимых трансцидентных чисел. Невычислимые числа.

Несчетность множества арифметических функций. Вычислимые арифметические функции. Невычислимые функции.

Счетность множества вычислимых арифметических функций.

Невозможность эффективного перечисления и сравнения вычислимых арифметических функций.
Невычислимые функции. Невозможность эффективного распознавания функций-констант среди вычислимых арифметических функций.
Несчетность множества частичных арифметических функций. Вычислимые частичные арифметические функции и их эффективное перечисление.
Невычислимые частичные функции. Теорема Черча (невозможность эффективного распознавания точек неопределенности вычислимой частичной функции).
Невозможность эффективного распознавания вычислимых арифметических функций среди вычислимых частичных арифметических функций.

Примитивно-рекурсивные функции и базис Клини. Примитивная рекурсивность суммы и факториала.

Рекурсивная функция. Примитивная рекурсивная функция. Базис Клини.
Геделева нумерация и эффективная перечислимость примитивно-рекурсивных функций.
Общерекурсивные и частично-рекурсивные функции. Расширенный базис Клини. Частичная рекурсивность разности.
Гёделева нумерация и эффективная перечислимость частично-рекурсивных функций.
Частичная рекурсивность нигде не определенной функции и функции, определенной в одной точке.
Тезис Черча. Расширенный базис Клини. Частичная рекурсивность разности.

Частичная рекурсивность нигде не определенной функции и функции, определенной в одной точке.

Рекурсивные функции и невозможность их эффективного перечисления.
Невозможность эффективной распознаваемости примитивно рекурсивных функций среди рекурсивных. Непримитивно рекурсивные функции.
Невозможность эффективной распознаваемости рекурсивных функций среди частично-рекурсивных. Нерекурсивные функции.