Матлогика 28. Свойства перечислимости. Универсальная вычислимая функция. Проблема самоприменимости

00:00 - Повторяем теорему о графике 01:30 - Полухарактеристическая функция 05:11 - Утв 1.Связь перечислимости и вычислимости полухарактерестической функции 08:30 - Утв 2. Если A непусто и перечислимо, то ∃ тотальная вычислимая функция порождающая A. 17:47 - Утв 3. A перечислимо тогда и только тогда когда ∃ B размерности на 1 больше такое, что A -- проекция B 24:38 - Th 4. Эквивалентные определения перечислимости 31:10 - T-предикат 32:55 - Свойство алгоритмов. T-предикаты разрешимы 34:15 - Th Поста. Она очень проста 38:10 - Универсальный алгоритм 38:41 - Возьмём ваш любимый язык программирования, какой? 38:53 - Универсальный алгоритм 44:04 - Универсальная вычислимая функция (У.В.Ф.) 45:00 - Универсальная вычислимая функция не похожа на морскую свинку 49:00 - Vn -- n-ое сечение V по первому аргументу 52:55 - ∃ У.В.Ф. 54:24 - T-предикаты для U 57:28 - Определения. K (dom d), S (dom U), d - Диагональ У.В.Ф. U 1:00:17 - Замечание. U вычислимо, S перечислимо, d вычислимо, K перечислимо 1:01:33 - Неразрешимость проблемы самоприменимости. Множество K неразрешимо 1:08:37 - Дополнение K неперечислимо 1:09:45 - Следствие 8. Неразрешимость проблемы остановки. 1:13:00 - Лемма 9. Если f вычислима, то ∃n, f(n) ~= d(n) 1:16:06 - Лемма 10. Функция d не имеет вычислимого тотального продолжения 1:21:14 - Лемма 11. ∃ вычислимая f из N в 2, что у f нет вычислимого тотального продолжения