Автомат фон Неймана
Клеточный автомат фон Неймана — клеточный автомат, разработанный фон Нейманом при содействии Станислава Улама для исследования возможности создания самовоспроизводящихся машин.
Клеточный автомат Нобили — разновидность клеточного автомата фон Неймана, дополненного возможностью пересечения сигналов и хранения информации группами передающих клеток. Последняя функция требует три дополнительных состояния, в силу чего автомат Нобили имеет 32 состояния, а не 28. Ещё одной разновидностью является клеточный автомат Хаттона (Hutton), допускающий репликацию кольцевых структур (см. Langton’s loops).
Содержание
Определение
Конфигурация
Клеточный автомат в общем виде представляет собой упорядоченное множество конечных автоматов, обменивающихся информацией с соседними автоматами. В клеточном автомате фон Неймана ячейки упорядочены в виде двухмерной прямоугольной решетки и взаимодействуют с четырьмя непосредственно прилегающими ячейками, образующими окрестность фон Неймана. Решетка считается имеющей бесконечный размер в обоих направлениях, а ячейки — идентичными в плане правил перехода. Изменение состояний всех ячеек происходит синхронно.
Состояния
Каждый конечный автомат в пространстве фон Неймана может принимать одно из 29 состояний:
- базовое состояние U
- транзитные (или чувствительные) состояния
- S
- S0
- S00
- S01
- S000
- S1
- S10
- S11
- конфлюентные состояния
- C00
- C10
- C01
- C11
- обычное передающее состояние
- T00 вправо
- T01 вверх
- T02 влево
- T03 вниз
- специальное передающее состояние
- T10 вправо
- T11 вверх
- T12 влево
- T13 вниз
Каждое из передающих состояний (8 состояний) также характеризуется возбужденностью/невозбужденностью (зеленые/синие стрелочки), что дает в итоге 16 передающих состояний. Возбужденное состояние переносит данные со скоростью 1 бит за такт. Конфлюентные состояния имеют задержку на один такт, и таким образом могут хранить 2 бита информации.
Правила перехода передающих состояний
Поток информации между ячейками определяется свойством направленности. Применяются следующие правила:
- Передающие состояния применяют оператор ИЛИ к входным сигналам, то есть ячейка в передающем состоянии (обычном или специальном) перейдет в возбужденное на такте t+1 если любой из входных сигналов является возбужденным на такте t
- Состояния передаются между передающими ячейками соответственно свойству направленности.
- Обычные и специальные передающие состояния являются «антагонистами»:
- Если ячейка А на такте t в обычном возбужденном передающем состоянии указывает на ячейку В в любом специальном передающем состоянии, то на такте t+1 ячейка В перейдет в базовое состояние U. Особое передающее состояние будет «уничтожено».
- Аналогичное событие произойдет, если ячейка в специальном передающем состоянии будет указывать на обычную передающую ячейку.
Правила перехода конфлюентных состояний
Следующие правила применяются к конфлюентным состояниям:
- Конфлюентные ячейки не передают данных между собой.
- Конфлюентные ячейки принимают входные сигналы от одной или нескольких обычных передающих ячеек и выдают их передающим ячейкам (обычным или специальным), которые не указывают на текущую ячейку.
- Данные не передаются в направлении, обратном направленности передающей ячейки.
- Данные, хранимые конфлюентной ячейкой, теряются, если у неё нет прилегающих передающих ячеек (не указывающих на неё).
- Конфлюентные ячейки служат мостами между обычными и специальными передающими ячейками.
- Конфлюентные ячейки применяют оператор И к входным сигналам.
- Конфлюентные ячейки задерживают сигнал на один такт дольше, чем обычные передающие ячейки.
Правила перехода транзитных состояний
В исходном состоянии большая часть клеточного пространства является «пустой», то есть заполненной ячейками в состоянии U. Получив входной сигнал от передающей ячейки, соседняя ячейка в состоянии U переходит в транзитное состояние, проходит ряд состояний и оказывается в одном из передающих или конфлюентных состояний. Это конечное состояние определяется последовательностью входных сигналов. То есть транзитные состояния могут рассматриваться как точки бифуркации на пути от базового состояния к передающим и конфлюентным. В следующих правилах последовательность входных сигналов указана в скобках двоичной строкой:
- ячейка в базовом состоянии U, получив сигнал, переходит в состояние S (1)
- ячейка в состоянии S, не получив сигнала, переходит в состояние S0 (10)
- ячейка в состоянии S0, не получив сигнала, переходит в S00 (100)
- ячейка S00, не получив сигнала, переходит в S000 (1000)
- ячейка S000, не получив сигнала, переходит в T00 (10000)
- ячейка S000, получив сигнал, переходит в T01 (10001)
- ячейка S00, получив сигнал, переходит в T02 (1001)
- ячейка S00, не получив сигнала, переходит в S000 (1000)
- ячейка S0, получив сигнал, переходит в S01 (101)
- ячейка S01, не получив сигнала, переходит в T03 (1010)
- ячейка S01, получив сигнал, переходит в T10 (1011)
- ячейка в состоянии S0, не получив сигнала, переходит в S00 (100)
- ячейка S, получив сигнал, переходит в S1 (11)
- ячейка S1, не получив сигнала, переходит в S10 (110)
- ячейка S10, не получив сигнала, переходит в T11 (1100)
- ячейка S10, получив сигнал, переходит в T12 (1101)
- ячейка S1, получив сигнал, переходит в S11 (111)
- ячейка S11, не получив сигнала, переходит в T13 (1110)
- ячейка S11, получив сигнал, переходит в C00 (1111)
- ячейка S1, не получив сигнала, переходит в S10 (110)
Разрушающие правила
- Входной сигнал от специальной передающей ячейки, полученный ячейкой в конфлюентном или обычном передающем состоянии, переводит эту ячейку в базовое.
- Входной сигнал от обычной передающей ячейки, полученный специальной передающей ячейкой, переводит эту ячейку в базовое.
См. также
Напишите отзыв о статье "Автомат фон Неймана"
Ссылки
- Дж. фон Нейман, Теория самовоспроизводящихся автоматов. М.: «Мир», 1971.
|
Отрывок, характеризующий Автомат фон Неймана
Потом он открыл глаза и сказал что то, чего долго никто не мог понять и, наконец, понял и передал один Тихон. Княжна Марья отыскивала смысл его слов в том настроении, в котором он говорил за минуту перед этим. То она думала, что он говорит о России, то о князе Андрее, то о ней, о внуке, то о своей смерти. И от этого она не могла угадать его слов.– Надень твое белое платье, я люблю его, – говорил он.
Поняв эти слова, княжна Марья зарыдала еще громче, и доктор, взяв ее под руку, вывел ее из комнаты на террасу, уговаривая ее успокоиться и заняться приготовлениями к отъезду. После того как княжна Марья вышла от князя, он опять заговорил о сыне, о войне, о государе, задергал сердито бровями, стал возвышать хриплый голос, и с ним сделался второй и последний удар.
Княжна Марья остановилась на террасе. День разгулялся, было солнечно и жарко. Она не могла ничего понимать, ни о чем думать и ничего чувствовать, кроме своей страстной любви к отцу, любви, которой, ей казалось, она не знала до этой минуты. Она выбежала в сад и, рыдая, побежала вниз к пруду по молодым, засаженным князем Андреем, липовым дорожкам.
– Да… я… я… я. Я желала его смерти. Да, я желала, чтобы скорее кончилось… Я хотела успокоиться… А что ж будет со мной? На что мне спокойствие, когда его не будет, – бормотала вслух княжна Марья, быстрыми шагами ходя по саду и руками давя грудь, из которой судорожно вырывались рыдания. Обойдя по саду круг, который привел ее опять к дому, она увидала идущих к ней навстречу m lle Bourienne (которая оставалась в Богучарове и не хотела оттуда уехать) и незнакомого мужчину. Это был предводитель уезда, сам приехавший к княжне с тем, чтобы представить ей всю необходимость скорого отъезда. Княжна Марья слушала и не понимала его; она ввела его в дом, предложила ему завтракать и села с ним. Потом, извинившись перед предводителем, она подошла к двери старого князя. Доктор с встревоженным лицом вышел к ней и сказал, что нельзя.
– Идите, княжна, идите, идите!
Княжна Марья пошла опять в сад и под горой у пруда, в том месте, где никто не мог видеть, села на траву. Она не знала, как долго она пробыла там. Чьи то бегущие женские шаги по дорожке заставили ее очнуться. Она поднялась и увидала, что Дуняша, ее горничная, очевидно, бежавшая за нею, вдруг, как бы испугавшись вида своей барышни, остановилась.
– Пожалуйте, княжна… князь… – сказала Дуняша сорвавшимся голосом.
– Сейчас, иду, иду, – поспешно заговорила княжна, не давая времени Дуняше договорить ей то, что она имела сказать, и, стараясь не видеть Дуняши, побежала к дому.
– Княжна, воля божья совершается, вы должны быть на все готовы, – сказал предводитель, встречая ее у входной двери.
– Оставьте меня. Это неправда! – злобно крикнула она на него. Доктор хотел остановить ее. Она оттолкнула его и подбежала к двери. «И к чему эти люди с испуганными лицами останавливают меня? Мне никого не нужно! И что они тут делают? – Она отворила дверь, и яркий дневной свет в этой прежде полутемной комнате ужаснул ее. В комнате были женщины и няня. Они все отстранились от кровати, давая ей дорогу. Он лежал все так же на кровати; но строгий вид его спокойного лица остановил княжну Марью на пороге комнаты.
«Нет, он не умер, это не может быть! – сказала себе княжна Марья, подошла к нему и, преодолевая ужас, охвативший ее, прижала к щеке его свои губы. Но она тотчас же отстранилась от него. Мгновенно вся сила нежности к нему, которую она чувствовала в себе, исчезла и заменилась чувством ужаса к тому, что было перед нею. «Нет, нет его больше! Его нет, а есть тут же, на том же месте, где был он, что то чуждое и враждебное, какая то страшная, ужасающая и отталкивающая тайна… – И, закрыв лицо руками, княжна Марья упала на руки доктора, поддержавшего ее.
В присутствии Тихона и доктора женщины обмыли то, что был он, повязали платком голову, чтобы не закостенел открытый рот, и связали другим платком расходившиеся ноги. Потом они одели в мундир с орденами и положили на стол маленькое ссохшееся тело. Бог знает, кто и когда позаботился об этом, но все сделалось как бы само собой. К ночи кругом гроба горели свечи, на гробу был покров, на полу был посыпан можжевельник, под мертвую ссохшуюся голову была положена печатная молитва, а в углу сидел дьячок, читая псалтырь.
Как лошади шарахаются, толпятся и фыркают над мертвой лошадью, так в гостиной вокруг гроба толпился народ чужой и свой – предводитель, и староста, и бабы, и все с остановившимися испуганными глазами, крестились и кланялись, и целовали холодную и закоченевшую руку старого князя.
Богучарово было всегда, до поселения в нем князя Андрея, заглазное именье, и мужики богучаровские имели совсем другой характер от лысогорских. Они отличались от них и говором, и одеждой, и нравами. Они назывались степными. Старый князь хвалил их за их сносливость в работе, когда они приезжали подсоблять уборке в Лысых Горах или копать пруды и канавы, но не любил их за их дикость.
Последнее пребывание в Богучарове князя Андрея, с его нововведениями – больницами, школами и облегчением оброка, – не смягчило их нравов, а, напротив, усилило в них те черты характера, которые старый князь называл дикостью. Между ними всегда ходили какие нибудь неясные толки, то о перечислении их всех в казаки, то о новой вере, в которую их обратят, то о царских листах каких то, то о присяге Павлу Петровичу в 1797 году (про которую говорили, что тогда еще воля выходила, да господа отняли), то об имеющем через семь лет воцариться Петре Феодоровиче, при котором все будет вольно и так будет просто, что ничего не будет. Слухи о войне в Бонапарте и его нашествии соединились для них с такими же неясными представлениями об антихристе, конце света и чистой воле.
В окрестности Богучарова были всё большие села, казенные и оброчные помещичьи. Живущих в этой местности помещиков было очень мало; очень мало было также дворовых и грамотных, и в жизни крестьян этой местности были заметнее и сильнее, чем в других, те таинственные струи народной русской жизни, причины и значение которых бывают необъяснимы для современников. Одно из таких явлений было проявившееся лет двадцать тому назад движение между крестьянами этой местности к переселению на какие то теплые реки. Сотни крестьян, в том числе и богучаровские, стали вдруг распродавать свой скот и уезжать с семействами куда то на юго восток. Как птицы летят куда то за моря, стремились эти люди с женами и детьми туда, на юго восток, где никто из них не был. Они поднимались караванами, поодиночке выкупались, бежали, и ехали, и шли туда, на теплые реки. Многие были наказаны, сосланы в Сибирь, многие с холода и голода умерли по дороге, многие вернулись сами, и движение затихло само собой так же, как оно и началось без очевидной причины. Но подводные струи не переставали течь в этом народе и собирались для какой то новой силы, имеющей проявиться так же странно, неожиданно и вместе с тем просто, естественно и сильно. Теперь, в 1812 м году, для человека, близко жившего с народом, заметно было, что эти подводные струи производили сильную работу и были близки к проявлению.