|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Каждая клетка имеет ровно восемь соседей, с которым соприкасается хотя бы в одной точке.Стр 1 из 2Следующая ⇒
Игра «Жизнь»
В данном реферате рассматривается краткая история создания данной игры, правила игры, некоторые получаемые в результате фигуры, а также возможные модификации и влияние игры «Жизнь» на развитие различных научных дисциплин.
Работу выполнила студентка 3 курса СПбПУ Воденкова Ксения, гр.33415/1
Содержание реферата
1. История создания игры 2. Классические правила игры «Жизнь» 3. Основные фигуры: 4. Устойчивые конфигурации 5. Осцилляторы 6. Планер и космические корабли 7. Планерные ружья и пожиратели 8. Сады Эдема 9. Модификации игры «Жизнь» 10. Заключение 11. Литература
История создания игры «Жизнь»
Что наша «Жизнь»? Игра!
На протяжении многих лет великие классики сравнивали человеческую жизнь с некой игрой, в которой всё подчинено жестким правилам, и победителю достаётся всё, а проигравший остаётся не с чем. В 20 веке многие учёные обратили внимание концепцию игры и предложили описывать природные явления с помощью математической игры с определенными правилами. Так возникли клеточные автоматы.
Клеточный автомат – это дискретная модель, включающая регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может иметь любую размерность. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.
Впервые клеточные автоматы были придуманы Станиславом Уламом и Джоном фон Нейманом в 1940-е годы. Станислав Уам изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана был двухмерный, а самовоспроизводящийся робот описан алгоритмически. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.
Клеточный автомат фон Неймана В данной конфигурации двоичный сигнал циркулирует вдоль петли из синих ячеек, происходит переход между обычным и возбужденным состоянием передающих ячеек. Коммутирующая ячейка дублирует сигнал в красную линию. Сигнал проходит по линии и создает новую ячейку. Двоичный сигнал 1011 кодирует восточно-ориентированное передающее состояние, таким образом продолжая линию вправо.
Примерно в это же время Норберт Винер и Артуро Розенблют разработали клеточно-автоматную модель возбудимой среды, описывающую распространение импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.
В 1970 году Джоном Конвеем был изобретён клеточный автомат, получивший название игры «Жизнь».
Джон Конвей родился в 1937 году и в настоящее время работает профессором математики в Принстонском университете. В его научные интересы входит теория конечных групп, теория чисел, теория узлов, комбинаторная теория игр и теория кодирования. Но известность Конвей получил именно как создатель игры «Жизнь», и благодаря популяризации этой игры Мартином Гарднером. Игра была придумана на обычном листке бумаге, расчерченным на клетки, ещё до того, как стали появляться первые персональные компьютеры. Первым любителям этой мыслительной забавы требовалось много времени и аккуратности, чтобы не ошибиться, но с появлением возможности реализовать игру на компьютере, началось активное исследование конфигураций и математических законов, заложенных в «Жизнь».
Портрет Джона Конвея
Классические правила игры «Жизнь»
Действие данной математической игры происходит на бесконечном поле, состоящем из квадратных клеток. Каждая клетка может быть только в одном из двух состояний: 1 и 0 (живая и мёртвая клетка соответственно). Конвей тщательно подбирал правила игры, и долго проверял их «на практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:
Короче говоря, правила должны быть такими, чтобы поведение популяции было непредсказуемым. Пример сложной эволюции конфигурации с простыми начальными данными:
В итоге были придуманы следующие очень простые правила: Если число (живых) клеток, с которыми граничит какая-нибудь пустая клетка, в точности равно трём (не больше и не меньше), то на этой клетке происходит зарождение нового «организма», то есть следующим ходом она тоже становится живой. 5. Игра прекращается, если: Триплеты Исходная конфигурация из трёх клеток (будем называть её триплетом), как правило, погибает. Выживает триплет лишь в том случае, если, по крайней мере, одна клетка граничит с двумя занятыми клетками. Пять триплетов, не погибающих на первом же ходу, изображены на рисунке. (Как расположены триплеты на плоскости — прямо, «вверх ногами» или косо, не существенно.)
Четвёртая конфигурация на втором ходу переходит в устойчивую конфигурацию — блок размером 2× 2. Пятая конфигурация служит простейшим примером так называемых флип-флопов (кувыркающихся конфигураций, возвращающихся в исходное состояние через каждые два хода). Она попеременно превращается то в вертикальный, то в горизонтальный ряд из трёх клеток. Конвей называет этот триплет мигалкой. Как правило исходные конфигурации либо переходят в устойчивые, и перестают изменяться, либо навсегда переходят в колебательный режим. Тетрамино и пентамино
Как мы уже видели, первый квадрат относится к категории устойчивых конфигураций. Вторая и третья конфигурация после второго хода переходит в устойчивую конфигурацию, называемую ульем. Ульи в игре возникают часто. Четвёртое тетрамино также превращается в улей, но на третьем ходу. Стоит отметить, что часто названия для конфигураций в игре «Жизнь» являются ассоциациями на реальные объекты нашего мира. Можно сравнить «клеточный» улей с настоящим:
Особый интерес вызывает ещё одно тетрамино, которое после девятого хода распадается на четыре отдельные мигалки (вся конфигурация носит название навигационные огни). Навигационные огни относятся к разряду флип-флопов и возникают довольно часто.
Из двенадцати фигур пентамино (фигур, состоящих из пяти клеток, связанных между собой так, что их можно обойти ходом ладьи) пять погибают уже на пятом ходу, две быстро переходят в устойчивые конфигурации из семи клеток, а четыре после небольшого числа ходов превращаются в навигационные огни. Единственным исключением является элемент пентамино, имеющий форму буквы r, превращения которого заканчиваются не столь быстро. Такие фигуры в игре «Жизнь» называются долгожителями. Подробно эволюция этого и других долгожителей рассмотрена в соответсвующем параграфе.
Устойчивые конфигурации Двенадцать наиболее часто встречающихся устойчивых конфигураций приведены на этом рисунке.
Приведём здесь ещё и некоторые более сложные натюрморты. Пасека является устойчивой конфигурацией из четырёх ульев, в которую после 14 ходов переходит горизонтальный ряд из 7 клеток. Квадрат размером 5× 5 после первого же хода переходит в конфигурацию, которая возникает лишь на четвёртом этапе эволюции семиклеточного ряда. Поэтому квадрат 5× 5 становится пасекой после 11 ходов.
Некоторые простые конфигурации можно удваивать: Библок
Двойной каравай и пекарня
Любопытное название имеют конфигурации «каноэ» и «знак интеграла»
Существует также класс натюрмортов, занимающих максимальную площадь. Задача размещения в области n × n натюрморта с максимальным числом клеток привлекала к себе внимание программистов как задача программирования в ограничениях. При стремлении размера области к бесконечности, живыми могут быть не более 50% клеток. На конечных квадратных областях можно достичь больших плотностей. Так, максимальная плотность натюрморта в квадрате 8 × 8 равна 36/64 = 0.5625 — эту плотность обеспечивает образец, состоящий из девяти блоков. Для квадратов до 20 × 20 известны на данный момент оптимальные решения. 19x19 20x20
(Изображения взяты с сайта wikipedia.org)
Осцилляторы
В «Жизни» конечные осцилляторы известны для всех периодов, кроме 19, 23, 38 и 41. Хотя существуют осцилляторы периода 34, все известные примеры считаются тривиальными, поскольку они состоят из по существу отдельных компонент, осциллирующих с меньшими периодами. К примеру, осциллятор с периодом 34 можно получить путём размещения во вселенной двух независимых осцилляторов с периодами 2 и 17. Осциллятор считается нетривиальным, если он содержит хотя бы одну клетку, период осцилляции которой равен периоду осциллятора. Самыми известными осцилляторами являются фигуры вертушки, бакена, часов и жабы.
Последние три конфигурации периодически воспроизводят себя (период равен двум ходам). По словам самого Конвея, жаба дышит, часы тикают, бакен зажигается, и в каждом случае период равен двум. Внутренняя часть вертушки с каждым следующим ходом поворачивается на 90°, а все внешние клетки остаются на своих местах. Подобные периодические конфигурации Конвей называет бильярдными столами, чтобы отличать их от истинно периодических конфигураций, таких, как, например, жаба, часы и бакен.
Следующая конфигурация называется пульсар СР 48-56-72. Она также периодически восстанавливает себя через каждые три хода. Начальное состояние пульсара образовано 48 клетками; на втором этапе число клеток возрастает до 56, а на третьем — до 72, после чего пульсар снова возвращается в исходное состояние, а число клеток понижается до 48.
А эти осцилляторы имеют забавные названия – «французский поцелуй» и «босс»:
Планер и космические корабли
Одним из самых замечательных открытий Конвея следует считать конфигурацию из 5 фишек — планер.
После второго хода планер немного сдвигается и отражается относительно диагонали. В геометрии такой тип симметрии называется скользящей симметрией, отсюда и название фигуры (По-английски планер называется glider, от glide — скользить). В результате двух последующих ходов планер «выходит из пике», ложится на прежний курс и сдвигается на одну клетку вправо и на одну клетку вниз относительно начальной позиции. Выше уже писалось, что в игре «Жизнь» введено понятие скорости света. Конвей доказал, что максимальная скорость по диагонали составляет одну четверть скорости света. Поскольку планер переходит сам в себя после четырех ходов и при этом опускается на одну клетку по диагонали, то говорят, что он скользит по полю со скоростью, равной одной четвёртой скорости света.
Космические корабли могут использоваться для передачи информации. Способность планера переносить информацию стала частью доказательства, что «Жизнь» является тьюринг-полной. (Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями.)
Планерное ружьё и пожиратели
Конвей высказал гипотезу, согласно которой не существует ни одной начальной конфигурации, способной беспредельно расти. Иначе говоря, любая конфигурация, состоящая из конечного числа клеток, не может перейти в конфигурацию, в которой число фишек превосходило бы некий конечный верхний предел. Это, наверное, одна из самых глубоких и самых сложных задач, возникающих в «Жизни». Когда описание игры появилось в октябрьском номере журнала Scientific American за 1970 год, Конвей предлагал премию тому, кто до конца года первым докажет или опровергнет его гипотезу. В ноябре 1970 года Конуэю пришлось выдать обещанную премию. Группа математиков из Массачусетского технологического института сумела построить ружьё, стреляющее планерами! Каждые 30 ходов из ружья вылетает планер. С появлением нового планера число «живых» клеток на доске увеличивается на 5, следовательно, происходит неограниченный рост популяции. Непосредственным изобретателем новой фигуры был Билл Госпер, поэтому данная конфигурация носит его имя.
Планерное ружьё Госпера
На протяжении многих лет ружьё Госпера оставалось наименьшим в игре «Жизнь» по числу клеток, хотя для других наборов правил известны меньшие ружья. Однако, в 2015 году было изобретено ружьё, создающее корабли с периодом 120 и имеющее меньшее числом клеток, но больший радиус, чем вышеописанное планерное ружьё. В дальнейшем было придумано огромное количество ружей. Но, как известно, всегда там, где появляется созидающая сила, должна возникнуть и сила разрушающая. Так, вслед за изобретением планерного ружья были найдены конструкции, названные «пожирателями». Та же группа исследователей обнаружила пентадекатлон — конфигурацию, способную «поглотить» сталкивающийся с ней планер.
Пентадекатлон может также отражать планер, изменяя курс последнего на 180°. Расположив друг против друга два пентадекатлона, можно провести между ними «теннисный матч»: они будут перекидывать планер, как мяч (период конфигурации на рисунке равен 60).
Это не единственный пожиратель в игре «Жизнь».
Все вышеперечисленные объекты являются стационарными, следовательно, не могут приблизиться к блоку. Но они могут появиться в ходе развития какого-либо неустойчивого объекта – это происходит довольно часто. И чаще всего они бывают лишними. Вот здесь и могут пригодиться блоки. В реакции, найденной Дейвом Бакинэмом, группа из четырех блоков взаимодействует с Гершелом.
  
(К сожалению, автор не нашёл изображения предпасеки.) Но особенно замечательна способность пожирателя поглощать такие объекты, как глайдеры, а также легкие и средние космические корабли. Можно также натравить двух пожирателей друг на друга. Они тут же начинают кусать друг друга, но в силу своей устойчивости через 3 поколения оба восстанавливаются - и реакция повторяются. Получается осциллятор периода 3, который так и называется " два пожирателя" или " пожиратель пожирающий пожирателя".
Долгожители
Долгожители— это такие конфигурации в игре «Жизнь», которые состоят из небольшого числа живых ячеек в начальном состоянии, но стабилизируются только спустя много поколений. Более точно Мартин Гарднер определяет их как конфигурации из 10 или меньшего числа клеток, которым необходимо не менее 50 поколений для стабилизации. Долгожители имеют любопытное название на английском языке – Мафусаил, которое происходит от имени библейского персонажа Мафусаила, прожившего 969 лет. R-пентамино При рассмотрении простых фигур уже приводилось r-пентамино, сейчас же будет подробно показана его эволюция.
Конвей проследил развитие r-образного пентамино вплоть до четыреста шестидесятого хода, после которого конфигурация распалась на множество планеров. Конвей написал, что «После сорока восьми ходов r-образное пентамино превратилось в конфигурацию, левая часть которой состоит из семи фишек, а правая — из фишек, заполняющих две симметричные области. Если бы левой части не было, то эти области развивались бы в пасеку с четырьмя ульями и навигационные огни. Возмущение, вносимое левой частью, приводит к тому, что пасека быстро вгрызается в навигационные огни и образующие их четыре мигалки гаснут одна за другой, оставляя после себя на доске „нечто бесформенное“». Эволюция r-пентамино была прослежена до конца с помощью компьютерных вычислений. Она завершается лишь после тысяча сто третьего хода. Шесть возникших на доске планеров удаляются от центра на всё большее и большее расстояние (находятся за пределами рисунка), и, в конце концов, вокруг бывшего пентамино (показано красным цветом) остаются четыре мигалки, один корабль, одна лодка, один каравай, четыре улья и восемь блоков.
Жёлудь
Другим примером долгожителя является конфигурация жёлудь, которая состоит из 7 ячеек в начальном состоянии и стабилизируется спустя 5206 поколений, оставляя на поле 633 ячейки, образующие конфигурацию дуб. В течение своего превращения из жёлудя в дуб, конфигурация выпускает множество планеров.
 
Кролики
Ещё одно забавное название имеет конфигурация-долгожитель из девяти начальных клеток. Время жизни «кроликов» составляет 17331 поколения. На рисунке можно видеть, как сильно расплодились «кролики». Как и предыдущая конфигурация, они формируют планеры в процессе эволюции.
 
Автор не стал отмечать местоположения начальной конфигурации в двух последних случаях, так как изменение масштаба между исходным изображением и изображением конечной фигуры очень велико.
Сады Эдема
У данного понятия существует довольно простое определение: садом Эдема называется конфигурация, не имеющая родителей. Тем не менее, такую конфигурацию найти совсем не просто. Термин " сад Эдема" появился в теории клеточных автоматов намного раньше, чем была придумана игра Жизнь. И его название выбрано неслучайно. Объект, не имеющий родителей, может быть внесённым в этот мир только некой внешней силой. И тут напрашивается ассоциация с Библией, в которой бог создал Райские сады или сады Эдема. Так же, как и соответствующая конфигурация в игре «Жизнь», сады Эдема развалились и смешались с окружающим миром с течением времени.
«Эдем», Лукас Кранах-старший Создатель игры Жизнь Джон Конвей не задавался вопросом, есть ли сады Эдема в игре Жизнь. Он с самого начала знал, что есть. Дело в том, что он знал теорему о садах Эдема, которая была сформулирована и доказана намного раньше, чем была придумана игра Жизнь. Она формулируется для очень широкого класса клеточных автоматов. Формулировка данной теоремы звучит так: «класс сюръективных клеточных автоматов совпадает с классом инъективных над конечными конфигурациями клеточных автоматов.» И требует некоторого пояснения. Дадим вспомогательные определения: · Конечными конфигурациями считаются такие паттерны, которые имеют конечное число живых клеток. · Инъективный клеточный автомат - это такой, в котором не существует двух отличающихся друг от друга конфигураций, отображающихся на одну и ту же конфигурацию. А отображение - это просто преобразование паттерна в результате смены поколения. Так как, в «Жизни» существуют конфигурации с множеством возможных родителей, она не является инъективной. · Отсюда инъективные над конечными конфигурациями клеточные автоматы - это такие, в которых не существует двух отличающихся друг от друга конечных конфигураций, переходящих при смене поколения в один и тот же конечный паттерн. · Сюръективными клеточными автоматами называются такие, в которых каждая конфигурация является отображением некоторой другой конфигурации. Следовательно, это клеточные автоматы, в которых все паттерны имеют родителей. Данная теорема утверждает, что все клеточные автоматы, в которых нет конечных конфигураций с двумя или более родителями, не имеют и конфигураций без родителей. И наоборот, все автоматы, в которых нет конфигураций без родителей, не имеют конечных паттернов с двумя или более родителями. Отсюда следует, что если бы в Жизни не существовало садов Эдема, то в ней бы и не было ни одной конечной конфигурации с несколькими родителями. По своей сути, сад Эдема - это всегда вся вселенная игры Жизнь в одном из ее возможных состояний. Оно отличается от других состояний тем, что никакое из возможных состояний не может породить данное состояние. Введём новый термин – сирота. Ахим Фламменкамп определяет его, как часть сада Эдема, какое-то количество живых и мертвых клеток, которое не может образоваться " естественным" путем, то есть по правилам Жизни. Есть еще понятие минимального сироты - это такой сирота, при изменении состояния любой клетки которого на противоположное он перестает быть сиротой. Ясно, что сирота - это та часть, которая делает конфигурацию садом Эдема. Во всей остальной вселенной может твориться что угодно - если на поле есть сирота, то эта конфигурация является садом Эдема. Поэтому интерес представляет именно сирота. И простейший сад Эдема с найденным сиротой - это сирота, дополненный пустым полем. Обычно в таком виде и демонстрируют сады Эдема.
Сады Эдема с сайта wikipedia.org Количество садов Эдема в игре Жизнь бесконечно. Имея даже всего одного конечного сироту, мы можем дополнять его до сада Эдема бесконечным количеством способов. Отсюда следует вопрос, каких конфигураций в игре Жизнь больше - имеющих родителей или садов Эдема. Рассмотрим ситуацию на большом, но конечном подмножестве вселенной Жизни. Рассмотрим долю сирот среди всех паттернов, умещающихся в прямоугольник A x B. Ясно, что при маленьких A или B в рассматриваемый прямоугольник не поместится ни одного сироты. Но, начиная с некоторых величин A и B, некоторые комбинации живых и мертвых ячеек окажутся сиротами. Это тоже доказуемо, но для нас достаточно того факта, что такие комбинации (в игре Жизнь) обнаружены на практике. Докажем, что сироты преобладают для некоторых достаточно больших размеров прямоугольника на поле Жизни. Причем, увеличивая размеры прямоугольника, мы можем сделать долю сирот сколь угодно близкой к 100%. Пусть доля сирот в прямоугольнике A x B равна конечному числу P. Рассмотрим прямоугольник MA x NB. Разобьем его на M x N прямоугольников первоначального размера. Все возможные комбинации живых и мертвых клеток большого прямоугольника состоят из все возможных комбинаций каждого из малых прямоугольников. При этом доля сирот в каждом из малых прямоугольников равна P. А доля не-сирот (1-P). Большой прямоугольник может оказаться не-сиротой только в том случае, когда все малые прямоугольники окажутся не-сиротами. Следовательно, вероятность, что в большом прямоугольнике не обнаружится сирота меньше, чем произведение таких вероятностей для малых прямоугольников. То есть, меньше, чем (1-P)MN. Так как (1-P) < 1, то всегда можно сделать MN достаточно большим для того, чтобы доля не-сирот большого прямоугольника оказалась меньше любого наперед заданного числа. Сады Эдема, найденные Николаем Белюченко Модификации игры «Жизнь»
Рассмотрим в этом параграфе некоторые любопытные модификации «Жизни». Семена Клеточный автомат, первоначально исследованный Брайаном Сильверманом и названный Миреком Войтовичем. Правила этого автомата схожи с правилами «Жизни», но на каждом временном шаге ячейка включается или «рождается», если она имеет ровно два соседства. Хаотическое развитие формы в «Семенах» Жизнь без смерти
Фигура «Жизни без Смерти» с сайта wikipedia.org Diamoeba (Диамоэба)
Фигуры алмазов из Диамоэбы с сайта wikipedia.org Highlife (Хайлайф)
День и ночь
Конфигурации из «Дня и ночи» с сайта wikipedia.org
Заключение
Игра «Жизнь» имеет множество научных параллелей. Хотя игра состоит всего из двух простых правил, тем не менее она более сорока лет привлекает внимание учёных. Игра «Жизнь» и её модификации повлияли (в ряде случаев взаимно) на многие разделы таких точных наук, как математика, информатика, физика. Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии, вязкости и теплопроводности в физике твёрдого тела. Поведение «жизненных» ячеек (рождение новых и взаимное уничтожение) во многом напоминают процессы, происходящие при столкновении элементарных частиц. Возможно, эта игра связана и с другими научными явлениями, в том числе и с теми, о которых современной науке пока неизвестно. Также возможно, что не открытые на сегодня законы Природы и Общества станут более понятными благодаря «Жизни» и её модификациям.
Литература https: //ru.wikipedia.org Мартин Гарднер «Математические досуги» https: //habrahabr.ru http: //beluch.ru/life/lifelex/lexr.htm Тоффоли Т., Марголус Н. Машины клеточных автоматов Журнал «Наука и Жизнь» Для создания изображений использовалась программная реализация «The game of life», созданная Романом Парпалаком Игра «Жизнь»
В данном реферате рассматривается краткая история создания данной игры, правила игры, некоторые получаемые в результате фигуры, а также возможные модификации и влияние игры «Жизнь» на развитие различных научных дисциплин.
Работу выполнила студентка 3 курса СПбПУ Воденкова Ксения, гр.33415/1
Содержание реферата
1. История создания игры 2. Классические правила игры «Жизнь» 3. Основные фигуры: 4. Устойчивые конфигурации 5. Осцилляторы 6. Планер и космические корабли 7. Планерные ружья и пожиратели 8. Сады Эдема 9. Модификации игры «Жизнь» 10. Заключение 11. Литература
История создания игры «Жизнь»
Что наша «Жизнь»? Игра!
На протяжении многих лет великие классики сравнивали человеческую жизнь с некой игрой, в которой всё подчинено жестким правилам, и победителю достаётся всё, а проигравший остаётся не с чем. В 20 веке многие учёные обратили внимание концепцию игры и предложили описывать природные явления с помощью математической игры с определенными правилами. Так возникли клеточные автоматы.
Клеточный автомат – это дискретная модель, включающая регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может иметь любую размерность. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.
Впервые клеточные автоматы были придуманы Станиславом Уламом и Джоном фон Нейманом в 1940-е годы. Станислав Уам изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана был двухмерный, а самовоспроизводящийся робот описан алгоритмически. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.
Клеточный автомат фон Неймана В данной конфигурации двоичный сигнал циркулирует вдоль петли из синих ячеек, происходит переход между обычным и возбужденным состоянием передающих ячеек. Коммутирующая ячейка дублирует сигнал в красную линию. Сигнал проходит по линии и создает новую ячейку. Двоичный сигнал 1011 кодирует восточно-ориентированное передающее состояние, таким образом продолжая линию вправо.
Примерно в это же время Норберт Винер и Артуро Розенблют разработали клеточно-автоматную модель возбудимой среды, описывающую распространение импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.
В 1970 году Джоном Конвеем был изобретён клеточный автомат, получивший название игры «Жизнь».
Джон Конвей родился в 1937 году и в настоящее время работает профессором математики в Принстонском университете. В его научные интересы входит теория конечных групп, теория чисел, теория узлов, комбинаторная теория игр и теория кодирования. Но известность Конвей получил именно как создатель игры «Жизнь», и благодаря популяризации этой игры Мартином Гарднером. Игра была придумана на обычном листке бумаге, расчерченным на клетки, ещё до того, как стали появляться первые персональные компьютеры. Первым любителям этой мыслительной забавы требовалось много времени и аккуратности, чтобы не ошибиться, но с появлением возможности реализовать игру на компьютере, началось активное исследование конфигураций и математических законов, заложенных в «Жизнь».
Портрет Джона Конвея
Классические правила игры «Жизнь»
Действие данной математической игры происходит на бесконечном поле, состоящем из квадратных клеток. Каждая клетка может быть только в одном из двух состояний: 1 и 0 (живая и мёртвая клетка соответственно). Конвей тщательно подбирал правила игры, и долго проверял их «на практике», добиваясь, чтобы они по возможности удовлетворяли трём условиям:
Короче говоря, правила должны быть такими, чтобы поведение популяции было непредсказуемым. Пример сложной эволюции конфигурации с простыми начальными данными:
В итоге были придуманы следующие очень простые правила: Каждая клетка имеет ровно восемь соседей, с которым соприкасается хотя бы в одной точке. |
Последнее изменение этой страницы: 2019-05-06; Просмотров: 168; Нарушение авторского права страницы
Первые три конфигурации на втором ходу погибают. Относительно третьей конфигурации следует сказать, что любой диагональный ряд клеток, каким бы длинным он ни был, с каждым ходом теряет стоящие на его концах клетки и, в конце концов, совсем исчезает. Конвей вводит понятие скорости света – это скорость, при которой конфигурация перемещается в одну какую-либо сторону на одну клетку за одну итерацию. По аналогии с СТО скорость света – это максимальная достижимая скорость передвижений в игре «Жизнь». Пользуясь этой терминологией, можно сказать, что диагональный ряд фишек распадается с концов со скоростью света.
Рассмотрим эволюцию пяти тетрамино: 
Данные устойчивые конфигурации, иначе называемые натюрмортами, являются одними из самых простых представителей своего класса. Натюрморт является осциллятором периода 1. По сути, живой конфигурация может считаться только пока она эволюционирует, как только форма становится устойчивой или превращается в осциллятор, можно сказать, что она закончила своё существование, как живая система. Так, неживая природа может претерпевать периодические изменения, те не менее оставаясь неживой. В качестве примера можно привести смену дня и ночи на нашей планете.
Восьмёрка — это периодически восстанавливающая себя конфигурация, открытие которой принадлежит Нортону. Она не только по форме напоминает восьмёрку, но и имеет период, равный восьми.
Конвей также показал, что скорость любой конечной фигуры, перемещающейся по вертикали или по горизонтали на свободные клетки, не может превышать половину скорости света. Конвею известны и другие движущиеся конфигурации, кроме планера, которые он называет космическими кораблями. На рисунке показаны три космических корабля. Все они передвигаются горизонтально слева направо со скоростью, равной половине скорости света. В полёте из них вылетают «искры», которые тут же гаснут при дальнейшем движении кораблей.
Одиночные космические корабли без эскорта не могут занимать в длину больше шести клеток, в противном случае на доске начинают появляться различные мелкие фигуры, препятствующие движению корабля. Конвей обнаружил, что более длинным кораблям (которые он назвал сверхтяжёлыми) необходим эскорт из двух или большего числа кораблей меньших размеров. Корабли эскорта не дают возникать препятствиям на пути сверхтяжёлого корабля. На рисунке изображён самый большой космический корабль, для которого достаточно двух эскортирующих кораблей меньшего размера. Для более длинных кораблей необходима целая флотилия эскортирующих кораблей. Конвей вычислил, что корабль длиной в сто клеток требует эскорта, состоящего из тридцати двух кораблей.
Простейшим и очень эффективным пожирателем является блок. Он в состоянии поглотить улей, каравай, лодку.
Сам по себе Гершел - неустойчивая конфигурация, которая пытается двигаться, испускает глайдер, но затем расплывается в стороны, испускает еще один глайдер и умирает. В реакции Гершел движется прямо на группу из четырех блоков, один из которых ему удается поглотить. Но остальные так расположены, что им удается своими укусами не только отогнать " хищника", но и вернуть на место первый блок. В 64 поколении Гершел принимает свой первоначальный вид, но оказывается повернутым на 90 градусов.
Самый известный пожиратель - это рыболовный крючок. Он называется также Пожиратель-1. Это наименьший натюрморт, не обладающий никакой симметрией. Его фантастическая устойчивость, способность к самовосстановлению при взаимодействии с другими объектами, были по достоинству оценены. Сейчас рыболовный крючок является компонентом тысяч конструкций. Существуют реакции, в которых он пожирает мигалку, предулей, предпасеку и пи-гептамино.
В терминологии игры «Жизнь» образец, в котором все «включенные» ячейки, становятся выключенными при каждом следующем ходе, называется фениксом. Все паттерны в «Семенах» имеют такую форму. Несмотря на то, что все живые клетки постоянно умирают, небольшое требование о рождении в виде наличия двух клеток означает, что почти каждая картина «Семян» взрывается в хаотический беспорядок, который растет, чтобы охватить всю вселенную.
Клеточный автомат, похожий на «Жизнь» Конвея. В этом клеточном автомате начальный паттерн растет согласно тем же правилам, что и в «Жизни» Конвея; однако, в отличие от Жизни, уже живые клетки не умирают, а сохраняются во времени. Этот клеточный автомат был первоначально рассмотрен Тоффоли и Марголом (1987), которые назвали его «Инкспот». «Жизнь без Смерти» обычно включает в себя картины натюрморта, в которых не происходит никаких изменений, и шаблоны лестниц, которые растут по прямой.
Клеточный автомат, который формирует крупные алмазы с хаотично колеблющимися границами. Впервые изучил Дин Хикерсон, который в 1993 году предложил приз в размере 50 долларов за нахождение образца, который заполняет всё пространство живыми клетками. Приз был выигран в 1999 году Дэвидом Беллом.
Клеточный автомат, подобный «Жизни». Был разработан в 1994 году Натаном Томпсоном. Это двумерный клеточный автомат с двумя состояниями, описывается следующим правилом: клетка рождается, если она имеет 3 или 6 соседей и выживает, если у нее есть 2 или 3 соседа. Основная причина интереса к HighLife заключается в существовании шаблона, называемого репликатором. После запуска репликатора после двенадцати шагов получим результат - два репликатора.
Клеточный автомат из семьи «Жизни». Определяется следующим правилом: мертвая ячейка становится живой (рождается), если она имеет 3, 6, 7 или 8 живых соседей, а живая клетка остается живой (выживает), если она имеет 3, 4, 6, 7 или 8. Он был изобретен Натаном Томпсоном в 1997 году. Название «День и ночь» было дано из-за того, что его состояния включения и выключения симметричны: если все ячейки во Вселенной инвертированы, будущие состояния являются инверсиями будущих состояний исходного шаблона.