MIPT-TCS-24-Lect-sn1

Теоретическая информатика в МФТИ. Темы: приложение коммуникационной сложности: нижняя оценка времени распознавания палиндромов на одноленточной МТ; колмогоровская сложность; доказательство Чейтина для 1-ой т. Гёделя о неполноте.