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

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

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

История

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

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

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

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

Колонии

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

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

Генетический код петель хранится в виде серии пар состояний ненулевой-нулевой. Геном стандартной петли показан на рисунке вверху и может быть представлен как серия пронумерованных состояний, начиная с Т-образного соединения и идущих по часовой стрелке: 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
Byl's loop ^{[ 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. Архивировано из оригинала (отсканированная книга онлайн) 5 января 2008 г. Проверено 29 февраля 2008 г.
^ Кодд, Эдгар Ф. (1968). Клеточные автоматы . Академик Пресс, Нью-Йорк.
^ К. Г. Лэнгтон (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Физика Д. 10 (1–2): 135–144. Бибкод : 1984PhyD...10..135L . дои : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .
^ Дж. Был (1989). «Самовоспроизведение в малых клеточных автоматах». Физика Д. 34 (1–2): 295–299. Бибкод : 1989PhyD...34..295B . дои : 10.1016/0167-2789(89)90242-X .
^ Дж. А. Реджиа; СЛ Арментроут; Х.-Х. Чжоу; Ю. Пэн (1993). «Простые системы, демонстрирующие самонаправленную репликацию». Наука . 259 (5099): 1282–1287. Бибкод : 1993Sci...259.1282R . дои : 10.1126/science.259.5099.1282 . ПМИД 17732248 . S2CID 36866419 .
^ Г. Темпести (1995). «Новый самовоспроизводящийся клеточный автомат, способный к конструированию и вычислениям». Достижения в области искусственной жизни, учеб. 3-я Европейская конференция по искусственной жизни . Гранада, Испания: Конспекты лекций по искусственному интеллекту, 929, Springer Verlag, Берлин. стр. 555–563. CiteSeerX 10.1.1.48.7578 .
^ Ж.-Ю. Перье; М. Сиппер; Дж. Занд (1996). «На пути к жизнеспособному, самовоспроизводящемуся универсальному компьютеру». Физика Д. 97 (4): 335–352. Бибкод : 1996PhyD...97..335P . CiteSeerX 10.1.1.21.3200 . дои : 10.1016/0167-2789(96)00091-7 .
^ Саяма, Хироки (1998). «Введение структурного растворения в самовоспроизводящуюся петлю Лэнгтона» . Искусственная жизнь VI: Материалы шестой Международной конференции по искусственной жизни . Лос-Анджелес, Калифорния: MIT Press. стр. 114–122.
^ Саяма, Хироки (1999). «На пути к реализации развивающейся экосистемы клеточных автоматов». Материалы Четвертого Международного симпозиума по искусственной жизни и робототехнике (AROB 4 '99) . Беппу, Оита, Япония. стр. 254–257. CiteSeerX 10.1.1.40.391 .
^ Крис Зальцберг; Хироки Саяма (2004). «Сложная генетическая эволюция искусственных саморепликаторов в клеточных автоматах» . Сложность . 10 (2): 33–39. Бибкод : 2004Cmplx..10b..33S . дои : 10.1002/cplx.20060 . Архивировано из оригинала 5 января 2013 г.
^ Николас Орос; К. Л. Неханив (2007). «Sexyloop: самовоспроизведение, эволюция и секс в клеточных автоматах». Первый симпозиум IEEE по искусственной жизни (1–5 апреля 2007 г., Гавайи, США) . стр. 130–138. hdl : 2299/6711 .

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

Видео Криса Лэнгтона, демонстрирующего самовоспроизводящиеся циклы.
визуальное представление нескольких самовоспроизводящихся циклов в Java-апплете
В репозитории таблиц правил имеются таблицы переходов для многих центров сертификации, упомянутых выше.
Golly — поддерживает Langton’s Loops , Game of Life и другие наборы правил.

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

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

[Langton1984-3] К. Г. Лэнгтон (1984). «Самовоспроизведение в клеточных автоматах» (PDF) . Физика Д. 10 (1–2): 135–144. Бибкод : 1984PhyD...10..135L . дои : 10.1016/0167-2789(84)90256-2 . hdl : 2027.42/24968 .

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

[Reggia1993-5] Дж. А. Реджиа; СЛ Арментроут; Х.-Х. Чжоу; Ю. Пэн (1993). «Простые системы, демонстрирующие самонаправленную репликацию». Наука . 259 (5099): 1282–1287. Бибкод : 1993Sci...259.1282R . дои : 10.1126/science.259.5099.1282 . ПМИД 17732248 . S2CID 36866419 .

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

[Perrier1996-7] Ж.-Ю. Перье; М. Сиппер; Дж. Занд (1996). «На пути к жизнеспособному, самовоспроизводящемуся универсальному компьютеру». Физика Д. 97 (4): 335–352. Бибкод : 1996PhyD...97..335P . CiteSeerX 10.1.1.21.3200 . дои : 10.1016/0167-2789(96)00091-7 .

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

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

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

[Oros2007-11] Николас Орос; К. Л. Неханив (2007). «Sexyloop: самовоспроизведение, эволюция и секс в клеточных автоматах». Первый симпозиум IEEE по искусственной жизни (1–5 апреля 2007 г., Гавайи, США) . стр. 130–138. hdl : 2299/6711 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]