City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Арифметическая иерархия. Колмогоровская сложность
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 17 October 2012, 18:30–19:50
Where: ФМЛ 239, Актовый зал

Description

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

Video