четверг, 15 августа 2013 г.

Размножение. Игра жизнь

Наскальная живопись. Бизон. Скала, уголь, охра.
Неизвестный художник
Жизнь.  Уникальное явление природы. Можно ли создать жизнь искуственную? Всю человеческую историю люди создавали копии живых объектов - зверей, птиц, рыб, наконец людей. С развитием техники, а именно механики стали появляться огромные человекоподобные роботы механические куклы. Куклы двигались, говорили. Но у них не было одного из главнейших свойств живого - способности к размножению.
Долгое время самовоспроизводящиеся роботы были недостижимой мечтой человечества из-за низкого уровня развития науки и техники, однако с 1950 года начались первые теоретические исследования в этом направлении.

Математик Джон фон Нейман поставил перед собой задачу доказать принципиальную
Осваивать космос хотели послать армию
роботов
возможность существования самовоспроизводящихся автоматов. Фон Нейман в своих построениях использовал моделей машины, способной передвигаться по складу запасных частей, отбирать необходимые детали и собирать новые машины, как две капли воды похожие на неё. Если такую машину снабдить надлежащими инструкциями, она построит точную копию самой себя. В свою очередь две машины («мама» и «дочь») смогут построить ещё две; четыре машины построят четыре и т. д.
Тогда думали, что создав такие механизмы можно будет послать их на отдаленные астероиды, где они смогут добывать полезные ископаемые и готовиться к приезду человека, постоянно размножаясь. Эх, наивное было время!
Именно из этих размышлений впоследствии родилось впоследствии новое направление в науке -  клеточные автоматы.
Самый известный такой автомат - игра "Жизнь", разработанная математиком Джоном Конвеем в 1970 году. Сейчас существует множество вариантов программной реализации игры, один из которых приведено ниже

Правила игры не простые, а очень простые. Есть «вселенная» — некий квадрат, расчерченный как школьный лист на клетки. Каждая клетка на этой поверхности может находиться в двух состояниях: быть «живой» или быть «мёртвой» (пустой). Клетка имеет восемь соседей - четыре по краям, четыре по диагонали.
Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:
в пустой (мёртвой) клетке, рядом с которой ровно три живые клетки, зарождается жизнь;
если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).
Игра прекращается, если на поле не останется ни одной «живой» клетки, если при очередном шаге ни одна из клеток не меняет своего состояния, или если конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов.

Эта модель конечно очень далека от реального положения вещей - обычно колонии бактерий растут. Модель Конвея предполагает постояное уменьшение и "сжатие" колоний до некого минимального стационарного состояния. 
Об этой особенности своего клеточного автомата создатель превосходно знал, и предположил, что никакая начальная комбинация не может привести к неограниченному размножению даже выделив премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института, придумавшей неподвижную повторяющуюся фигуру, которая периодически выбрасывала "споры" в окружающее пространство.

Игра Конуэя «Жизнь» вызвала огромный интерес у ученых, занимающихся разработкой проблем, связанных с использованием компьютеров. Главное направление исследований - построение самовоспроизводящихся конфигураций во "вселенной" живущей по законам, похожим на законы вселенной игры жизнь. Интереснее всего заставить работать в этой вселенной машину Тьюринга-Поста которая является простейшей вычислительной машиной. Еще одна цель - подобрать такую конфигурацию клеточного пространства, которая сделает возможным клонирование машины. Фон Нейман доказал, что такое возможно при начальной конфигурации клеточного пространства, содержащего около 200 000 клеток.

Вообще же за годы исследования клеточных автоматов удалось создать простые и понятные правила "размножения" клеток, позволяющие "клонировать" начальную конфигурацию. 
Как и в игре "Жизнь" ячейки могут быть "живыми" или "мертвыми", и каждая из них, имеет четырёх соседей (сверху, снизу, слева, справа), а правила размножения сводятся к следующим. Каждая клетка, четное число (0, 2, 4, ...) живых соседей, к следующему ходу "умирает". Каждая клетка, имеющая нечетное число (1, 3, ...) соседей, становится живой. Через некоторое число ходов (которое зависит от выбора начальной конфигурации) любая конфигурация живых клеток в таком пространстве воспроизведет себя четыре раза: одна копия расположится справа, другая — слева, третья — сверху, четвёртая — снизу от того (уже пустого) места, где находилась начальная конфигурация. Число копий будет увеличиваться геометрической прогрессии 1, 4, 16, 64... На рисунке показаны полтора цикла размножения тримино в форме прямого угла.
Армия клонов от создателей клеточных автоматов

Множество автоматов такого рода, отличающихся друг от друга схемой примыкания соседних клеток, числом состояний и правилами перехода, исследовал С. Улам.
Еще один интересный клеточный автомат
Как и в игре Конуэя, клетки в игре Улама могут находиться в двух состояниях, но соседними считаются клетки, примыкающие к данной лишь по вертикали, но не по диагонали. Рождение фишки происходит на клетке, имеющей одного и только одного соседа, а все клетки поколения n погибают после рождения поколения n + 2. Иначе говоря, на любом этапе эволюции выживают лишь два последних поколения. На рисунке черными изображены новорожденные клетки (их 444). Зеленые клетки предыдущего поколения — их 404 — исчезнут на следующем ходу. Обратите внимание на характерную деталь, которую Улам назвал «обглоданной костью». Улам проводил эксперименты и с такими играми, в которых две конфигурация могли расти до тех пор, пока они не сталкивались. В следующей за столкновением «битве» одной стороне иногда удавалось одержать верх над другой, а иногда обе армии исчезали. Улам рассмотрел также игры на трёхмерных досках — кубических «паркетах», заполняющих всё пространство. Основные результаты Улама собраны в его статьях, опубликованных в сборнике «Очерки теории клеточных автоматов».
 На рисунке показано сорок пятое поколение организма, родившегося из одной-единственной фишки, стоявшей в центральной клетке.
Сам Смит работает над созданием клеточных автоматов, имитирующих машины для распознавания образов. Хотя сегодня такая проблема может показаться имеющей лишь чисто теоретический интерес, вполне возможно, что когда-нибудьвычислительным машинам и автоматам понадобится «сетчатая оболочка» для распознавания образов.

Комментариев нет:

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