Конвеевская "Жизнь" Впервые я прочитал о ней в незапамятные времена в журнале "Наука и жизнь". Никакого программируемого вычислителя у меня тогда не было, лишь убогая доска для 100-клеточных магнитных шашек. Потом были популярные книжки М.Гарднера, реализация при помощи битовых массивов на Алголе-68 для ЕС ЭВМ в пакетном режиме и на Форте прямо в паре экранных буферов терминала ЕС 7970.
С тех пор случилось много прекрасного и удивительного. В частности, появились
сайт и продвинутая реализация
Golly.
Внутри этой реализации имеется алгоритм HashLife, основанный на вариации на тему глобального изведения общих подвыражений. Алгоритм способен демонстрировать парадоксальную независимость вычислительных расходов от числа занятых клеток. Достаточно выбрать алгоритм HashLife, включить HyperSpeed и автоматический zoom, выбрать паттерн Life/Miscellaneous/Cambrian-Explosion.rl
e и наблюдать, как скорость вычисления поколений
растет вместе с числом живых клеток и площадью занятого пространства.
На самом деле, конечно, никакого парадокса тут нет, но тем не менее наглядный урок одержимым оценкой сложности алгоритмов.