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

Арифметическая иерархия. Колмогоровская сложность
Основы вычислимости и теории сложности

Что: Лекция
Когда: Среда, 17 октября 2012, 18:30–19:50
Где: ФМЛ 239, Актовый зал

Описание

Арифметическая иерархия и ее простейшие свойства. Универсальные множества в арифметической иерархии. Строгость арифметической иерархии. Теоремы Тарского и Геделя. Системы доказательств и перечислимые множества. Колмогоровская сложность, ее невычислимость. Доказательство Чайтина теоремы Геделя о неполноте.

Видео