История возникновения клеточных автоматов

Химия и жизнь клеточных автоматов

История возникновения клеточных автоматов

“Чтобы приготовить эликсир мудрецов, или философский камень, возьми, сын мой, философской ртути и накаливай, пока она не превратится в зеленого льва. После этого прокаливай сильнее, и она превратится в красного льва… Киммерийские тени покроют реторту своим темным покрывалом, и ты найдешь внутри нее истинного дракона, потому что он пожирает свой хвост…

Он загорится и, приняв вскоре великолепный лимонный цвет, вновь воспроизведет зеленого льва… Наконец, мой сын, тщательно ректифицируй, и ты увидишь появление горючей воды и человеческой крови” (цит. по Рабинович В.Л. Алхимический миф и химера собора Парижской богоматери//в книге Заблуждающийся разум?: Многообразие вненаучного знания/Отв. ред. и сост. И.Т. Касавин.-М.

: Политиздат, 1990.-464 с., стр. 100)

Примерно так представляли себе средневековые алхимики процесс приготовления философского камня – средства для превращения или “трансмутации” металлов в золото.

Кроме философского камня, у алхимиков был еще один знаменитый проект – создание химическим путем искусственного человечка – гомункулуса.

Обратите внимание

Своих целей они так и не добились, хотя существенно обогатили арсенал технических средств, заложив тем самым фундамент современной экспериментальной химии.

К таинствам превращения веществ в живых системах наука подобралась только в XX столетии. Причем даже современная биохимия пока не может в полной мере искусственно воссоздавать процессы, лежащие в основе феномена жизни.

Тем не менее, определенные успехи в области моделирования необыкновенных “жизнеподобных” химических реакций в современной науке все же достигнуты. Огромный шаг в этом направлении совершил сразу после войны советский ученый Белоусов. История его открытия весьма драматична. Работы Белоусова долго отказывались признавать.

Слава пришла к ученому уже после смерти. Открытая реакция была названа его именем и вошла во все классические труды по неравновесной термодинамике и теории самоорганизации.

Причина длительного непризнания открытия состояла в том, что оно не вписывалось в догмы традиционной термодинамики. В этом смысле реакция Белоусова представляет собой глубокую и общую метафору биохимических процессов.

Химию живых систем невозможно понять в рамках традиционной термодинамики. Химические процессы в живых системах идут в совсем ином направлении, чем указывает классическая физическая химия, а именно – в сторону роста упорядоченности и усложнения итоговых структур.

Из химического хаоса возникает химический порядок.

В процессе реакции, открытой Белоусовым, из первичного хаоса смеси реагентов рождаются макроскопические упорядоченные структуры в форме кольцевых волн. Это, конечно, пока еще не гомункулус, но существенный шаг вперед по пути моделирования химических процессов нового типа – самоорганизационных процессов. А именно они и лежат в основе возникновения и эволюции живых систем.

В еще большей степени проблема создания гомункулуса, т.е. некоего подобия искусственного существа, нашла свое выражение в компьютерных науках.

Важно

На заре компьютерной революции, так же, как и в эпоху расцвета алхимических исканий, казалось, что нужно еще немного наворотить электроники, чуть-чуть подработать программное обеспечение и… электронный гомункулус начнет вещать бесстрастным металлическим голосом из чрева железных шкафов, набитых проводами и обрамленных мигающими лампочками.

По своей наивности эти мечты были вполне сравнимы с фантазиями алхимиков, только-только начавших постигать таинства химических превращений веществ.

Им так же, как и пионерам компьютерной эры, представлялось, что их новая всемогущая наука наук перевернет все человеческие знания, позволит варить золото из ртути и, смешивая химические ингредиенты, взращивать в ретортах искусственных человечков. Несмотря на всю наивность и беспочвенность этих мечтаний, те и другие, несомненно, продвигали познание вперед, и, кто знает, может, когда-нибудь мечта человечества об искусственном создании чего-то, хотя бы отдаленно напоминающего живые системы, все-таки сбудется.

Ниже мы рассмотрим одну игру, принадлежащую к семейству игр клеточных автоматов, в которой удивительным образом соединились химия, компьютерные науки и современная теория самоорганизации. Речь пойдет о так называемой перемешивающей машине.

Перемешивающая машина – это своеобразное развитие знаменитой клеточной модели жизни Дж. Конвэя. Как и все клеточные автоматы, перемешивающая машина представляет собой матрицу, состоящую из множества параллельно взаимодействующих друг с другом ячеек.

Именно таким образом организованные параллельные вычислительные устройства, по мнению многих теоретиков искусственного интеллекта, позволят приблизиться к решению проблемы моделирования настоящих мыслительных процессов.

Правила взаимодействия ячеек в перемешивающей машине таковы, что дают возможность моделировать волновые структуры, точь в точь напоминающие те, которые можно наблюдать в уже упоминавшейся химической реакции, открытой Белоусовым.

Клеточный автомат “Перемешивающая машина” был предложен М. Герхардом и Х. Шустером из Билефельдского университета ФРГ (см. статью А.К. Дьюдни “Перемешивающая машина”-клеточный автомат, моделирующий химические реакции//В мире науки, 1988 – №10, с.82-86).

Правила взаимодействия ячеек автомата Герхарда и Шустера удобно излагать, используя эпидемическую терминологию. Отдельная клетка может находиться в некотором множестве состояний. Обозначим их целыми числами от 0 до n. Клетки, находящиеся в состоянии 0, будем называть здоровыми, а клетки, находящиеся в состоянии n, – больными.

Все остальные промежуточные состояния интерпретируются как зараженность различной степени. Иными словами, клетка в рассматриваемой модели может быть либо здорова, либо заражена, либо больна. В зависимости от того, к какому из этих трех типов клетка относится в данный момент времени t, ее судьба в момент времени t+1 складывается по-разному.

Совет

Если клетка здорова (то есть ее состояние x(i,j)=0), то ее состояние в момент времени t+1 будет определяться формулой:

Y(i,j)=Round(A/k1,0)+Round(B/k2,0),

Здесь A – это количество зараженных, а B – количество больных клеток в окрестности. Константы k1 и k2 представляют собой некие изначально задаваемые управляющие параметры. Функция Round возвращает округленное до указанного количества знаков значение выражения.

Если в момент времени t клетка заражена (то есть x(i,j) имеет любое значение, большее 0, но меньшее n), то в момент времени t+1 ее состояние будет определяться формулой:

Y(i,j)=Round(S/A,0)+G,

Здесь, как и прежде, А – количество зараженных соседей в окрестности клетки, а S – это сумма состояний всех соседних клеток, включая саму X(i,j).

Константа G также представляет собой некий изначально задаваемый управляющий параметр. Следует помнить, что Y(i,j) ни при каких условиях не может превышать максимального значения n.

Поэтому, если в процессе вычислений значение выходит за эти рамки, его следует приравнять к n.

Наконец, если клетка в момент времени t больна (то есть, ее состояние равно n), то в следующий момент времени t+1 она всегда переходит в состояние 0, то есть выздоравливает.

Программный код, моделирующий поведение перемешивающей машины, приведен на врезке. Для того, чтобы не изменять общие правила на границах поля, я “свернул” клеточную матрицу в тор. Процедура сворачивания лишает поверхность ее границ, а значит, и “пограничных” проблем. Для хранения состояний ячеек в предыдущем и последующем поколении используются два двухмерных массива – X(i,j) и Y(i,j).

Обратите внимание

Результат выводится на форму в виде мозаики квадратиков, раскрашенных в градации серого цвета в соответствии с состояниями ячеек в момент времени t. При моделировании перемешивающей машины я категорически рекомендую читателям использовать анимационные технологии, поскольку динамика образования и движения волновых фронтов производит совершенно неповторимое впечатление именно в движении.

Как и во многих других играх клеточных автоматов, в поведении перемешивающей машины угадываются биоподобные черты. Клеточная плазма, первоначально хаотическая, начинает беспокойно пульсировать.

Постепенно ее пульсации становятся все более регулярными и, наконец, в ее недрах рождаются устойчивые центры, генерирующие медленно распространяющиеся во все стороны ряды кольцевых волн.

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

В описанной игре воспроизводится удивительное явление самоорганизации, которому, по существу, обязан своим существованием и окружающий нас мир, и мы сами. Из хаотической смеси находящихся в случайных состояниях клеточек постепенно сами собой возникают некие макроскопические образования.

Массивы клеток согласованно циклически меняют свои состояния, кооперируясь в связные коллективные структуры. Не правда ли, картина, достойная быть первым кадром научно-популярного фильма под названием “Сотворение мира”.

Если когда-либо в будущем удастся создать машины, способные действительно думать, а не просто считать, то они, несомненно, будут основываться на принципах самоорганизации. В первой главе известной монографии семидесятых годов “Искусственный интеллект”, ее автор Э.

Хант писал: “Можно ли сказать что-нибудь содержательное о самоорганизации самой по себе? Некоторые думают, что можно, но я не из их числа… Это предубеждение и послужило причиной того, что самоорганизующиеся системы в книге не обсуждаются”. Сейчас феномен самоорганизации стал намного более понятен современной науке.

Важно

И именно в этом направлении следует искать решение проблемы искусственного моделирования мышления. С древнейших времен лучшие умы человечества пытаются постичь тайну развития.

Как, почему хаотическая первосубстанция, самоструктурируясь, породила и продолжает порождать столь сложные и высокоупорядоченные структуры? Уже очень давно было замечено, что основа механизма саморазвития материи состоит в вечном стремлении различных противоначал слиться в недостижимой гармонии. В играх клеточных автоматов эта диалектика предстает в овеществленном, наблюдаемом виде, демонстрируя феномен развития в очень ярких и завораживающе красивых формах.

А. КОЛЕСНИКОВ,
andr61@mail.ru

Dim x(210, 210) As Integer
Dim y(210, 210) As Integer
Dim c As Byte
Dim n As Byte
Dim m As Byte
Dim k1 As Single
Dim k2 As Single
Dim g As Byte
Private Sub Form_Click()
For f = 1 To 150 x(0, 0) = x(n, n): x(0, n + 1) = x(n, 1): x(n + 1, 0) = x(1, n): x(n + 1, n + 1) = x(1, 1) For k = 1 To n x(0, k) = x(n, k): x(k, 0) = x(k, n): x(n + 1, k) = x(1, k): x(k, n + 1) = x(k, 1) Next k For i = 1 To n For j = 1 To n Select Case x(i, j) Case Is = 0 a = 0: b = 0 For k = i – 1 To i + 1 For l = j – 1 To j + 1 Select Case x(k, l) Case 1 To m – 1 a = a + 1 Case Is = m b = b + 1 End Select Next l Next k y(i, j) = Round((a / k1), 0) + Round((b / k2), 0) blue = 0: red = 0: green = 0 Case 1 To m – 1 a = 0: s = 0 For k = i – 1 To i + 1 For l = j – 1 To j + 1 If x(k, l) > 0 And x(k, l) < m Then a = a + 1 s = s + x(k, l) Next l Next k y(i, j) = Round((s / a), 0) + g If y(i, j) > m Then y(i, j) = m Case Is = m y(i, j) = 0 End Select c = (x(i, j) / m) * 255 Line (4 * (i – 1), 4 * (j – 1))-(4 * i – 1, 4 * j – 1), RGB(c, c, c), BF Next j Next i For i = 1 To n For j = 1 To n x(i, j) = y(i, j) Next j Next i
Next f
End SubPrivate Sub Form_Load()
Randomize
n = 25
m = 100
k1 = 5
k2 = 4
g = 28
For i = 1 To n For j = 1 To n x(i, j) = m * Rnd Next j
Next i
End Sub

Клеточные автоматы (обзор Гарднера)

История возникновения клеточных автоматов

Книга Мартина Гарднера «Математические досуги» вышла в 1972 году. Её последняя глава посвящена игре «Жизнь», в которой также есть небольшой обзор теории клеточных автоматов. Многие сведения уже устарели.

Например, было доказано, что в «Жизни» существует универсальный конструктор (машина Тьюринга), а в 2002 году универсальный конструктор был построен.

Тем не менее, обзор всё равно опубликован, так как он может быть полезен при первом знакомстве с этой областью.

Игра Конуэя «Жизнь» вызвала огромный интерес у ученых, занимающихся разработкой проблем, связанных с использованием компьютеров. Поэтому остановимся на некоторых основных фактах развития «теории клеточных автоматов» — области науки, занимающейся изучением игр, аналогичных конуэевской «Жизни».

Всё началось с 1950 года, когда Джон фон Нейман поставил перед собой задачу доказать возможность существования самовоспроизводящихся автоматов. Если такую машину снабдить надлежащими инструкциями, она построит точную копию самой себя. В свою очередь две машины («мама» и «дочь») смогут построить ещё две; четыре машины построят четыре и т. д.

Фон Нейман впервые доказал возможность существования таких машин с помощью «кинематических» моделей машины, способной передвигаться по складу запасных частей, отбирать необходимые детали и собирать новые машины, как две капли воды похожие на неё.

Позднее, воспользовавшись идеей, высказанной его другом Станиславом Уламом, фон Нейман дал более изящное и абстрактное доказательство возможности существования самовоспроизводящихся машин.

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

На состояние любой клетки оказывает влияние конечное число соседних клеток. Во времени состояния пространства изменяются дискретно, в соответствии с «правилами перехода», которые необходимо применять одновременно ко всем клеткам.

Клетки соответствуют основным частям автомата с конечным числом состояний, а конфигурация из «живых» клеток — идеализированной модели автомата. Именно в таком клеточном пространстве и развёртывается действие придуманной Конуэем игры «Жизнь». Соседними для каждой клетки в «Жизни» считаются восемь непосредственно окружающих её клеток.

Совет

Клетка может находиться в двух состояниях (либо на ней стоит фишка, либо клетка пуста). Правила перехода определяются генетическими законами Конуэя (рождение, гибель и выживание).

Фон Нейман, применяя правила перехода к пространству, каждая клетка (или ячейка) которого могла находиться в 29 состояниях и имела четыре соседние клетки (примыкающие к данной по вертикали и горизонтали), доказал существование самовоспроизводящейся конфигурации, состоящей примерно из 200 000 клеток.

Причина столь чудовищных размеров конфигурации объяснялась тем, что фон Нейман намеревался применить своё доказательство к реальным автоматам и специально подобрал клеточное пространство, способное имитировать машину Тьюринга — идеальный автомат, названный в честь изобретателя, английского математика А. М. Тьюринга, и способный производить любые вычисления.

«Погрузив» универсальную машину Тьюринга в созданную им конфигурацию, фон Нейман получил возможность создать «универсальный конструктор», способный построить любую конфигурацию в пустых клетках пространства, в том числе и точную копию самого себя.

За время, прошедшее после смерти фон Неймана (последовавшей в 1957 году), предложенное им доказательство существования самовоспроизводящейся системы (речь идет именно о «чистом» доказательстве существования, а не о построении используемой в доказательстве фон Неймана конфигурации) удалось значительно упростить.

Рекорд по простоте установило доказательство, найденное выпускником инженерного факультета Массачусетского технологического института Эдвином Р. Бэнксом. В нём используются «ячейки», которые могут находиться лишь в 4 состояниях.

Самовоспроизведения в тривиальном смысле — без использования конфигураций, включающих в себя машину Тьюринга, — добиться легко. Удивительно простой пример «тривиальной» самовоспроизводящейся системы предложил около 10 лет назад Эдвард Фредкин.

В этой системе ячейки могут находиться лишь в двух состояниях, каждая из них, как и в примере фон Неймана, имеет четырёх соседей, а правила перехода сводятся к следующим. Каждая клетка, имеющая в момент времени t четное число (0, 2, 4, …

) живых соседей, в момент времени t + 1 становится пустой (то есть переходит в нулевое состояние или, если она уже находилась в нулевом состоянии, остаётся в нём). Каждая клетка, имеющая в момент времени t нечетное число (1, 3, …

) соседей, в момент времени t + 1 становится живой (то есть переходит в ненулевое состояние или сохраняет его, если она уже в нём находилась).

Через 2n ходов (число n зависит от выбора конфигурации) любая конфигурация живых клеток в таком пространстве воспроизведет себя четыре раза: одна копия расположится справа, другая — слева, третья — сверху, четвёртая — снизу от того (уже пустого) места, где находилась начальная конфигурация.

Обратите внимание

Новая конфигурация через 2n шагов снова размножится (с коэффициентом воспроизводства, равным 4) и т. д. Число копий увеличивается в  геометрической прогрессии 1, 4, 16, 64… На рисунке показаны полтора цикла размножения тримино в форме прямого угла.

Терри Виноград в 1967 году обобщил правила Фредкина на любое число соседей, произвольную схему примыкания клеток и размерность (результаты Винограда относятся к клеткам, число состояний которых просто).

Множество автоматов такого рода, отличающихся друг от друга схемой примыкания соседних клеток, числом состояний и правилами перехода, исследовал С. Улам. В опубликованной им (совместно с Робертом Г. Шрандтом) в 1967 году статье «О рекурсивно определённых геометрических объектах и схемах роста» Улам описал несколько игр.

На рисунке показано сорок пятое поколение организма, родившегося из одной-единственной фишки, стоявшей в центральной клетке.

Как и в игре Конуэя, клетки в игре Улама могут находиться в двух состояниях, но соседними считаются клетки, примыкающие к данной лишь по вертикали, но не по диагонали («соседи» в смысле фон Неймана).

Рождение фишки происходит на клетке, имеющей одного и только одного соседа, а все клетки поколения n погибают после рождения поколения n + 2. Иначе говоря, на любом этапе эволюции выживают лишь два последних поколения. На рисунке черными изображены новорожденные клетки (их 444).

Зеленые клетки предыдущего поколения — их 404 — исчезнут на следующем ходу. Обратите внимание на характерную деталь, которую Улам назвал «обглоданной костью». Улам проводил эксперименты и с такими играми, в которых две конфигурация могли расти до тех пор, пока они не сталкивались.

В следующей за столкновением «битве» одной стороне иногда удавалось одержать верх над другой, а иногда обе армии исчезали. Улам рассмотрел также игры на трёхмерных досках — кубических «паркетах», заполняющих всё пространство. Основные результаты Улама собраны в его статьях, опубликованных в сборнике «Очерки теории клеточных автоматов» (Essays on Cellular Automata, University of Illinois Press, 1970, ed. by Arthur W. Burks).

Аналогичные игры можно вести и на бесконечных досках, клетки которых имеют форму равносторонних треугольников и правильных шестиугольников.

Несмотря на сильное внешнее отличие, по существу эти игры не вносят ничего нового, и с помощью подходящего определения «соседних» клеток их всегда можно свести к эквивалентным играм на обычной доске с клетками в форме квадратов. Соседними могут быть не только клетки, имеющие общие стороны или вершины.

Важно

Например, в шахматах для клетки, на которой стоит конь, соседними (то есть влияющими на её состояние) считаются все клетки, на которые можно пойти конём или на которых стоят угрожающие ему фигуры.

Как заметил Беркс, такие игры, как шахматы, шашки и го, допустимо рассматривать как клеточные автоматы со сложными окрестностями каждой клетки (окрестностью называется совокупность соседей) и правилами перехода. Противники, делая очередной ход, выбирают среди множества допустимых состояний то, которое должно привести их к определённому конечному состоянию — выигрышу.

Среди наиболее значительных вкладов в теорию клеточных автоматов наибольшую известность получил предложенный Эдвардом Ф. Муром способ доказательства существования конфигураций, которые Джон У. Тьюки назвал «садами Эдема». Эти конфигурации не могут возникать в процессе игры, поскольку никакая конфигурация отличного от них типа не может их породить.

«Сады Эдема» должны быть заданы с самого начала — в нулевом поколении. Поскольку конфигурации такого типа не имеют «предшественников», они не могут быть самовоспроизводящимися. Подробно метод Мура изложен в его популярной статье «Математика в биологических науках» (Scintific American, сентябрь 1964).

Более строгое изложение дано в уже упоминавшемся сборнике под редакцией Беркса.

Алви Р. Смит обнаружил простой способ, позволяющий применять метод Мура к игре Конуэя. Из теоремы Мура следует, что конфигурация типа «садов Эдема» должна возникать в игре Конуэя. К сожалению, доказательство теоремы ничего не говорит о том, как найти «сады Эдема», и они до сих пор не обнаружены.

Конфигурация типа «садов Эдема» может оказаться и простой, и чрезвычайно сложной. С помощью одной из выведенных Муром формул Смит сумел доказать, что такую конфигурацию всегда можно заключить в квадрат со стороной в 10 миллиардов клеток, но и этот результат ненамного облегчает поиски конфигурации.

Сам Смит работает над созданием клеточных автоматов, имитирующих машины для распознавания образов. Хотя сегодня такая проблема может показаться имеющей лишь чисто теоретический интерес, вполне возможно, что когда-нибудь вычислительным машинам и автоматам понадобится «сетчатая оболочка» для распознавания образов.

Создание планерного ружья открывает волнующую возможность построения в игре Конуэя машины Тьюринга, способной (в принципе) производить все действия, которые только доступны самым совершенным из современных компьютеров.

Планеры можно было бы использовать в качестве «единичных импульсов» для хранения и передачи информации, а также для выполнения всех операций, допускаемых схемой реальной вычислительной машины.

Следующий вопрос после создания машины Тьюринга — это создание универсального конструктора, позволяющего осуществлять нетривиальное самовоспроизведение конфигураций.

Совет

До сих пор никому не удалось «построить» машину Тьюринга в пространстве, все клетки которого могут находиться лишь в двух состояниях, а «соседние» клетки понимаются в смысле Конуэя (то есть должны иметь с данной либо общую сторону, либо общую вершину). Доказано, что в пространстве, все клетки которого могут находиться в двух состояниях, а «соседство» понимается в смысле фон Неймана, построить машину Тьюринга невозможно.

Клеточные автоматы (из вики)

История возникновения клеточных автоматов

ИСТОРИЯ

Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1930-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота.

В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра «Жизнь».

Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии.

Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает».

Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между очевидным хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры — сочетания клеток, движущиеся по сетке как единое целое. Возможно построить автомат, в котором глайдеры будут выполнять некоторые вычисления

В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.

Клеточные автоматы в естественной среде

Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска раковин ряда морских моллюсков, например, родов Conus или Cymbiola, генерируется естественным одномерным клеточным автоматом, результат эволюции которого похож на Правило 30.

Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста раковины полоса клеток формирует цветной узор на её поверхности.

Растения регулируют приток и отток газообразных веществ посредством механизма клеточных автоматов. Каждое устьице на поверхности листа действует как ячейка[источник не указан 277 дней].

Нейронные сети также могут быть использованы как клеточные автоматы. Сложный движущийся узор на коже головоногих является отражением паттернов активирования в мозгу животных.

Классификация

Классификация по типам поведения

Правило 40(Класс 1) со случайными начальными условиями. Как видно, информация быстро исчезает в этой системе.

Правило 3(Класс 2) со случайными начальными условиями. Очевидно появление периодических структур

Правило 18(Класс 3) со случайными начальными условиями. Видно, что начальные условия порождают хаотические движения внутри системы.

Обратите внимание

Правило 193(Класс 4) со случайными начальными условиями. Можно увидеть порождение устойчивых структур(колонка белых треугольников и взаимодействие таких структур в других частях изображения.)

Стивен Вольфрам в своей книге A New Kind of Science предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:

  • Класс 1: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния и его гомогенность. Любые случайные конструкции в таких правилах быстро исчезают.
  • Класс 2: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния, либо возникновение колебаний. Большинство случайных структур в начальных условиях быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы.
  • Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают широкое, неопределямое влияние на ход всей эволюции системы.
  • Класс 4: Результатом эволюции почти всех правил являются структуры, которые взаимодействуют сложным и интересным образом с формированием локальных, устойчивых структур, которые способны выживать длительное время. В результате эволюции правил этого класса могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают широкое, неопределямое влияние на ход всей эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу. Последний факт был доказан для Правила 110 и игры «Жизнь».

Такого рода определения носят по большей части качественный характер и их можно по разному интерпретировать. Вот что Вольфрам говорит об этом:

Практически при всякой попытке классификации будут возникать ситуации, когда по одному свойству предмет можно отнести к одному классу, а какому-либо другому свойству — к другому классу. Такая же ситуация и с клеточными автоматами: встречаются правила, которые показывают свойства, присущие одновременно одному и другому классу.

Оригинальный текст  (англ.)  

Тоталистичные клеточные автоматы

Существует специальный класс клеточный автоматов, называемых тоталистичными.

На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу(обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки.

Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек .

Термин тоталистичный происходит от английского totalistic. В свою очеред total может быть переведено как сумма, что и отражено в принципе действия этого типа автоматов, когда новое значение клетки зависит от суммы значений других клеток.

Связанные определения клеточных автоматов

Существует множество возможных обобщений концепций клеточных автоматов.

Клеточный автомат работающий на сетке, компонентами которой являются шестиугольники, а не квадраты(правило 34/2)

Один из них — использование сетки не с квадратами(гиперкубами в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом, то шестиугольники будут клетками.

Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо вместе специальные правила отношений с клетками-соседями.

Другой способ обобщения — использование нерегулярной сетки(например, в виде Мозаики Пенроуза).

Ещё один способ — использование вероятностных правил. Такие клеточные автоматы называются стохастическими. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой.

Или, например, в игре «Жизнь» добавляется правило, что клетка с определенной вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.

Определение соседства клетки может меняться с течением времени иили пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом — вертикально смежные.

В клеточных автоматах на новое состояние клетки не влияют новые состояния смежных клеток. Правило можно поменять: можно сделать так, что, например, в блоках 2 на 2 состояния клеток зависят от состояния клеток внутри блока и от таких-же смежных блоков.

Существуют непрерывные клеточные автоматы. В таких системах вместо дискретного набора состояний используются непрерывные функции (обычно определяемые на промежутке ).

Свойство обратимости

Клеточный автомат называется обратимым, если для каждой текущей конфигурации существует только одна предшествующая конфигурация.

Если рассматривать клеточный автомат как функцию, отображающую одну конфигурацию в другую, то обратимость предполагает биективность этой функции. Если клеточный автомат обратим, то его обратная эволюция также может быть описана клеточным автоматом.

Конфигурации, не имеющие предшествующих, то есть недостижимые в данном клеточном автомате, носят название «Сады Эдема».

Важно

Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.

Обратимые клеточные автоматы часто используют для моделирования таких физических феноменов, как динамика жидкости и газа, поскольку они подчиняются законам термодинамики. Такие автоматы специально создаются обратимыми.

Такие системы изучались Томасо Тоффоли (Tommaso Toffoli) и Норманом Марголусом (Norman Margolus). Существует несколько типов обратимых конечных автоматов. Наиболее известными являются клеточный автомат второго порядка и блочный клеточный автомат.

Обе эти модели следуют несколько модифицированному варианту определения клеточного автомата, однако доказано, что они могут быть эмулированы традиционным клеточным автоматом со значительно большим размером окрестности и числом состояний.

Также, было доказано, что любой обратимый клеточный автомат может быть сэмулирован блочным клеточным автоматом.

Компьютерное моделирование реакции Белоусова — Жаботинского в тонком слое жидкости в чашке Петри.

Реакция Белоусова — Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А. М.

 Жаботинский, продолжая работу Б. П.

 Белоусова, обнаружил, что тонкий однородный слой смеси определённых химических веществ способен образовывать движущиеся геометрические узоры, такие как концентрические круги и спирали.

История

История возникновения клеточных автоматов

Прообразом современных клеточных автоматов можно считать треугольник Паскаля, известный с десятого века. Вот что пишет Википедия:

Если очертить треугольник Паскаля, то получится равнобедренный треугольник. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Продолжать треугольник можно бесконечно. Строки треугольника симметричны относительно вертикальной оси. Имеет применение втеории вероятностей и обладает занимательными свойствами.

Если заменить нечётные числа точками, а чётные сделать прозрачными, то получаем треугольник Серпинского:

Рекомендую обзор треугольников Паскаля и Серпинского, опубликованный на Арбузе.

Клеточный автоматОпять обратимся к Википедии:

“Станислав Улам, работая в Лос-аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая.

Совет

Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого “запаса частей”, из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система.

Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий “внутри” клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний.

Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.”

Алгоритм Живые Пиксели на бесконечном поле бесконечно копирует любой начальное расположение активных пикселей, то есть решает задачу фон Неймана.

Определение клеточного автомата из Википедии:

“Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решётку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0.

Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых соседством. К примеру, соседство может быть определено как все ячейки на расстоянии не более 2 от текущей.

Для работы клеточного автомата требуется задание начального состояния всех ячеек, и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки.

Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решётке.”

Достаточно обширный анализ клеточных автоматов сделан в программе  Cellular Automata Laboratory http://www.fourmilab.ch/cellab/cellab.zip В программе реализованы 37 видов автоматов, которые описаны по-английски на странице:http://www.fourmilab.ch/cellab/manual/rules.

Обратите внимание

html Примеры к программе не используют алгоритм, повторяющий Живые Пиксели, изучение описаний алгоритмов показывает, что Живые Пиксели являются частным случаем алгоритма Эдварда Фредкина Fredmem.

Близким к Живым Пикселям является алгоритм Fractal, который также является частным случаем алгоритма Fredmem.

Эдвард Фредкин указывает на то, что его алгоритм является примером «самовоспроизводства», то есть «размножения» – начальная фигура через определённое число итераций превращается в несколько таких же фигур. Такую картину мы наблюдаем в Живых Пикселях на бесконечном поле.

Ещё более полная подборка клеточных автоматов приводится на сайте:http://www.mirekw.com/ca/rullex_wlif.html

Алгоритмы «Эволюция», и затем «Живые Пиксели» были разработаны и программно реализованы в 2012м году. На сегодняшний день многие аспекты алгоритмов остаются неизученными. Читатель может принять участие в анализе «Живых Пикселей» и «Эволюции» и поиске интересных конструкций, используя программу NeoNeuro Live Pixels – Живые Пиксели.

История возникновения клеточных автоматов

История возникновения клеточных автоматов

Понятие клеточных автоматов вводилось учёными неоднократно. Они могли непринципиально отличаться названием или заложенным в них механизмом функционирования.

В теории динамических систем они присутствуют как один из разделов топологической динамики, в электротехнике их можно встретить как итеративные массивы, различные компьютерные игры построены на основе клеточного поля с различной геометрией клеток и правилами поведения.

Интересующие нас клеточные автоматы как инструмент математического моделирования ввёл в конце 1940 годов фон Нейман, следуя идее Улама.

Важно

В качестве основной цели преследовалась необходимость обеспечения более реалистичных моделей поведения сложных и распределённых в двух- или трёхмерном пространстве систем.

В его клеточных автоматах и объекты, характеризующиеся массивами пассивных данных, и объекты, описывающиеся как вычислительные устройства, собираются из одного типа структурных элементов и подчиняются одним и тем же законам.

При том, что фон Нейман был ведущим физиком и математиком, точные физические рассуждения в его работах по клеточным автоматам отсутствуют. Учёного в большей степени интересовало объяснение определенных аспектов биологии.

И в самом деле, принципы межклеточного взаимодействия, которые им были предложены для реализации с помощью клеточного автомата, оказались схожими с открытыми в следующем десятилетии механизмами, реально наблюдаемыми в биологических системах.

В конце Второй мировой войны, когда фон Нейман участвовал в создании одного из первых электронных компьютеров, немецкий инженер Цузе прятался от нацистов в Австрии.

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

Цузе особенно интересовался численными моделями в механике, поэтому интерес к физическим процессам на микроуровне играл основную роль в его работе.

Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана одним из конструкторов первого электронного компьютера Бёрксом, который сохранил активный интерес к этой области и на протяжении последующих лет.

Совет

Его «Очерки по клеточным автоматам» являлись хорошим обобщением знаний того времени в данной области. Одновременно с работами Бёркса его коллега по Мичиганскому университету Голланц приступил к использованию клеточных автоматов для решения задач адаптации и оптимизации.

Им был разработан программный имитатор универсальных клеточных автоматов общего назначения.

Тем временем специалисты-математики начали пристально изучать итерационные преобразования в пространственно-распределённых структурах с дискретным набором состояний – по сути, клеточных автоматах.

Узкий круг научного общения, изолированность отдельных научных сообществ и, как следствие, отсутствие единой терминологии вели, с одной стороны, к частичному дублированию работ, а с другой стороны, – к их замедлению.

Игра английского математика Конуэя «Жизнь», основанная на принципах клеточного автомата, была представлена широкой общественности в 1970 году.

Благодаря её популяризации с помощью ряда научных и научно-популярных изданий, в том числе в журнале Scientific American, она довольно продолжительное время пользовалась особым успехом и закрепила понятие «клеточный автомат» в научной терминологии исследователей.

Вопрос о способности клеточных автоматов моделировать законы физики, а не только общие феноменологические аспекты, был поставлен американскими учёными Фредкином и Тоффоли. Основной целью их исследования была формулировка компьютероподобных моделей в физике.

Модели, которые явным образом сводят макроскопические явления к точно определённому множеству микроскопических процессов, вызывали и вызывают у научного сообщества наибольший интерес потому, что особенно понятны и убедительны.

Обратите внимание

Этот подход стал по-настоящему популярен. Со временем он стал использоваться взамен или вместе с известными моделями в виде дифференциальных уравнений физики.

Ячеечные модели, популярные в моделировании химико-технологических процессов, также базируются на принципах клеточных автоматов.

Использование принципов клеточно-автоматного моделирования позволяет, при необходимости, привнести вероятностную составляющую, что, в свою очередь, даёт возможность учесть стохастическую природу многих изучаемых таким образом процессов и явлений.

Таким образом, клеточные автоматы нашли широкое и устойчивое применение в качестве концептуальных и практических моделей для описания поведения пространственно-распределённых динамических систем. А их аналогия с процессами в живых клеточных комплексах дала многим современным учёным моральное право выделить их как отдельное направление развития методов и систем искусственного интеллекта.

Как и в случае других методов искусственного интеллекта, при использовании клеточных автоматов для решения различных прикладных задач повышенной сложности в последние годы характерно их сочетание с другими методами.

В частности, есть работы по нечётким клеточным автоматам, где состояние клетки описывается нечётким образом и определяется в результате применения операций нечёткой логики или механизма нечётко-логического вывода, и работы по ячеечно-нейросетевым моделям, в которых состояние клетки вычисляется с использованием нейронной сети.

искусственные нейронные сети клеточные автоматы

Оцените статью
Просто о технологиях
Добавить комментарии

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: