Лекция 3. Математические модели вычислимости

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