Петли Лангтона - Википедия - Langtons loops

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

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

История

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

Технические характеристики

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

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

Колония петель. Те, что в центре, «мертвы».

Колонии

Из-за особого свойства «псевдоподий» петель они не могут воспроизводиться в пространстве, занятом другой петлей. Таким образом, если петля окружена, она не может воспроизводиться, что приводит к коралл -подобная колония с тонким слоем воспроизводящихся организмов, окружающая ядро ​​неактивных «мертвых» организмов. Если не будет предоставлено неограниченное пространство, размер колонии будет ограничен. Максимальное население будет асимптотический к , куда А - общая площадь помещения в ячейках.

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

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

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

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

Сравнение связанных петель CA

CAколичество состоянийрайонколичество ячеек (типовое)период репликации (типичный)миниатюра
Петли Лэнгтона[3] (1984): Оригинальная самовоспроизводящаяся петля.8фон Нейман86151
Langtons Loop.png
Петля Быля[4] (1989): Удалив внутреннюю оболочку, Бил уменьшил размер петли.6фон Нейман1225
Byl Loop.png
Петля Чоу-Реджа[5] (1993): Дальнейшее уменьшение петли за счет удаления всех ножен.8фон Нейман515
Петля Чжоу-Реджи.png
Петля Темпести[6] (1995): Темпести добавил к своему циклу конструктивные возможности, позволяя записывать шаблоны внутри цикла после воспроизведения.10Мур148304
Петля Темпести.png
Петля Перье[7] (1996): Perrier добавил программный стек и расширяемую ленту данных в цикл Лэнгтона, что позволило ему вычислить что угодно. вычислимый.64фон Нейман158235
Perrier Loop.png
Петля SDSR[8] (1998): С дополнительным состоянием растворения структуры, добавленным к петлям Лэнгтона, петля SDSR имеет ограниченный срок службы и растворяется в конце своего жизненного цикла. Это обеспечивает непрерывный рост и смену поколений.9фон Нейман86151
SDSR Loop.png
Evoloop[9] (1999): Расширение петли SDSR, Evoloop способно взаимодействовать с соседними петлями, а также эволюция. Часто самое сильное давление отбора в колонии Evoloops - это борьба за пространство, и естественный отбор отдает предпочтение наименьшей из имеющихся функциональных петель. Дальнейшие исследования продемонстрировали большую сложность, чем первоначально предполагалось, в системе Evoloop.[10]9фон Нейман149363
Evoloop крупным планом.png
Sexyloop[11] (2007): Sexyloop - это модификация Evoloop, в которой самовоспроизводящиеся петли имеют возможность секс. Благодаря этой способности петли способны переносить генетический материал в другие петли. Это увеличивает разнообразие в эволюции новых видов петель.10фон Нейман149363
SL thumb.png

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

Рекомендации

  1. ^ фон Нейман, Джон; Беркс, Артур В. (1966). "Теория самовоспроизводящихся автоматов.". www.walenz.org. Архивировано из оригинал (Отсканированная книга онлайн) на 2008-01-05. Получено 2008-02-29.
  2. ^ Кодд, Эдгар Ф. (1968). Клеточные автоматы. Academic Press, Нью-Йорк.
  3. ^ К. Дж. Лэнгтон (1984). «Самовоспроизведение в клеточных автоматах» (PDF). Physica D. 10 (1–2): 135–144. Дои:10.1016/0167-2789(84)90256-2. HDL:2027.42/24968.
  4. ^ Дж. Бил (1989). «Самовоспроизводство в малых клеточных автоматах». Physica D. 34 (1–2): 295–299. Дои:10.1016 / 0167-2789 (89) 90242-Х.
  5. ^ Дж. А. Реджиа; С. Л. Арментроут; Х.-Х. Чжоу; Ю. Пэн (1993). «Простые системы, демонстрирующие самонаправленную репликацию». Наука. 259 (5099): 1282–1287. Дои:10.1126 / science.259.5099.1282. PMID  17732248.
  6. ^ Г. Темпести (1995). «Новый самовоспроизводящийся клеточный автомат, способный создавать и вычислять». Успехи в искусственной жизни, Proc. 3-я Европейская конференция по искусственной жизни. Гранада, Испания: конспекты лекций по искусственному интеллекту, 929, Springer Verlag, Берлин. С. 555–563. CiteSeerX  10.1.1.48.7578.
  7. ^ Ж.-Й. Perrier; М. Сиппер; Дж. Занд (1996). «К жизнеспособному самовоспроизводящемуся универсальному компьютеру». Physica D. 97 (4): 335–352. CiteSeerX  10.1.1.21.3200. Дои:10.1016/0167-2789(96)00091-7.
  8. ^ Саяма, Хироки (1998). «Введение структурного растворения в самовоспроизводящуюся петлю Лэнгтона». Искусственная жизнь VI: Материалы Шестой Международной конференции по искусственной жизни. Лос-Анджелес, Калифорния: MIT Press. С. 114–122.
  9. ^ Саяма, Хироки (1999). «К реализации развивающейся экосистемы на клеточных автоматах». Материалы четвертого Международного симпозиума по искусственной жизни и робототехнике (AROB 4th '99). Беппу, Оита, Япония. С. 254–257. CiteSeerX  10.1.1.40.391.
  10. ^ Крис Зальцберг; Хироки Саяма (2004). «Сложная генетическая эволюция искусственных саморепликаторов в клеточных автоматах». Сложность. 10 (2): 33–39. Дои:10.1002 / cplx.20060. Архивировано из оригинал на 2013-01-05.
  11. ^ Николас Орос; К. Л. Неханив (2007). «Sexyloop: самовоспроизведение, эволюция и секс в клеточных автоматах». Первый симпозиум IEEE по искусственной жизни (1–5 апреля 2007 г., Гавайи, США). С. 130–138. HDL:2299/6711.

внешняя ссылка