Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Лекция 13. Колмогоровская сложность.
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 01 декабря 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

Сложность относительно декомпрессора. Оптимальный декомпрессор. Свойства колмогоровской сложности. Вычислимые функции и перечислимые множества. Невычислимость нетривиальной нижней оценки на колмогоровскую сложность. Доказательство Чайтина первой теоремы Геделя о неполноте. Доказательство бесконечности простых чисел. Нижняя оценка на время работы одноленточной машины Тьюринга, распознающей палиндромы.