Лекция 13

"Введение в математическую логику и теорию алгоритмов" (Л. Д. Беклемишев, мехмат МГУ) Лекция 13 (27.11.2020) 00:00 Начало лекции --- Логика предикатов 0:32 Элементарная теория модели. 1:15 Элементарная эквивалентность. 8:06 Подмодель. 10:58 Элементарная подмодель. 16:48 Теорема Лёвенгейма—Сколема. 18:57 Следствия теоремы Лёвенгейма—Сколема о существовании счётных моделей теории полей вещественных чисел, элементарной геометрии, теории множеств. 31:37 Доказательство теоремы Лёвенгейма-Сколема. 57:30 Существование элементарных подмоделей промежуточных мощностей. 59:02 Теорема Мальцева о повышении мощности модели. 1:07:37 Следствие теоремы Мальцева для формальной арифметики. --- Вычислимость 1:07:53 Понятие алгоритма. Неформальное представление об алгоритмах. 1:11:30 Частичная функция, её область определения, значения, её вычислимость. 1:15:23 Вычислительные модели. 1:18:55 Тезис Чёрча—Тьюринга. 1:23:35 Физический тезис Чёрча—Тьюринга. 1:24:59 Определение машины Тьюринга. 1:28:06 Примеры простейших машин Тьюринга.