Матлогика 27. Введение в теорию алгоритмов. Вычислимость, разрешимость, перечислимость

00:00 - Начинаем разговор об алгоритмах 07:20 - Конструктивные объекты. Слова конечных алфавитов 10:36 - Вычислимость функции 17:25 - Что такое алгоритм? 21:10 - Разрешимость множества 24:05 - Лемма 1. Если множество конечно, то оно разрешимо 26:10 - Свойства отношений разрешимых множеств 30:00 - Перечислимость множества 32:00 - Как это можно представить? Наступает cyberpunk, так сказать high tech, low life, все как водится. Но мы можем подумать о другом стиле! О steampunk! 34:32 - Из разрешимости следует перечислимость 36:50 - Свойства отношений перечислимых множеств 52:00 - Th 6. О графике 1:04:05 - Следствие 7. Если f вычислима, то dom f и rng f перечислимы 1:06:05 - Следствие 8. Если f вычислима и A перечислимо, то f[A] и f^(-1)[A] перечислим