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

Общая информация
ЛекторД. М. Ицыксон
Семестросень 2011
Дата начала14.09.2011
Количество пар12
Язык курсарусский
Вопросы к экзамену
Анонсы
Анонс habrahabr.ruhttp://habrahabr.ru/events/91/
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Лекция 1. Вычислимые функции, разрешимые и перечислимые множества.
(14.09.2011 - 18:30 - 19:50)

Вычислимые функции, разрешимые множества, определения перечислимого множества. Теорема Поста. Перечислимые множества как проекции разрешимых. Вычислимость функции и перечислимость ее графика. Универсальная функция. Вычислимая функция, которую нельзя доопределить до всюду определенной. Пример перечислимого, но неразрешимого множества. http://www.lektorium.tv/lecture/?id=13344
2. Лекция 2. Теорема Успенского-Райса, теорема о неподвижной точке.
(21.09.2011 - 18:30 - 19:50)

m-сведения, другие примеры неразрешимых множеств. Последовательность Шпеккера. Теорема Успенского-Райса. Теорема Клини о неподвижной точке. Программа, печатающая свой текст. Доказательство теоремы Клини для искуcственного языка программирования. http://www.lektorium.tv/lecture/?id=13365
3. Лекция 3. Теорема о неподвижной точки (окончание), Машины Тьюринга.
(28.09.2011 - 18:30 - 19:50)

Главные универсальные функции. Вывод теоремы Успенского-Райса из теоремы Клини. Машины Тьюринга. Неразрешимость проблемы равенства слов в полугруппе (выводимости в одностороннем и двустороннем ассоциативном исчислении). Определение примитивно рекурсивных функций. http://www.lektorium.tv/lecture/?id=13366
4. Лекция 4. Примитивно рекурсивные и частично рекурсивные функции.
(05.10.2011 - 18:30 - 19:50)

Примитивно рекурсивные функции: примеры. Примитивная рекурсивность вычислимых функций за примитивно рекурсивное время. Частично рекурсивные и вычислимые функции. Теорема о нормальной форме. Функция Аккермана. http://www.lektorium.tv/lecture/?id=13367
5. Лекция 5. Функция Аккермана. Пропозициональные формулы.
(12.10.2011 - 18:30 - 19:50)

Оценка примитивно рекурсивных функций функцией Аккермана. Функция Аккермана не является примитивно рекурсивной. Перечислимые множества и системы доказательств. Пропозициональные формулы, КНФ, ДНФ. Метод резолюций для исчисления высказываний. Связь с алгоритмами расщепления. http://www.lektorium.tv/lecture/?id=13375
6. Лекция 6. Предикатные формулы. Арифметика.
(19.10.2011 - 18:30 - 19:50)

Предикатные формулы (формулы I-го порядка). Интерпретации. Выразимость в арифметике. Арифметичность графика вычислимой функции. http://www.lektorium.tv/lecture/?id=13408
7. Лекция 7. Арифметическая иерархия.
(26.10.2011 - 18:30 - 19:50)

Арифметическая иерархия. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Прямое доказательство теоремы Геделя о неполноте. http://www.lektorium.tv/lecture/?id=13412
8. Лекция 8. Невыразимость: автоморфизмы и эллиминация кванторов.
(02.11.2011 - 18:30 - 19:50)

Невыразимость: метод автоморфизмов. Элиминация кванторов. Простейшие примеры. Задача о разрезании квадрата на меньшие квадраты. http://www.lektorium.tv/lecture/?id=13424
9. Лекция 9. Элиминация кванторов в элементарной теории вещественных чисел.
(09.11.2011 - 18:30 - 19:50)

Элиминация кванторов в теории вещественных чисел (алгоритм Тарского). http://www.lektorium.tv/lecture/?id=13441
10. Лекция 10. Полнота исчисления предикатов.
(16.11.2011 - 18:30 - 19:50)

Предваренная нормальная форма. Скулемизация. Эрбрановская интерпретация. Теорема Эрбрана. Теорема о полноте исчисления предикатов (множество тавтологий является перечислимым множеством, метод резолюций для исчисления предикатов). Теорема о полноте в сильной форме. http://www.lektorium.tv/lecture/?id=13456
11. Лекция 11. Теории и модели.
(23.11.2011 - 18:30 - 19:50)

Теорема о компактности. Аксиомы равенства. Неразрешимость множества тавтологий. Теорема о полноте для нормальных моделей. Аксиоматизация теорий с помощью элиминации кванторов. Примеры теорий. http://www.lektorium.tv/lecture/?id=13466
12. Лекция 12. Ультрафильтры и теорема о компактности.
(30.11.2011 - 18:30 - 19:50)

Фильтры: определение, примеры. Главные фильтры, ультрафильтры, ультрафильтры на конечном множесве, бесконечные неглавные ультрафильтры. Продолжение фильтра до ультрафильтра. Ультрафильтры и игры. Ультрафильтровое произведение интерпретаций, теорема Лося об ультрафильтрах. "Конструктивное" доказательство теоремы о компактности. Пример применения теоремы о компактности: продолжение частичного порядка до линейного. http://www.lektorium.tv/lecture/?id=13477
13. Лекция 13. Колмогоровская сложность.
(07.12.2011 - 18:30 - 19:50)

Колмогоровская сложность относительно декомпрессора, оптимальный декомпрессор. Простейшие свойства колмогоровской сложности. Невычислимость неограниченной нижней оценки на колмогоровскую сложность. Доказательство Чайтина теоремы Геделя о неполноте. Нижняя оценка на сложность копирования слова на одноленточной машине Тьюринга. Доказательство бесконечности простых чисел с помощью колмогоровской сложности. http://www.lektorium.tv/lecture/?id=13494
Ваша оценка: Пусто Средняя: 3.4 (5 votes)
Share |