Другое: Клеточные автоматы
Итак, мы располагаем планерами и различными кораблями. Возникает вопрос, что происходит, когда они сталкиваются между собой или с различными стационарными конфигурациями (стационарами). Столкновения могут быть очень разнообразны в зависимости от курса планера и его фазы при столкновении. Столкновение двух планеров или планера со стационаром может приводить к их «аннигиляции». В столкновении может рождаться целый набор семафоров и стационаров.
Обратим внимание на следующую закономерность. Если конфигурация все время локализована в квадрате размером NxN, то она является набором стационаров и циклов, период которых не превышает 2N. В самом деле, каждая клетка может находиться в одном из двух состояний, а всего клеток в области N2 , поэтому при t>2N конфигурации начнут повторяться.
Рассматривая непрерывные среды, можно говорить о
резонансном возбуждении - начальных данных, приводящих к более сложной эволюции
решений, чем в остальных случаях. В игре «Жизнь» есть аналог такого поведения.
Обратим внимание на конфигурацию, показанную на рисунке 5, называемую
«r-пентемино». Возникающие клетки занимают всё большую часть плоскости,
рождается несколько планеров, причем это сообщество будет развиваться далее. Ни
одна из других конфигураций, состоящих из пяти клеток, не приводит к такому
сложному поведению.
Как правило, эволюция взятых наугад конфигураций приводит к появлению наборов стационаров, семафоров, планеров. При этом общее число клеток при t, стремящемся к бесконечности, оказывается ограниченным (это было заложено в требованиях Конуэя), однако, при некоторых начальных данных эволюция системы может качественно меняться. Такое поведение характерно для ряда биологических систем, в частности, эволюционных процессов. Маловероятное событие может качественно изменить поведение системы, привести к появлению новых видов. Именно поэтому игра «Жизнь» находит применение в экологических моделях, при моделировании морфогенеза, в других биологических задачах.
Чем большую площадь занимает сообщество, тем
сложнее оно может себя вести. Поэтому большой интерес вызывают неограниченно
растущие в пространстве конфигурации. Одну из них, называемую «катапультой» или
«планерным ружьём», предложил в 1970 году Р. Госпер-младший. Видно, что
катапульта через каждые 30 шагов повторяет себя и выпускает планер (см. рисунок
6). Планерное ружьё заполняет пространство потоком планеров. Конуэй высказал
гипотезу, согласно которой не существует ни одной начальной конфигурации,
способной беспредельно расти. Иначе говоря, любая конфигурация, состоящая из
конечного числа живых клеток, не может перейти в конфигурацию, в которой число
живых клеток превосходило бы некий конечный предел. Но гипотеза оказалась
ошибочной! Опровержение - планерное ружьё.
Рис. 6. Планерное ружьё (катапульта) -
конфигурация, генеририрующая за каждые 30 ходов планер.
Есть ещё более сложные сообщества клеток, которые могут двигаться, оставляя за собой большой набор семафоров и стационаров. Одно из них - «паровоз» (он имеет довольно сложную структуру). Поиск таких конфигураций - довольно трудоёмкий процесс, требующий применения специальных алгоритмов и под силу квалифицированным специалистам.
Также были найдены особые конфигурации, которые Джон Тьюки назвал «садами Эдема». «Сады Эдема» не могут возникнуть в ходе работы клеточного автомата, поскольку их не способна породить никакая конфигурация. В силу этого они должны быть заданы с самого начала - в нулевом поколении. Не имея предшественников, они не могут быть самовоспроизводящимися. Алви Р. Смит нашел способ применить теорему Мура к игре Конуэя и показал, что конфигурация по типу «садов Эдема» возможна и в «Жизни». Формулы, выведенные Муром, позволили Смиту утверждать, что подобная конфигурация всегда может быть заключена в квадрат со стороною в 10 000 000 000 клеток.
Приведённые примеры показывают, что в обсуждаемой дискретной системе существует большое количество различных типов упорядоченности, которые определяют асимптотическое поведение некоторого множества конфигураций (в этом смысле они оказываются эквивалентны аттракторам динамических систем). Однако можно доказать большее - в игре «Жизнь» существуют сколь угодно сложные типы упорядоченности, эта дискретная система оказывается эквивалентна универсальной вычислительной машине.
ЭВМ можно рассматривать как конечный набор простейших логических элементов, осуществляющих операции И, ИЛИ, НЕ, определённым образом соединённых проводами, по которым распространяется набор импульсов, кодирующих последовательность нулей и единиц. В качестве генератора таких импульсов в игре «Жизнь» выступает планерное ружьё. Наличие планера в потоке естественно интерпретировать как единицу, отсутствие как ноль. Столкновение планеров, приводящих к их аннигиляции, позволяет построить элемент НЕ, направив два потока под прямым углом (если планер в определённом месте есть в первом потоке, то после столкновения планер в другом потоке на этом месте исчезнет). Более сложным образом конструируются другие элементы.
Для анализа ситуаций, возникающих в игре «Жизнь», применяется компьютер. В программе, моделирующей этот клеточный автомат, используется квадратная матрица, которая и является полем для игры. При смене хода анализируется каждый элемент старой матрицы и строится на её основе новая, которая соответствует конфигурации на следующем шаге эволюции. Для более детального исследования игра Конуэя расширена на несколько популяций, каждая из которых развивается по своим правилам. Правила для каждой популяции выбираются из следующих:
• Условия рождения и смерти. Задаются четыре параметра (параметры можно менять в процессе игры): минимальное и максимальное количество соседей своей популяции, при котором рождается клетка; минимальное и максимальное количество соседей, при котором клетка выживает и переходит в следующее поколение.
• Соседями клетки могут быть любые клетки, находящиеся в квадрате 3х3 с центром в данной клетке.
Игра «Жизнь» нашла свое применение в биологии
как игра «Аква-Тор», которая моделирует поведение системы, состоящей из двух
популяций, условно называемых «травоядные» и «хищники».
ПРАКТИЧЕСКАЯ
ЧАСТЬ
#include <iostream>
#include <ctime>namespace std;main()
{int iFieldWidth(20) , iFieldHeight(10);char chLiveCell('#') , chDeathCell('.');iGenerations(5);bCellArry[iFieldWidth * iFieldHeight] = {false};bTempCellArry[iFieldWidth * iFieldHeight] = {false};((unsigned)time(NULL));(int y=0; y < iFieldHeight; y++)
{(int x=0; x < iFieldWidth; x++)
{(bCellArry[x + y * iFieldWidth])
{<< chLiveCell;
}
{<< chDeathCell;
}
}<< '\n' ;}<< '\n' ;<< '\n' ;(int y=0; y < iFieldHeight; y++)
{(int x=0; x < iFieldWidth; x++)
{[x + y * iFieldWidth] = rand() % 2;(bCellArry[x + y * iFieldWidth])
{<< chLiveCell;
}
{<< chDeathCell; } }<< '\n' ;}<< '\n' ;<< '\n' ;(int g=0 ; g<iGenerations ; g++)
{(int y=0; y < iFieldHeight; y++)
{(int x=0, iCellCounter = 0; x < iFieldWidth; x++)
{( ((x-1) >=0 ) && ((y-1) >=0) )
{(bCellArry [(x-1)+(y-1)*iFieldWidth]) iCellCounter++ ;
}((y-1) >=0 )
{(bCellArry [x+(y-1)*iFieldWidth]) iCellCounter++ ;
}( ((x+1) <= iFieldWidth) && ((y-1) >=0 ))
{(bCellArry[ (x+1) + (y-1) * iFieldWidth]) iCellCounter++ ;
}((x-1) >=0 )
{(bCellArry[(x-1) + y*iFieldWidth]) iCellCounter++;
}((x+1) <= iFieldWidth-1 )
{(bCellArry[(x+1) + y*iFieldWidth] ) iCellCounter++;
}( ((x-1) >= 0 ) && ((y+1) <= iFieldHeight-1))
{(bCellArry[(x-1) + (y+1) * iFieldWidth]) iCellCounter++;
}((y+1) <= iFieldHeight-1)
{(bCellArry [x+(y+1) * iFieldWidth]) iCellCounter++;
}(((x+1) <= iFieldWidth -1) && ((y+1) <= iFieldHeight-1))
{(bCellArry [(x+1) + (y+1) * iFieldWidth]) iCellCounter++;
}((iCellCounter < 2 ) || (iCellCounter > 3 ))
{[x + y * iFieldWidth] = false;<< chDeathCell;
}
{((!bCellArry [x + y * iFieldWidth]) && (iCellCounter !=3))
{[x + y * iFieldWidth] = false;<< chDeathCell;
}
{[x + y * iFieldWidth] = true;<< chLiveCell;
}
}= 0;
}<< '/n' ;
}<< '/n' ;<< '/n' ;(int i=0 ; i < (iFieldWidth * iFieldHeight) ; i ++ )
{[i] = bTempCellArry[i];
}
}0; }
1) Задаем
начальное
состояние
) Вывод пяти поколений
ВЫВОД
Хотя игра состоит всего из трех
простых правил, тем не менее, она более сорока лет привлекает пристальное
внимание учёных. Игра «Жизнь» и ее модификации повлияла (в ряде случаев
взаимно) на многие разделы таких точных наук как математика, информатика,
физика. Кроме того, многие закономерности, обнаруженные в игре, имеют свои
аналогии в других, подчас совершенно «нематематических» дисциплинах. Возможно,
эта игра связана и с другими научными явлениями, в том числе и с теми, о
которых современной науке пока неизвестно. Также возможно, что не открытые на
сегодня законы Природы и Общества станут более понятными благодаря «Жизни» и ее
модификациям.
СПИСОК ЛИТЕРАТУРЫ
1. <http://habrahabr.ru/>
. <http://life.written.ru/>
. <http://crm.ics.org.ru/>
. <http://www.ict.edu.ru/>