Эта лекция посвящена клеточным автоматам и рождению сложности из простоты.

00:00 Введение. Представление содокладчика
01:50 Проблема соответствия Поста
13:10 Булевы функции и машинки Кнута
19:20 Игра "Жизнь"
23:50 Одномерные автоматы и классификация процессов
34:03 Микрофон переходит к Тимуру: снова машины Тьюринга
36:30 Системы тегов
42:47 Циклические системы тегов
47:17 Системы глайдеров и проблемы установления эквивалентности клеточных автоматов
51:03 Язык глайдеров и последовательности де Брёйна
59:25 Почти раскрытая тайна эфира и завершение

Лекторы: Константин Владимиров, Тимур Голубович