Основы вычислимости и теории сложности. Лекция 5
ЛекцияПартнёр:
Предмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
17.10.12
Дата публикации:
17.10.12
Код для блога:
Арифметическая иерархия. Колмогоровская сложность
Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.
Страница лекции на сайте Computer Science Center
Другие лекции курса
11