Ebook: Теория алгоритмов: Учебно-методический комплекс

Елабуга: Елабужский государственный педагогический университет. – 87 с.Содержание:
Теория рекурсивных функций.
Примитивно рекурсивные функции. Базис элементарных функций. Операции подстановки и примитивной рекурсии. Основные свойства.
Примитивно рекурсивные функции относительно совокупности функций. Основные свойства.
Производные операции над функциями.
Операции конечного суммирования и конечного произведения.
Предикат, логическая функция. Логические операции с предикатами.
Операции навешивания кванторов. Операции навешивания кванторов относительно двуместных предикатов.
Примитивно рекурсивный предикат.
Операция навешивания ограниченного квантора над предикатами.
Кусочное задание функции.
Операция ограниченной минимизации.
Частично рекурсивные функции.
Уточнение понятия алгоритма через абстрактную математическую машину Тьюринга.
Определение машины Тьюринга.
Применение машин Тьюринга к словам.
Вычислимые по Тьюрингу функции.
Композиция машин Тьюринга.
Тезис Тьюринга (основная гипотеза теории алгоритмов).
Машины Тьюринга и современные электронно-вычислительные машины.
Вычислимость по Тьюрингу примитивно рекурсивных функций.
Вычислимость по Тьюрингу частично рекурсивных функций.
Уточнение понятие алгоритма через машину с неограниченными регистрами.
Марковские подстановки.
Нормальные алгоритмы Маркова.
Нормально вычислимые функции и принцип нормализации Маркова.
Совпадение класса всех нормально вычислимых функций с классом всех функций, вычислимых по Тьюрингу.