Это ЖИЗНЬ!

Дата: 04.02.14
Автор:
21 комментарий


В 1950 году один из „отцов кибернетики“ Джон фон Нейман рассмотрел проблему самовоспроизводящейся машины — то есть такая машина должна была создать собственную копию, которая затем тоже создала бы копию себя и так далее. Он выбрал довольно реалистичную математическую модель (машина состояла из разнотипных деталей, изначально находящихся в разных местах) и тем изрядно усложнил себе задачу, но всё же смог её решить. Было доказано, что машины могут размножаться.

А двадцатью годами позже Джон Конвэй (тёзка, соотечественник и коллега Неймана, тоже довольно известный математик) подошёл к подобному вопросу с другой стороны. Вместо сложной машины он рассмотрел совсем простенькую машинку — настолько простую, что она больше напоминала элементарный живой организм (ЭЖО) — и стал изучать поведение их колоний. На повестке дня стояло два вопроса:

  • Может ли колония ЭЖО размножаться неограниченно? Иными словами, можно ли создать такую конфигурацию из ЭЖО, которая с ростом времени будет увеличивать свою численность так, что та превзойдёт любое наперёд заданное число?
  • Может ли колония ЭЖО размножаться регулярно? Иными словами, можно ли создать такую конфигурацию из ЭЖО, которая рано или поздно воспроизведёт свою копию?

Придуманные Конвэем организмы оказались настолько интересными, что он на некоторое время отвлёкся от этих вопросов. (: В современных математических терминах ЭЖО можно охарактеризовать как „клеточный автомат на 1-окрестности ортогональной сетки с правилом поведения s23/b3“, но на самом деле всё гораздо проще, чем может показаться по этим устрашающим словам. (:

Сейчас объясню по-человечески. Представьте себе плоскость, расчерченную на квадратные клетки (вроде шахматной доски), и в каждой клетке может быть (а может и не быть) один ЭЖО. У клетки есть восемь соседних клеток (четыре диагональных и четыре ортогональных), про которые можно сказать то же самое. В зависимости от соседства происходит следующее:

  • Если у ЭЖО есть два или три соседа, то он продолжает жить. Иначе в следующий временной такт („в следующем поколении“) он умирает от одиночества или перенаселения.
  • Если у пустой клетки есть ровно три ЭЖО-соседа, то они в следующий временной такт рождают на этой клетке новый ЭЖО.
  • Рождения и смерти происходят одновременно и независимо друг от друга. Иными словами, если ЭЖО в следующем поколении должен умереть, то это не мешает ему стать родителем, но потомок не сможет спасти его от смерти.

Это все правила, и они очень просты. Что же такого интересного нашёл в них Конвэй? (:

А вот что. Очень быстро он обнаружил несколько конфигураций, которые периодически воспроизводили себя, но со сдвигом относительно прежнего положения! Иными словами, колонии ЭЖО показали способность к перемещению. Вот четыре вида таких колоний, обнаруженные первыми:

Это жизнь

Они получили названия (слева направо): „глайдер“ (Glider, в российских переводах превращавшийся то в „планер“, то в „глиссер“, что по ряду причин идеологически неверно), „малый космический корабль“ (LWSS), „средний космический корабль“ (MWSS), „тяжёлый космический корабль“ (HWSS). „Глайдер“ движется диагонально, смещаясь на одну клетку за четыре поколения, а „корабли“ ортогонально на две клетки за четыре поколения (при этом они „выбрасывают гаснущие искры“). Этот процесс нетрудно проследить и без помощи компьютера.

Конвэй усмотрел здесь некий физический аналог реального мира. Поскольку ЭЖО за одно поколение может породить что-то на расстоянии лишь одной клетки от себя, то в их мире скорость „одна клетка за одно поколение“ является своеобразной „скоростью света“. Оказалось, что в диагональном направлении ничто не может двигаться со скоростью больше четверти световой, а в ортогональном — больше половины. Однако если речь идёт не о перемещении „материи“ (=структуры ЭЖО с самосохранением формы), а о передаче сигнала, то световая скорость вполне достижима. Это самые азы; обнаружились и другие интересные аналогии, коими я не буду вас сейчас грузить. (:

Потом обнаружились структуры, способные поглощать движущиеся объекты или менять направление их движения. Вот рисунок из моей тетради 1988 года, изображающий найденные закономерности поглощения:

Это жизнь

После этого придумка Конвэя перешла из статуса научной теории в разряд увлекательной забавы. (: В 1970 году знаменитый Мартин Гарднер опубликовал в журнале „Scientific American“ несколько статей о ней, получившей название „Игра в Жизнь“. Энтузиасты буквально накинулись на исследования и собственные построения. В СССР первая публикация о „Жизни“ проскочила почти сразу — в 1971 году, в августовском номере „Науки и Жизни“, затем там же в 1972 году, тоже в августе. Там, правда, игра упоминалась под названием „Эволюция“. Потом отметился журнал „Квант“ в сентябре 1974. Следующий всплеск интереса (под который попал и я) был уже в 1987 году, после февральской статьи в „Юном технике“… ну а на следующий 1988 год вышла на русском языке книга Гарднера „Крестики-нолики“, в которой „Жизни“ посвящались аж три главы.

Хотя все эти публикации и несли полезную информацию, выяснять детали приходилось самостоятельно — именно так и родился мой вышеприведённый рисунок. Потом уже я подключил к делу компьютер. (:

Но вернёмся к двум проблемам размножения, о которых я говорил в начале статьи. Тогда, в далёком 1970-м, Конвэй склонялся к отрицательному ответу в обоих случаях. Эксперименты показывали, что после эволюций (иногда довольно долгих) конфигурации либо исчезали, либо распадались на группы элементов трёх родов: стабильные, не меняющиеся во времени; осциллирующие, повторяющие своё состояние каждые несколько поколений; прямолинейно перемещающиеся „космические корабли“. Примеры „кораблей“ я уже приводил, а вот примеры других элементов:

Это жизнь

В верхнем ряду три самые известные стабильные группы: „блок“, „улей“ и „лодка“; в нижнем — три известных осциллятора: „мигалка“, „восьмёрка“ и „жаба“.

Конвэй объявил, что готов выплатить премию ($50 из своего кармана) тому, кто докажет возможность неограниченного роста популяции ЭЖО, то есть обоснует положительный ответ на первый из вопросов. Уже в ноябре того же 1970 года он признал свою неправоту и выписал чек группе ребят из MIT, которые сделали замечательное открытие. Вот оно:

жизнь

Эта штука, названная „ружьём Госпера“, через некоторое время генерирует глайдер, и затем каждые 30 поколений генерирует новый. Таким образом, численность популяции на плоскости возрастает в среднем на 1/6 организма за поколение и неограниченно увеличивается!

Что же касается второго вопроса, то в начале 1980-ых было доказано, что „Жизнь“ допускает построение эквивалента машины Тьюринга, способной решить любую алгоритмизируемую проблему. В свете результата Неймана это означает и возможность самовоспроизведения структуры. А в 2002 был опубликован рецепт такого „универсального конструктора машин Тьюринга“.

Но довольно теорий и историй. Чтобы вы поняли возможности „Жизни“ и заодно усвоили её терминологию, вот вам небольшой словарик:

  • Космический корабль (spaceship) — конфигурация, через определённое число поколений воспроизводящая свою начальную форму со сдвигом. Наименьший „космический корабль“ — глайдер.
  • Осциллятор (oscillator) — конфигурация, через определённое число поколений воспроизводящая свою начальную форму на том же месте.
  • Пожиратель (eater) — конфигурация, способная уничтожить оказавшуюся рядом с собой другую конфигурацию и восстановить после этого свою форму.
  • Отражатель (reflector) — конфигурация, при столкновении с которой космический корабль изменяет направление своего движения.
  • Ружьё (gun) — конфигурация, способная периодически генерировать космические корабли.
  • Долгожитель (methuselah) — простая конфигурация, эволюция которой длится очень долго (т.е., число поколений, во много десятков раз большее числа начальных ЭЖО).
  • Райский сад (eden’s garden) — конфигурация, которая не может получиться в результате эволюции никакой другой конфигурации.
  • Фитиль (wick) — конфигурация повторяющейся структуры, постепенно исчезающая с одного конца.
  • Паровоз (puffer) — конфигурация, движущаяся подобно космическому кораблю, но оставляющая за собой следы движения.

Чтобы вы представили себе, чего можно замутить из таких элементов, вот вам пример творчества фанатов игры:

Анимированный GIF (откроется в новом окне, 1.4 мегабайта)

Цвета на этой картинке используются исключительно для наглядности. Синими „блоками“ выложены дорожки, по которым путешествуют „космические корабли“ разных типов.

Ну и теперь о том, как этим можно развлекаться на iPad. Существует немало приложений, реализующих „игру Жизни“ под iOS, я же расскажу о двух бесплатных.

Первое из них называется просто и без затей — „Игра Жизнь“. Собственно, оно и само именно такое простое-незатейливое.

Жизнь

Нехитрый интерфейс с максимальным полем размерности 120. Медленная обработка ситуации — примерно одно поколение в секунду. Сохранение и загрузка конфигураций не предусмотрены, можно только сделать скриншот.

Можно было и не упоминать это приложение, но оно имеет одно существенное достоинство: русский язык. В нём, по крайней мере, не запутаешься. Предусмотрен краткий рассказ о „Жизни“ и небольшая коллекция известных конфигураций с пояснениями. Эта последняя скрывается за кнопкой „Паттерны“ и выглядит примерно так:

Жизнь на iPad

В общем, неплохая игрушка для самого начального знакомства, но не более того.

Другое приложение, напротив, весьма продвинуто. Оно называется „Golly“ и его авторы довольно известны в математическом мире. Томашу Рокики, например, принадлежат несколько доказательств, касающихся оптимальных стратегий сборки кубика Рубика

Как оно выглядит, вы можете видеть на самой первой иллюстрации к данной статье. А вообще Golly — это кроссплатформенное приложение, существующее и для PC и для Mac. У него очень мощные возможности, включающие эмуляцию и других клеточных автоматов. Можно также подключать свои собственные сценарии, определяющие, например, правила окраски ЭЖО.

В iOS-версии часть этого дополнительного функционала ушла, но всё равно мощь приложения огромна. Достаточно сказать, что поле здесь может иметь размеры до 1000, а в секунду могут обрабатываться десятки поколений. Результаты можно сохранять и загружать, да и предустановленная коллекция примеров впечатляет. Дабы вы получили представление о возможностях программы (и, опять же, „Жизни“ как таковой), вот вам небольшое видео:

Колония ЭЖО численностью порядка девяти тысяч особей генерирует бегущей строкой название приложения. Причём вместо буквы „О“ используется изображение фазы так называемой галактики Кока, показанной на скриншоте чуть ранее.

Такая вот забава. Которая, если вдуматься, не такая уж и забава. „Жизнь“ внесла колоссальный вклад в теорию алгоритмов, методы параллельных вычислений, распознавание образов, обработку изображений… и много чего ещё.

Возможно, и вам удастся обнаружить что-нибудь новое.

Михаил Баландин специально для ipadstory.ru

1 звезда2 звезды3 звезды4 звезды5 звёзд (Ещё никто не присваивал рейтинг статье. Будьте первым!)
Загрузка...


Google Plus:
Twitter:
ВКонтакте:
Facebook:
21 комментарий к записи: “Это ЖИЗНЬ!”

  1. Мм:

    класс, обожаю Ваши обзоры, Михаил. Так интересно рассказываете о науке :)

    [Ответить]

    Дмитрий Reply:

    Солидарен. Про себя я даже больше скажу — примерно 85% всего моего интереса принадлежит именно статьям Михаила. В игры я не играю, приложения использую крайне редко, а вот узнать что-то интересное и необычное из статей такого рода — это святое.

    [Ответить]

    sputnik1818 Reply:

    Даже у меня так:) Свои то статьи я не читаю.
    А статьи Михаила читаю дважды — один раз перед размещением поверхностно, а потом уже проверенный вариант на сайте вникая подробней.
    По теме — я знал, что рано или поздно, статья про «Жизнь» у нас появится. У меня диплом был очень косвенно с этой темой связан. Тот Gif что представлен в статье ещё цветочки. Моя движущаяся картинка (смотрели на проекторе) так заворожила комиссию, что они решили диплом отправить на какой-то конкурс.
    Я отказался, так как знал о просчетах в самом дипломе, а доделывать не хотел. Теперь вы понимаете, что такая статья для меня чуть больше, чем просто познавательный материал. Пожалуй, стоит её повесить в «Статья недели» :)

    [Ответить]

    Дмитрий Reply:

    А Ваша картинка сохранилась? Очень интересно было бы глянуть!
    Понимаю Вас прекрасно :)
    Отличная идея! Эта статья того заслуживает :)

    [Ответить]

    Кирилл Reply:

    я бы тоже очень хотел бы взглянуть на проэект sputnik’a

    [Ответить]

    sputnik1818 Reply:

    Мне кажется он безвозвратно утерян. Я лично не храню.
    Возможно, в университете у преподавателя моя работа осталась, ну или в архивах:)

    [Ответить]

    Кирилл Reply:

    Эх жалко…

    [Ответить]

  2. Роман:

    Ну просто лучшие статьи!! лучшие))) Потрясно!

    [Ответить]

  3. Kiwi:

    Ничего себе! Не знала! День прожит не зря, большое спасибо!)

    [Ответить]

  4. Antf:

    Я гуманитарий, ничего не понимаю, но читаю с интересом.

    [Ответить]

    SergeyF Reply:

    А я музыкант, лучше вообще промолчу.

    :)

    [Ответить]

  5. Maksim"LaFkraFt":

    Очередной заряд удовольствия!!! Спасибо афтару!!! Почаще пиши!

    А для геймеров могу сказать, что сегодня раздают бесплатно последнюю версию «modern combat»

    [Ответить]

  6. Maksim"LaFkraFt":

    Сори за грамотность, пишу за рулем ;)

    [Ответить]

  7. niks26:

    На хабре интересная статья была, про путешествие во времени. В статье той автор модернизировал «жизнь» под исследование затухания временных отклонений — очень интересно.
    Михаилу в очередной раз РЕСПЕКТ. Golly однозначно достойно внимания.

    [Ответить]

  8. sanoksan:

    Как всегда, интересно и поучительно! Михаил, спасибо за такие познавательные статьи :)

    [Ответить]

  9. Вася:

    Статьи сподвигают идти поступать учиться, причём чем дальше ,тем всё сильнее и сильнее:)

    [Ответить]

  10. Михаил:

    Какой-то сферический конь в вакууме. В общем фигня :) Лучше бы разрабатывали лекарство от рака или занились реальным мат. моделировнаием, а то взрослые вроде люди, а играют в квадратики…

    [Ответить]

    Michael Reply:

    О, я ждал подобного комментария! Большое спасибо. (: Лишнее подтверждение убожества нынешнего школьного образования, носители которого бросаются комментировать, даже не дочитав до конца. (:

    [Ответить]

    Кирилл Reply:

    :)

    [Ответить]

  11. Алексей:

    Спасибо. Про Жизнь узнал еще из Науки и жизни, в детстве любил играть в нее. У нас была простыня в клетку и на ней я раскладывал шашки.
    Не думал, что у эту игру ещё помнят. К тому же что она есть и для айпада.

    [Ответить]

  12. Mr.K.:

    Очень интересная статья! Спасибо!

    [Ответить]

Оставить комментарий