Вычислимость, сложность и логика

Вычислимость и неразрешимые задачи

00:00 Введение. Исчисление пропозиций

11:20 Аксиомы и правила вывода

18:58 Проверять или доказывать?

27:10 Программа Гильберта и теоремы Гёделя

35:30 Машины Тьюринга

46:40 Универсальная машина Тьюринга и проблема останова

53:50 Лямбда-исчисление

1:13:00 Тезис Черча-Тьюринга

1:17:30 Простые неразрешимые задачи

1:29:45 Теорема Райса

1:34:00 Быстро растущие и частично рекурсивные функции

1:41:50 Игра в бобра

1:49:17 Возвращаясь к программе Гильберта

1:52:20 Заключение

Вычислительная сложность

00:00 Введение

04:45 Конечные автоматы

14:10 Эпсилон переходы и NFA

25:40 Автоматы с магазинной памятью

41:34 Недетерминированная машина Тьюринга, P и NP

55:20 SAT и варианты SAT

01:07:00 NP-полнота и теорема Кука

01:15:11 Cведения к SAT и друг другу самых разных задач

01:52:15 TAUT и co-NP

02:02:41 QBF и класс PSPACE

02:20:10 Заключение

Источник: vk.com

Комментарии: