Zoaron : другие произведения.

Логические элементы в клеточном автомате "Жизнь": Введение

Самиздат: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Обзоры] [Помощь|Техвопросы]
Ссылки:


 Ваша оценка:



Логические элементы в клеточном автомате "Жизнь"


Введение


  Клеточный автомат - есть некоторый (не обязательно реальный, чаще всего - виртуальный) механизм, меняющий своё состояние, переходящий из одного состояния в другое, в зависимости от заданных правил таких переходов. Правила, обычно, включают рассмотрение состояний ближайших соседних автоматов1, образующих в совокупности периодическую решётку - клеточное пространство.
  Клеточный автомат "Жизнь", получивший широкую известность под названием "Игра Жизнь", был создан Джоном Конвеем в 1970 году и популяризован в серии статей Мартина Гарднера2). На самом деле, это конечно не игра, по крайней мере - не только игра. Конвей ставил себе сложную и серьезную задачу: сделать наименьший клеточный автомат, с наиболее простыми правилами3, в котором, тем не менее, можно было бы строить самовоспроизводящиеся машины фон Неймана. Сам Нейман, доказал возможность создания такой машины для клеточного автомата, клетки которого могли бы принимать двадцать девять4 возможных состояний, взаимодействуя с четырьмя соседними (смежными с данной по вертикали и горизонтали, т. е. ортогонально) клетками. Репликатор фон Неймана, должен был бы состоять из примерно 200000 клеток. Автомат Конвея, на первый взгляд, выглядит побледнее. Хотя окрестность каждой клетки и была увеличена до восьми, но возможных состояний у каждой клетки всего лишь два. Тем не менее, в автомате Конвея так же может быть построен репликатор...
  Но, конечно, на репликатор, этот "Грааль" для жизнелюбов5 (как предложил называть исследователей клеточного автомата "Жизнь" Роберт Уэйнрайт), мы замахиваться не будем6, а попытаемся некоторые логические элементы, реализующие как простые операции: инверсию, конъюнкцию и дизъюнкцию, так и более сложные, которые могут быть осуществлены той или иной комбинацией простых элементов: эквивалентность, исключающее или, штрих Шеффера и стрелка Пирса7.
  И ещё одно замечание. Сложившаяся исторически терминология, используемая для обозначения различных конфигураций в "Жизни", представляется мне несколько неудовлетворительной. Названия, которые давались конфигурациям в ранних исследованиях, в том числе, и самого Конвея, нередко выбирались на основе внешнего сходства этих конфигураций с теми или реальными объектами (как, например каравай8, улей, пасека, пруд и т. п.). Никакой смысловой связи между поведением конфигурации и названием её здесь, зачастую, нет, а само название не столько проясняет суть дела, сколько запутывает начинающего исследователя.
  Уходя в "глубокий оффтоп", можно провести здесь параллель с названиями созвездий, как известно, ничего общего не имеющими с реальным расположением звёзд. Названия тем или иным конфигурациям, возникающим в процессе работы клеточного автомата, рискну предполагать, давались по почти таким же мотивам, что и названия созвездиям - получить хоть какую то опору. И если за второе мы до сих пор расплачиваемся отнюдь не влачащей сегодня жалкое существование астрологией и поделками горе-фантастов, отправляющих очередную экспедицию куда ни будь в "созвездие Волопаса", то за произвольность своей терминологии, "Жизнь" расплачивается, в том числе, статусом игры. С одной стороны, это обеспечивает "Жизни" постоянную популярность, однако с другой - эта популярность никуда не ведёт, впервые столкнувшись с этим клеточным автоматом, вы рискуете увязнуть9 в пестрой, но пустой терминологии, в дальнейшем считая "Жизнь" лишь родом головоломки или калейдоскопа; занимательным, но совершенно не серьёзным время провождением.
  Поэтому, в дальнейшем, я буду использовать не традиционные названия для конфигураций, а термины из электроники, наиболее точно, насколько это будет возможным, отражающие смысл.

(продолжение следует)




  1. Здесь имеется небольшая тонкость. Дело в том, что клеточным автоматом, в единственном числе, называют не только некий конкретный экземпляр клеточного автомата, но также и всё множество автоматов, составляющих клеточное пространство. Здесь нет противоречия, но есть двусмысленность. Фактически - клеточное пространство представляет собой бесконечное или конечное множество автоматов и если бы мы захотели реализовать это пространство, так сказать, в металле, нам пришлось бы изготовить множество идентичных друг другу автоматов. Это с одно стороны. С другой стороны, алгоритмически - клеточный автомат один, то есть всё клеточное пространство, и все конфигурации которые возникают в клеточном пространстве, можно считать результатом работы одного клеточного автомата, последовательно применяемого к ячейкам клеточного пространства. [Назад]

  2. Интересно, что колонки типа "Занимательный компьютер", исчезли из журналов "Scientific American" и "Наука и жизнь", почти одновременно с широким распространением персональных компьютеров. [Назад]

  3. Правила следующие: "мёртвая" клетка, рядом с которой имеются три "живые" клетки, становится "живой"; "живая" клетка, сохраняет своё состояние, если вокруг неё имеются две или три "живые" клетки. [Назад]

  4. Оригинальное доказательство фон Неймана, впоследствии было значительно упрощено, в частности, Э. Р. Бэнксу удалось доказать возможность существования репликатора на автомате лишь с четырьмя возможными состояниями. [Назад]

  5. На русском языке, слово "жизнелюб" в этом смысле было впервые использовано Владимиром Скляром. [Назад]

  6. Такой репликатор должен иметь чудовищные размеры но, на правах чистой спекуляции: а не может ли существовать значительно более компактный репликатор, работающий в клеточном пространстве периодически замощённом некими устойчивыми конфигурациями? Как знать... [Назад]

  7. Таблицы логических функций:

инверсия
x!x
01
10
-
конъюнкция
x1x2x1&x2
000
100
010
111
дизъюнкция
x1x2x1Vx2
000
101
011
111
исключающее или
x1x2x1^x2
000
101
011
110
эквивалентность
x1x2x1<=>x2
001
100
010
111
штрих Шеффера
x1x2x1|x2
001
101
011
110
стрелка Пирса
x1x2x1↓x2
001
100
010
110

[Назад]

  8. В оригинале - loaf, то есть - булка. [Назад]

  9. На первый взгляд, произвольные термины и неточные сравнения не являются чем то опасным, однако, не помню уже кто заметил, что, например, развитие объектно-ориентированного программирования в России серьёзно тормозится неточными примерами. В частности, многих наверное запутал распространённый пример, в котором некоторый класс объектов сравнивался со студенческой группой, а субкласс - со старостой этой группы. Что ж, может быть там, где права даются за ответственность и ответственность зачастую превышает права - это и легко воспринять. Но здесь, где увеличение прав подразумевает только прогрессирующее уменьшение ответственности, здесь всякий ставит даже старосту студенческой группы - над группой... [Назад]




  Zoaron
  2011 jan.


 Ваша оценка:

Связаться с программистом сайта.

Новые книги авторов СИ, вышедшие из печати:
О.Болдырева "Крадуш. Чужие души" М.Николаев "Вторжение на Землю"

Как попасть в этoт список
Сайт - "Художники" .. || .. Доска об'явлений "Книги"