Петли Лэнгтона — это особый «вид» искусственной жизни в клеточном автомате, созданный в 1984 году Кристофером Лэнгтоном . Они состоят из петли клеток, содержащей генетическую информацию, которая непрерывно течет по петле и выходит наружу по «руке» (или ложноножке ), которая станет дочерней петлей. «Гены» инструктируют его сделать три поворота влево, завершая петлю, которая затем отключается от родителя.
В 1952 году Джон фон Нейман создал первый клеточный автомат (КА) с целью создания самовоспроизводящейся машины . [1] Этот автомат обязательно был очень сложным из-за своей универсальности вычислений и конструкции. В 1968 году Эдгар Ф. Кодд сократил количество штатов с 29 в СА фон Неймана до 8 в его . [2] Когда Кристофер Лэнгтон отменил условие универсальности, он смог значительно снизить сложность автомата. Его самовоспроизводящиеся контуры основаны на одном из простейших элементов автомата Кодда — периодическом излучателе.
Петли Лэнгтона выполняются в СА, имеющем 8 состояний и использующем окрестность фон Неймана с вращательной симметрией. Таблицу переходов можно найти здесь: [1].
Как и СА Кодда , петли Лэнгтона состоят из проводов в оболочке. Сигналы пассивно распространяются по проводам, пока не достигнут открытых концов, когда команда, которую они несут, будет выполнена.
Из-за особого свойства «псевдоподий» петель они не могут воспроизводиться в пространстве, занимаемом другой петлей. Таким образом, как только петля окружена, она становится неспособной к размножению, в результате чего образуется кораллоподобная колония с тонким слоем воспроизводящихся организмов, окружающих ядро неактивных «мертвых» организмов. Если не предоставить неограниченное пространство, размер колонии будет ограничен. Максимальная популяция будет асимптотической к , где A – общая площадь пространства в ячейках.
Генетический код петель хранится в виде серии пар состояний, отличных от нуля-нуля. Геном стандартной петли показан на рисунке вверху и может быть представлен как серия пронумерованных состояний, начиная с Т-образного соединения и идущих по часовой стрелке: 70-70-70-70-70-70-40-40. Команда «70» продвигает конец провода на одну ячейку, а последовательность «40-40» вызывает поворот влево. Состояние 3 используется как временный маркер для нескольких этапов.
Хотя роли состояний 0,1,2,3,4 и 7 аналогичны СА Кодда, остальные состояния 5 и 6 используются вместо этого для опосредования процесса репликации цикла. После завершения цикла состояние 5 перемещается против часовой стрелки вдоль оболочки родительского цикла к следующему углу, вызывая создание следующего плеча в другом направлении. Состояние 6 временно присоединяется к геному дочерней петли и инициализирует растущую руку в следующем углу, которого она достигает.
Геном используется в общей сложности шесть раз: один раз для расширения ложноножки в нужное место, четыре раза для завершения цикла и еще раз для переноса генома в дочернюю петлю. Очевидно, что это зависит от четырехкратной вращательной симметрии петли; без него цикл был бы неспособен содержать информацию, необходимую для его описания. Такое же использование симметрии для сжатия генома используется во многих биологических вирусах , таких как икосаэдрический аденовирус .
