Модуль 5. Элементы теории алгоритмов

Понятие алгоритма. Свойства. Способы описания алгоритмов. Необходимость уточнения понятия алгоритм. Основные алгоритмические модели.

Определение машины Тьюринга. Применение машин Тьюринга к словам. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов). Машины Тьюринга и современные электронно-вычислительные машины.

Рекурсивные функции. Основные понятия теории рекурсивных функций и тезис Черча.

Марковские подстановки. Нормальные алгоритмы и их применение к словам. Нормально вычислимые функции и принцип нормализации Маркова. Эквивалентность различных теорий алгоритмов.

Последнее изменение: понедельник, 28 сентября 2026, 09:42