петли Лэнгтона

Самовоспроизводящиеся модели клеточных автоматов

Петля Лэнгтона в начальной конфигурации.

Петли Лэнгтона — это особый «вид» искусственной жизни в клеточном автомате, созданный в 1984 году Кристофером Лэнгтоном . Они состоят из петли клеток, содержащих генетическую информацию, которая непрерывно течет вокруг петли и вдоль «руки» (или псевдопода ), которая станет дочерней петлей. «Гены» предписывают ей сделать три левых поворота, завершая петлю, которая затем отсоединяется от своей родительской.

История

В 1952 году Джон фон Нейман создал первый клеточный автомат (КА) с целью создания самовоспроизводящейся машины . ^[1] Этот автомат был по необходимости очень сложным из-за своей универсальности вычислений и построения. В 1968 году Эдгар Ф. Кодд сократил количество состояний с 29 в КА фон Неймана до 8 в своем . ^[2] Когда Кристофер Лэнгтон избавился от условия универсальности, он смог значительно снизить сложность автомата. Его самовоспроизводящиеся циклы основаны на одном из простейших элементов автомата Кодда — периодическом излучателе.

Спецификация

Циклы Лэнгтона работают в КА, имеющем 8 состояний, и используют окрестности фон Неймана с вращательной симметрией. Таблицу переходов можно найти здесь: [1].

Как и в случае с CA Кодда , петли Лэнгтона состоят из проводов в оболочке. Сигналы пассивно перемещаются по проводам, пока не достигнут открытых концов, когда выполняется команда, которую они несут.

Колонии

Из-за особого свойства "псевдоподий" петель они не способны размножаться в пространстве, занимаемом другой петлей. Таким образом, как только петля окружена, она неспособна размножаться, что приводит к образованию колонии, похожей на коралл , с тонким слоем размножающихся организмов, окружающих ядро неактивных "мертвых" организмов. Максимальная популяция будет асимптотической к , где A - общая площадь пространства в ячейках. $\textstyle \left\lfloor {\frac {A}{121}}\right\rfloor$

Кодирование генома

Генетический код петель хранится в виде ряда пар состояний ненулевой-нулевой. Геном стандартной петли показан на рисунке вверху и может быть представлен как ряд пронумерованных состояний, начинающихся с Т-образного перекрестка и идущих по часовой стрелке: 70-70-70-70-70-70-40-40. Команда «70» продвигает конец провода на одну ячейку, а последовательность «40-40» вызывает поворот налево. Состояние 3 используется как временный маркер для нескольких этапов.

В то время как роли состояний 0, 1, 2, 3, 4 и 7 аналогичны КА Кодда, оставшиеся состояния 5 и 6 используются вместо этого для опосредования процесса репликации цикла. После завершения цикла состояние 5 перемещается против часовой стрелки вдоль оболочки родительской петли к следующему углу, заставляя следующую руку производиться в другом направлении. Состояние 6 временно присоединяется к геному дочерней петли и инициализирует растущую руку в следующем углу, которого она достигает.

Геном используется в общей сложности шесть раз: один раз для расширения псевдопода до нужного места, четыре раза для завершения петли и еще раз для переноса генома в дочернюю петлю. Очевидно, что это зависит от четырехкратной вращательной симметрии петли; без нее петля была бы неспособна содержать информацию, необходимую для ее описания. Такое же использование симметрии для сжатия генома используется во многих биологических вирусах , таких как икосаэдрический аденовирус .

Сравнение связанных циклов CA

КА	описание	количество штатов	район	количество ячеек (типичное)	период репликации (типичный)
Петли Лэнгтона ^[3] (1984)	Оригинальный самовоспроизводящийся цикл.	8	фон Нейман	86	151
Петля Быля^[4] (1989)	Удалив внутреннюю оболочку, Бил уменьшил размер петли.	6	фон Нейман	12	25
Петля Чжоу-Реджиа ^[5] (1993)	Дальнейшее уменьшение петли путем удаления всех оболочек.	8	фон Нейман	5	15
Петля Темпести ^[6] (1995)	Темпести добавил к своему циклу возможности конструирования, позволяющие записывать узоры внутри цикла после воспроизведения.	10	Мур	148	304
Петля Перье ^[7] (1996)	Перье добавил программный стек и расширяемую ленту данных к циклу Лэнгтона, что позволило ему вычислять все, что можно вычислить .	64	фон Нейман	158	235
Цикл SDSR ^[8] (1998)	С добавлением дополнительного состояния растворения структуры к петлям Лэнгтона цикл SDSR имеет ограниченный срок службы и растворяется в конце своего жизненного цикла. Это обеспечивает непрерывный рост и смену поколений.	9	фон Нейман	86	151
Эволупс ^[9] (1999)	Расширение петли SDSR, Evoloop способно взаимодействовать с соседними петлями, а также к эволюции . Часто наибольшее давление отбора в колонии Evoloops — это конкуренция за пространство, и естественный отбор благоприятствует наименьшей функциональной петле. Дальнейшие исследования продемонстрировали большую сложность, чем первоначально предполагалось в системе Evoloop. ^[10]	9	фон Нейман	149	363
Сексуальный цикл ^[11] (2007)	Sexyloop — это модификация Evoloop, в которой самовоспроизводящиеся петли обладают способностью к сексу . Благодаря этой способности петли способны передавать генетический материал в другие петли. Это увеличивает разнообразие в эволюции новых видов петель.	10	фон Нейман	149	363

Смотрите также

Искусственная жизнь – Область исследования
Клеточный автомат – Дискретная модель, изучаемая в информатике.
Кристофер Лэнгтон — американский учёный-компьютерщик
Клеточный автомат Кодда – двумерный клеточный автомат, разработанный Эдгаром Ф. Коддом в 1968 году.
Игра Конвея «Жизнь» – Двумерный клеточный автомат
Муравей Лэнгтона – Двумерная машина Тьюринга с эмерджентным поведением
Клеточный автомат фон Неймана – Клеточный автомат, используемый для моделирования универсальной конструкции

Ссылки

^ фон Нейман, Джон; Беркс, Артур В. (1966). "Теория самовоспроизводящихся автоматов". www.walenz.org. Архивировано из оригинала (Отсканированная книга онлайн) 2008-01-05 . Получено 2008-02-29 .
^ Кодд, Эдгар Ф. (1968). Клеточные автоматы . Academic Press, Нью-Йорк.
^ CG Langton (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Physica D . 10 ( 1– 2): 135– 144. Bibcode :1984PhyD...10..135L. doi :10.1016/0167-2789(84)90256-2. hdl : 2027.42/24968 .
^ J. Byl (1989). «Самовоспроизведение в малых клеточных автоматах». Physica D. 34 ( 1– 2 ): 295– 299. Bibcode :1989PhyD...34..295B. doi :10.1016/0167-2789(89)90242-X.
^ JA Reggia; SL Armentrout; H.-H. Chou; Y. Peng (1993). «Простые системы, демонстрирующие самонаправленную репликацию». Science . 259 (5099): 1282– 1287. Bibcode :1993Sci...259.1282R. doi :10.1126/science.259.5099.1282. PMID 17732248. S2CID 36866419.
^ G. Tempesti (1995). «Новый самовоспроизводящийся клеточный автомат, способный к построению и вычислениям». Достижения в области искусственной жизни, Proc. 3-я Европейская конференция по искусственной жизни . Гранада, Испания: Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Берлин. стр. 555–563 . CiteSeerX 10.1.1.48.7578 .
^ J.-Y. Perrier; M. Sipper; J. Zahnd (1996). «К жизнеспособному, самовоспроизводящемуся универсальному компьютеру». Physica D. 97 ( 4): 335– 352. Bibcode :1996PhyD...97..335P. CiteSeerX 10.1.1.21.3200 . doi :10.1016/0167-2789(96)00091-7.
^ Саяма, Хироки (1998). «Введение структурного распада в самовоспроизводящийся цикл Лэнгтона». Искусственная жизнь VI: Труды Шестой международной конференции по искусственной жизни . Лос-Анджелес, Калифорния: MIT Press. стр. 114–122 .
^ Саяма, Хироки (1999). «К реализации эволюционирующей экосистемы на клеточных автоматах». Труды Четвертого международного симпозиума по искусственной жизни и робототехнике (AROB 4th '99) . Беппу, Оита, Япония. стр. 254–257 . CiteSeerX 10.1.1.40.391 .
^ Крис Зальцберг; Хироки Саяма (2004). «Сложная генетическая эволюция искусственных саморепликаторов в клеточных автоматах». Complexity . 10 (2): 33– 39. Bibcode : 2004Cmplx..10b..33S. doi : 10.1002/cplx.20060. Архивировано из оригинала 2013-01-05.
^ Николас Орос; CL Неханив (2007). «Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata». Первый симпозиум IEEE по искусственной жизни (1–5 апреля 2007 г., Гавайи, США) . стр. 130–138 . hdl :2299/6711.

Внешние ссылки

Видео Криса Лэнгтона, демонстрирующего самовоспроизводящиеся петли.
визуальное представление нескольких самовоспроизводящихся циклов в Java-апплете
В репозитории таблиц правил имеются таблицы переходов для многих из упомянутых выше ЦС.
Golly - поддерживает циклы Лэнгтона, а также игру «Жизнь» и другие наборы правил.

[TSRA-1] фон Нейман, Джон; Беркс, Артур В. (1966). "Теория самовоспроизводящихся автоматов". www.walenz.org. Архивировано из оригинала (Отсканированная книга онлайн) 2008-01-05 . Получено 2008-02-29 .

[Codd68-2] Кодд, Эдгар Ф. (1968). Клеточные автоматы . Academic Press, Нью-Йорк.

[Langton1984-3] CG Langton (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Physica D . 10 ( 1– 2): 135– 144. Bibcode :1984PhyD...10..135L. doi :10.1016/0167-2789(84)90256-2. hdl : 2027.42/24968 .

[Byl1989-4] J. Byl (1989). «Самовоспроизведение в малых клеточных автоматах». Physica D. 34 ( 1– 2 ): 295– 299. Bibcode :1989PhyD...34..295B. doi :10.1016/0167-2789(89)90242-X.

[Reggia1993-5] JA Reggia; SL Armentrout; H.-H. Chou; Y. Peng (1993). «Простые системы, демонстрирующие самонаправленную репликацию». Science . 259 (5099): 1282– 1287. Bibcode :1993Sci...259.1282R. doi :10.1126/science.259.5099.1282. PMID 17732248. S2CID 36866419.

[Tempesti1995-6] G. Tempesti (1995). «Новый самовоспроизводящийся клеточный автомат, способный к построению и вычислениям». Достижения в области искусственной жизни, Proc. 3-я Европейская конференция по искусственной жизни . Гранада, Испания: Lecture Notes in Artificial Intelligence, 929, Springer Verlag, Берлин. стр. 555–563 . CiteSeerX 10.1.1.48.7578 .

[Perrier1996-7] J.-Y. Perrier; M. Sipper; J. Zahnd (1996). «К жизнеспособному, самовоспроизводящемуся универсальному компьютеру». Physica D. 97 ( 4): 335– 352. Bibcode :1996PhyD...97..335P. CiteSeerX 10.1.1.21.3200 . doi :10.1016/0167-2789(96)00091-7.

[Sayama1998-8] Саяма, Хироки (1998). «Введение структурного распада в самовоспроизводящийся цикл Лэнгтона». Искусственная жизнь VI: Труды Шестой международной конференции по искусственной жизни . Лос-Анджелес, Калифорния: MIT Press. стр. 114–122 .

[Sayama1999-9] Саяма, Хироки (1999). «К реализации эволюционирующей экосистемы на клеточных автоматах». Труды Четвертого международного симпозиума по искусственной жизни и робототехнике (AROB 4th '99) . Беппу, Оита, Япония. стр. 254–257 . CiteSeerX 10.1.1.40.391 .

[Salzberg2004-10] Крис Зальцберг; Хироки Саяма (2004). «Сложная генетическая эволюция искусственных саморепликаторов в клеточных автоматах». Complexity . 10 (2): 33– 39. Bibcode : 2004Cmplx..10b..33S. doi : 10.1002/cplx.20060. Архивировано из оригинала 2013-01-05.

[Oros2007-11] Николас Орос; CL Неханив (2007). «Sexyloop: Self-Reproduction, Evolution and Sex in Cellular Automata». Первый симпозиум IEEE по искусственной жизни (1–5 апреля 2007 г., Гавайи, США) . стр. 130–138 . hdl :2299/6711.