2. Жизнь диктует свои законы, или Клеточные автоматы и машинная графика
2.
Жизнь диктует свои законы,
или Клеточные автоматы и машинная графика
Жизнь — это многоклеточное сообщество, населяющее пустыни Флатландии. Пустыня представляет собой квадратную решетку, каждая ячейка которой вмещает одну клетку Жизни. Мерой течения времени служит смена поколений Жизни, приносящая в колонию клеток смерть и рождение.
Чтобы проследить за историей развития колонии, разместим в пустыне клетки Жизни в их начальном положении. Смена поколений будет происходить по следующим правилам.
1. Соседями клетки считаются все клетки, находящиеся в восьми ячейках, расположенных рядом с данной по горизонтали, вертикали или диагонали.
2. Если у некоторой клетки меньше двух соседей, она погибает от одиночества. Если клетка имеет больше трех соседей, она погибает от тесноты.
3. Если рядом с пустой ячейкой окажется ровно три соседние клетки Жизни, то в этой ячейке рождается новая клетка.
4. Гибель и рождение происходят в момент смены поколений. Таким образом, гибнущая клетка может способствовать рождению новой, но рождающаяся клетка не может воскресить гибнущую, и гибель одной клетки, уменьшив локальную плотность населения, не может предотвратить гибель другой.
Так, например, колония ??? превращается в следующем поколении в ? а колония °° должно быть, живет неподалеку от райского Палм-Спрингс, поскольку она вообще никогда не меняется. На рис. 2.1 показана история еще одной колонии клеток Жизни.
Тема. Напишите программу, моделирующую колонию Жизни. Исходными данными служит начальное расположение клеток, а в качестве результата нужно получить вид сверху всех поколений колонии. Для вывода истории можно воспользоваться обычным устройством построчной печати (АЦПУ), но такой способ дает весьма неприглядные изображения. Если в вашем распоряжении имеется графопостроитель или графический терминал, воспользуйтесь их возможностями для получения более изящной картинки.
Рисунок 2.1. История одной колонии Жизни. Номер поколения выписан слева от каждой картинки. Найдите самостоятельно поколения 9 и 10.
Рекомендации исполнителю. Хотя этого и не видно из примеров, некоторые колонии разрастаются невероятным образом при весьма скромных начальных размерах. Есть другие колонии, которые медленно перемещаются по пустыне, переходя на все новые и новые территории. Ваша программа должна обрабатывать большие колонии без чрезмерной траты памяти или времени. Многократный просмотр большого массива для построения следующих поколений — это банальный подход; здесь программистская задача состоит в выборе более экономичных структур данных и алгоритмов. Вам, возможно, захочется испытать какой-либо метод, отслеживающий только занятые квадраты. Растущая или движущаяся колония может выйти из поля зрения, если его положение и границы зафиксированы, поэтому, вероятно, понадобится еще и метод вывода, перемещающий нашу точку зрения вслед за изменениями колонии[6].
Инструментовка. Для этой задачи подойдет язык APL благодаря наличию в нем операций над векторами и матрицами, однако можно использовать почти любой язык высокого уровня, если в нем предусмотрена работа с массивами. На примере этой задачи хорошо изучать, как сказывается использование языка ассемблера: насколько замедляется программирование и каков выигрыш в эффективности внутреннего цикла. Наконец, для тех, кто имеет доступ к оборудованию ЭВМ, интересным экспериментом могла бы быть микропрограммная реализация; машина при этом превращается в колонию Жизни.
Длительность исполнения. Одному исполнителю на 3 недели.
Развитие темы. Колония может все время расти, непрерывно меняя свое расположение, форму или число клеток. Однако чаще колония становится в конце концов стационарной, начиная циклически повторять один и тот же конечный набор состояний. Длина цикла называется периодом колонии. (По этому определению период мертвой и пустой колонии равен единице.) Измените вашу программу так, чтобы она выявляла стационарные колонии и сообщала о них. Можете ли вы придумать хоть какой-нибудь алгоритм, не использующий запоминания всех предыдущих поколений, который мог бы распознать любую стационарную колонию?
История колонии Жизнь зачаровывает, если ее просматривать как фильм (это одно из соображений в пользу графического терминала), но она будет еще увлекательней, если предстанет в цвете. Каждой клетке при рождении может быть приписан некоторый цвет, определяемый, возможно, ее поколением или генами, переданными ей родителями. Циклические, но при этом движущиеся колонии (а таких немало) великолепны в своем сверкающем многоцветном наряде.
Любая колония имеет преемника, но не у каждой есть предшественник. Такие изолированные колонии называются садами Эдема. Сад Эдема можно увидеть, только если поместить его на плоскость в качестве начальной конфигурации. Подумайте, как использовать вашу программу для нахождения сада Эдема.
Литература
Беркс (ред.) (Burks A. W. (Ed.)). Essays on Cellular Automata. University of Illinois Press, Urbana, IL, 1970.
Кодд (Codd E. F.). Cellular Automata. Academic Press, New York, NY, 1968.
Обе эти книги значительно серьезнее статей Гарднера в Scientific American. Вторая из названных книг познакомит вас с основами предмета, а книга Беркса представляет собой сборник разнородных статей, охватывающих всю область клеточных автоматов. После изучения этих книг читателю будет доступен практически весь математический материал.
Гарднер (Gardner Martin). Mathematical Games. Scientific American, 223, 10, pp. 120–123, October 1970, and 224, 2, pp. 112–117, February 1971. [Имеется перевод: Гарднер М. Математические досуги. — Мл Мир, 1972, с. 458.]
Мартин Гарднер описал игру Жизнь в своей колонке журнала, и это вызвало такой отклик читателей, что он вынужден был немедленно (по меркам ежемесячного журнала) посвятить ей еще одну колонку. Игра Жизнь, несомненно, принесла славу Джону Хортону Конвею, ее талантливому и продуктивному изобретателю. В более поздних статьях содержится много дополнительного материала об игре Жизнь, а также о других работах Конвея.
Уэйнрайт (ред.) (Wainwright R. Т. (Ed.)). Lifeline. 1280 Edcris Road, Yorktown Heights, NY 10598.
Lifeline — ежеквартальный журнал, посвященный Жизни и родственным темам. Ориентированный на фанатиков этой игры, журнал содержит всевозможную информацию о Жизни, и его чтение может оказаться захватывающим занятием.
Более 800 000 книг и аудиокниг! 📚
Получи 2 месяца Литрес Подписки в подарок и наслаждайся неограниченным чтением
ПОЛУЧИТЬ ПОДАРОКЧитайте также
Пакет Автоматы
Пакет Автоматы Пакет Автоматы специфицирует поведение при построении моделей с использованием систем переходов для конечного множества состояний. В нем определено множесто понятий, которые необходимы для представления поведения модели в виде дискретного
6.1. Автоматы
6.1. Автоматы Автомат (state machine) в языке UML представляет собой некоторый формализм для моделирования поведения элементов модели и системы в целом. В метамодели UML автомат является пакетом, в котором определено множество понятий, необходимых для представления поведения
Машинная архитектура высокого уровня
Машинная архитектура высокого уровня Истинная независимость от аппаратуры может быть достигнута, если вместо определения отдельных API для разных специфических приложений (что имеет место в случае такой API-ориентированной архитектуры как Single Unix Specification), будет формально
§ 99. Законы дизайна
§ 99. Законы дизайна 26 января 2003В дизайне законов нет. Не было и не будет.Есть рекомендации, советы, житейский опыт. Есть «десять главных ошибок» и «семь золотых правил». А законов нет.Если бы дизайн был наукой (а дизайн — это такая же наука, как шахматы — спорт), можно было
Основные законы теории цепей
Основные законы теории цепей При изучении электрических цепей широко применяется второй закон Кирхгофа, согласно которому алгебраическая сумма напряжений на замкнутом контуре равна 0. Первый закон Кирхгофа относится к токам, подходящим к узлу, и утверждает, что
Конечные автоматы и альтернативы
Конечные автоматы и альтернативы Я упомянул, что регулярные выражения могут анализироваться с использованием конечного автомата. В большинстве книг по компиляторам а также в большинстве компиляторов, вы обнаружите, что это применяется буквально. Обычно они имеют
Конечные автоматы
Конечные автоматы Подпрограмма анализа типа GetName действительно реализует конечный автомат. Состояние неявно в текущей позиции в коде. Очень полезным приемом для визуализации того, что происходит, является синтаксическая диаграмма или «railroad-track» диаграмма. Немного
Глава 10. Конечные автоматы и регулярные выражения.
Глава 10. Конечные автоматы и регулярные выражения. Существует целый класс проблем, которые могут быть решены с помощью авторучки и бумаги. По-моему, это замечательный аспект программирования: иметь возможность графически представить какой-либо процесс, а затем
Конечные автоматы
Конечные автоматы В отличие от большинства рассмотренных в этой книге алгоритмов, конечные автоматы - это технологии, призванные облегчать разработку других алгоритмов. Они служат средством достижения конечной цели - реализации алгоритма. Тем не менее, как будет
Детерминированные и недетерминированные конечные автоматы
0
Кафедра Ваннаха: Информация, тайны, законы Ваннах Михаил
Кафедра Ваннаха: Информация, тайны, законы Ваннах Михаил Опубликовано 19 августа 2010 года Всякий раз, когда мы слышим разговоры о модернизации национальной экономики, мы должны понимать, что речь на самом деле идёт об эвентуальных попытках
Глава 2 Законы безопасности
Глава 2 Законы безопасности В этой главе обсуждаются следующие темы: • Обзор законов безопасности • Закон 1. Невозможно обеспечить безопасность клиентской части • Закон 2. Нельзя организовать надежный обмен ключами шифрования без совместно используемой порции
Лучшая жизнь в трехмерном онлайне: Жизнь в метаверсе как часть «просто жизни»
Лучшая жизнь в трехмерном онлайне: Жизнь в метаверсе как часть «просто жизни» Автор: Анатолий ЛевенчукЯ не буду даже обсуждать многопользовательские онлайн-игры — где есть понятие квеста, где есть геймплей. Я буду обсуждать метаверсы — многопользовательские
Законы:
Законы: Computer Misuse Act 1990 (UK)Crimes Act 1914 (no. 5) (cwlth)Crimes Legislation Amendment Act 1989, no. 108Computer Fraud and Abuse Act 1986 (us), 18 usc 1030Computer Misuse Crimes Legislation Amendment Bill 1989 (aus),Explanatory Memo Clause 7 Crimes (Computers) Act, no. 36 of 1988
Тактика № 4: используйте существующие законы и добивайтесь принятия новых
Тактика № 4: используйте существующие законы и добивайтесь принятия новых Сегодня мы имеем огромное количество принятых законов, защищающих приватность. Печально, но очень мало потребителей знает о своих правах. Доступные сегодня средства уже давно используются в