Плиско В.Е. - Введение в математическую логику - 3. Математические модели вычислимости

00:00:14 Вступление. Машина Тьюринга 00:10:49 Программа. Применение правила 00:17:49 Вычисление. Вычисление функции 00:24:53 Примеры. Программа для сложения. Программа для перемещения первой буквы слова в конец 00:33:17 Тезис Тьюринга. Базисные функции и операция подстановки. Примеры 00:42:58 Операция рекурсии. Примитивно рекурсивные функции. Примеры 00:49:31 Операция минимизации. Частично-рекурсивные функции. Примеры 00:56:51 Теорема о связи между классом частично-рекурсивных функций и классов вычислимых по Тьюрингу функций. Тезис Чёрча. Машина с неограниченными регистрами (МНР) 01:05:58 Вычисление. МНР-вычислимые функции. Примеры 01:18:07 Соединение программ. Использование подпрограмм. Реализация подстановки на МНР 01:29:56 Реализация рекурсии на МНР. Реализации минимизации на МНР. МНР-вычислимость частично-рекурсивных функций 01:37:57 Частично-рекурсивность МНР-вычислимых функций. Заключение Ссылка на плейлист: #математическаялогика