436
правок
Изменения
Langton: description added
== Автомат Лэнгтона ==
Одним из направлений развития работы фон Неймана стали попытки конструирования более простых самовоспроизводящихся клеточных автоматов. Примером эволюции простого самовоспроизводящегося автомата {{---}} автомат Лэнгтона<ref name="mitin" />.<br> В статье<ref>Byl John. Self-reproduction in small cellular automata. Physica D, v. 34 (1989),p.295-299.</ref> приводятся самовоспроизводящиеся автоматы, которые еще проще автоматов Лэнгтона, показанных на '''изображениях выше'''. Оказалось, что можно сконструировать самовоспроизводящийся автомат всего лишь из 10 клеток, при этом каждая клетка автомата может находиться в одном из шести возможных состояний.<br> Также интерес представляет Муравей Лэнгтона<ref>Langton, Chris G. (1986). "Studying artificial life with cellular automata", 120–149</ref>, разработанный в 1986 году Крисом Лэнгтоном. Данный автомат является, по сути, двумерной машиной Тьюринга с 2 символами и 4 состояниями<ref>Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.</ref>.{{Определение|definition='''Автомат Лэнгтона''' {{---}} двумерный клеточный самовоспроизводящийся автомат, представляющий собой сигнальную ленту, заключенную между двумя стенками.<br>В автомате Лэнгтона клетка может находиться в одном из восьми возможных состояний. Состояние клетки в следующий момент времени определяется состоянием в текущий момент состоянием четырех соседей.}}Сигнальная лента несет информацию, необходимую для создания копии автомата.<br> Состояния автомата Лэнгтона:* $0,\;1,\;2$ {{---}} служебные состояния;* $3,\;4,\;5,\;6,\;7$ {{---}} сигнальные состояния. Из клеток в состоянии $2$ строятся «стенки» автомата.Состояние $1$ является «несущей частотой», или, скорее, «несущей лентой» сигнала.Вслед за сигнальным состоянием должно идти состояние $0$ {{---}} так задается направление распространения сигнала.Состояние $3$ используется в качестве промежуточного состояния при повороте, состояния $5$ и $6$ используются при отделении дочернего автомата и для инициализации новой итерации самовоспроизведения. === Принцип работы ===''' TODO: ADD PICTURES'''<br>Когда конца ленты достигает сигнал $70$, то длина ленты увеличивается на $1$. Когда в конец ленты приходят два сигнала $40$, то лента делает поворот налево. Копия исходного состояния получается через $151$ такт времени после запуска автомата.
= Тюрьмиты =
