Джон Конвей и клеточные автоматы (original) (raw)
Кажется, никакая книга, никакая научная теория не могла бы доказать мне происхождение сложного из простого так наглядно, как это сделала банальная игра, придуманная далёким британским математиком. На листе бумаги в клеточку рисуется несколько "живых" клеток - в отличие от пустых мертвых, они помечены каким-нибудь символом вроде "звёздочки". А дальше на каждом шаге происходит обновление всего поля, на основе простых правил. Каждая клетка смотрит на своих соседей - восемь соседних клеток. Та клетка, у которой больше трёх живых соседей, умирает от тесноты (или, как сказали бы сейчас, "от нарушения режима самоизоляции"). Клетка, у которой меньше двух живых соседей - умирает от одиночества. А если у какой-то пустой клетки оказалось ровно три соседа, там рождается новая живая.
Этой странной игре была посвящена одна из первых программ на Алголе-68, которые я писал в интернате в 1987 году. Кажется, я всего только две работающие программы и написал на этом языке. Просто в то время школьнику сделать работающую программу - это был целый проект на много дней, с походами в далёкий вычислительный центр на заданное "машинное время", с мудрёными процедурами сохранения и и распечатки программ, не говоря уже об их мучительной отладке. Первая моя школьная программа рисовала спираль Архимеда, а вторая - позволяла запускать "Жизнь". Картинка рисовалась символами "звёздочка" на тёмно-зелёном экране, и вычислялась большим шкафом из серии ЕС ЭВМ. За соседней дверью Андрей Терехов клепал свои "Эльбрусы" и "Самсоны". А я просто пялился на узоры "Жизни".
Позже, на матмехе, это увлечение вылилось в дипломный "Универсальный имитатор клеточных автоматов", написанный на крутом языке Forth (плюс немножко ассемблера для ускорения). В этом имитаторе можно было задавать разные правила клеточной жизни и разные окрестности. А сами клетки имели до 16 возможных состояний (а не только два, как в "Жизни"). Никто из окружающих не понимал этого сумасшедшего хобби - ну, кроме тех, кто пробовал ЛСД.
Это было самое начало лихих 90-х, наука в России никому была не нужна, и уж тем более - такие вот странные картинки. Но неожиданно нашёлся научный руководитель для моей диссертации - доктор Сергей Баранов из СПИИРАН, автор первого русского Forth-транслятора. Правда, его не клеточная жизнь интересовала, а именно приложения "Форта". За несколько лет до этого в MIT построили "Машину клеточных автоматов", о ней вышла книжка Тоффоли и Марголуса, и все примеры клеточных правил там были на "Форте". Мы с доктором Барановым прочли эту книжку одновременно, независимо друг от друга. И после этого оба, ещё не зная друг друга, написали свои версии такой машинки.
Доктор Баранов своей версией хотел показать американцам, что может имитировать все их параллельные вычисления даже на обычной персоналке (если писать на крутом языке Forth). И он действительно повторил все примеры из книжки Тоффоли и Марголуса, при этом его имитатор, вместе с редактором клеточных правил и скоростным выводом клеточного "кино" на экран, весил всего лишь 29 килобайт (интересно, сейчас бывают программы такого размера?).
Ну а меня просто восхищала самоорганизация сложных макроструктур из простейших локальных правил. Мой имитатор был помедленнее, зато я придумывал собственные клеточные правила для моделирования всяких явлений природы. Рост снежинок и дендритов с разными законами налипания, случайное блуждание без самопересечения (короеды), правило большинства для трёх фракций (образование капель), фракталы из "ткацкого станка" одномерного автомата, повторяющего узор ракушек-"конусов"... Желающие могут попробовать запустить эту демку на каком-нибудь не очень современном виндовом компе. Скорее всего, её заблокируют ваши антивирусы. Но даже если запустится, будет пролетать очень быстро. А 25 лет назад, при запуске на IBM PC 286, это был тормозной мультик на полчаса.
Потом я уехал в Штаты и забил на всю эту шизу, потому что увлекся японской поэзией и красивыми женщинами. Хотя нет, сначала всё-таки послал своё резюме в пару мест - в институт Макса Планка и в Brandeis University. Только в этих двух вузах я нашёл PHD-программы, напоминавшие моё увлечение. Искусственная жизнь, самособирающиеся роботы... Но у них там хватало своих претендентов на докторскую по таким сумасшедшим темам.
По возвращении в Питер мне надо было отчитаться перед доктором Барановым за бесцельно прожитые годы, поэтому я ещё разок напряг свой имитатор параллельных миров - и выступил на одной конфе с докладом о применении клеточных автоматов в распознавании образов и обработке изображений. А после этого уже окончательно забил. Сейчас я думаю, это даже хорошо, что я не свернул в эту сторону. Всё равно это кончилось бы ракетами и терминаторами.
Последним применением клеточных автоматов в моей жизни был роман "Паутина" - там фигурирует цифровой наркотик "диоксид", изобретённый (по сюжету романа) математиком Мишей Вербицким. И когда я выложил "Паутину" у себя на сайте в конце 90-х, каждая глава там кончалась иллюстрацией какого-нибудь клеточного автомата из моего заброшенного диссера.
Почему эти странные мультики-модели, крутившиеся на тысячах маленьких параллельных компьютеров, так завораживали меня?Возможно, мне просто нужно было стать биологом. На той самой олимпиаде, когда приглашали в интернат, нужно было было пойти в биологический класс. Возможно, я просто не в ту дверь зашёл. Но даже попав в компьютерно-математическую колею, я умудрился вывернуться - через вот этот поворот, который устроил в моей жизни британский математик Джон Конвей со своей простенькой игрой. А его самого на прошлой неделе подкосил простенький коронавирус. Впрочем, ему было уже 82. Он многое успел в этой жизни.
PS. С картинками я вас конечно обманул: это не конвеевская "Жизнь". Её вы и сами легко найдёте в Интернете. А тут на картинках - колонии моих клеточных автоматов. Ведь каждый, кто когда-нибудь запускал "Жизнь", наверняка задумывался о том, что будет, если немного поменять клеточное правило. Вдруг получится придумать свою версию "Жизни", ещё более удивительную, чем у Конвея? Насколько я знаю, пока ни у кого не получилось.