Как называется клеточный автомат для строительства компьютера

Обновлено: 05.07.2024

Данная статья, надеемся, привлечет внимание программистов к такой чрезвычайно увлекательной и полезной области дискретной математики, как клеточные автоматы, которые могут обладать весьма сложным поведением, несмотря на простоту описания их клеток. Один из крупнейших специалистов в области информатики — Марвин Минский [1] считает, что самым важным при этом, видимо, является изучение различных путей возникновения сложного поведения при использовании простых устройств, действий, описаний или концепций. Нам кажется, что не существует ничего более подходящего для этой цели, чем клеточные автоматы.

В последние десятилетия проводился ряд исследований, посвященных анализу динамических систем. К этой области, в частности, относится теория самовоспроизводящихся структур [2]. Однако использование в ней формализма, основанного на решении рекуррентных нелинейных уравнений и связанного с применением теории функций комплексных переменных, является нетривиальным подходом. Был предложен другой способ построения самовоспроизводящихся структур, основанный на применении рекурсивных процедур при написании программ, не упрощающий, однако, понимания процессов вычислений [3].

К рассматриваемой области принадлежит также теория хаоса [4], признанная, наряду с теорией относительности и квантовой теорией [5], одним из основных теоретических достижений XX в. Нельзя сказать, что математический аппарат, применяемый в ней, прост. И для этой теории весьма актуальны исследования клеточных автоматов. Такие автоматы, как отмечалось выше, зачастую порождают сложное поведение даже при использовании действительно очень простого и наглядного математического аппарата. В настоящей работе поведение каждой из клеток описывается одной булевой формулой и демонстрируются различные формы их самовоспроизведения (рост, клонирование, перемещение). Рассматриваются два класса клеток: с памятью, обладающие лишь двумя состояниями, и без памяти.

Клеточные автоматы

Клеточные автоматы были предложены в работе фон Неймана [6]. Большой интерес к ним вызван тем, что такие автоматы являются универсальной моделью параллельных вычислений подобно тому, как машины Тьюринга являются универсальной моделью для последовательных вычислений [7].

Клеточный автомат — дискретная динамическая система, представляющая собой совокупность одинаковых клеток, одинаково соединенных между собой. Все клетки образуют так называемую решетку клеточного автомата. Эти решетки могут быть разных типов и отличаться как по размерности, так и по форме клеток. В настоящей работе каждая клетка — это конечный автомат, состояние которого определяется состояниями соседних клеток и, возможно, ее собственным. В клеточных автоматах, как в моделях вычислений, не рассматриваются входные и выходные воздействия. При аппаратной реализации клеточные автоматы обычно называют однородными структурами [8]. В общем случае клеточные автоматы обладают следующими свойствами.

Изменения значений всех клеток происходят одновременно после вычисления нового состояния каждой клетки решетки.
Решетка однородна - невозможно различить какие-либо две области решетки по ландшафту.
Взаимодействия локальны. Лишь клетки окрестности (как правило, соседние) способны повлиять на данную клетку.
Множество состояний клетки конечно.

Клеточные автоматы можно реализовать разными способами. В данной работе применен такой подход.

Вводятся два массива для хранения состояний клеток: первый из них содержит текущее состояние каждой клетки, второй предназначен для хранения нового ее состояния.
Определяется функция переходов клетки решетки. Для выявления следующего ее состояния в качестве параметров в функцию переходов передаются текущие значения состояний клеток окрестности, возможно, включая ее саму. Эта функция будет задана в виде булевой формулы.
На нулевом шаге решетка (первый массив) заполняется начальными данными, что полностью определяет поведение системы для выбранных решетки и функции переходов клетки.
вычисления новых состояний вводится цикл. На каждой итерации для любой клетки, используя в качестве переменных элементы первого массива, определяется ее новое состояние, помещаемое во второй массив. Значения аргументов функции переходов берутся из первого массива.
По завершении итерации значения из всех элементов второго массива переносятся в первый, что обеспечивает синхронное изменение значений состояний всех клеток решетки.
Визуализируется содержимое решетки. В зависимости от ее размерности (одномерная или двумерная) отображение решетки производится по-разному.
6.1. Для одномерной (линейной) решетки после каждой итерации выводится соответствующая ей строка. Их расположение одна под другой позволяет наблюдать динамику системы во времени (ось времени направлена вертикально вниз).
6.2. Для двумерной (плоскостной) решетки в каждый момент времени отражается результат лишь последней итерации. Последовательный переход от одной итерации к другой позволяет наблюдать динамику системы.
Нажатием клавиши выполняется переход к пункту 4, а нажатие на клавишу q завершает работу программы.

Одномерные клеточные автоматы

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

где f — функция переходов клетки;
y'[i] — состояние i-й клетки в следующий момент времени;
y[i-1] — состояние (i-1)-й клетки в данный момент времени;
y[i] — состояние i-й клетки в данный момент времени;
y[i+1] — состояние (i+1)-й клетки в данный момент времени.

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

Пример 1. Пусть функция переходов клетки имеет такой вид:

y'[i] = y[i-1] | y[i] | y[i+1],

где | — символ логической операции «дизъюнкция» на языке программирования Си.

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

Эта программа позволяет представить поведение клеточного автомата во времени (рис. 1). Такое поведение может быть названо «пирамида».

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

Пример 3. Второй клеточный автомат характеризуется следующей функцией переходов:

y'[i] = y[i-1] | y[i] ^ y[i+1],

где ^ — символ логической операции «неравнозначность» («сумма по модулю два») в языке программирования Си.

Выбирая в качестве начального то же заполнение решетки, что и в примере 1, получим поведение, которое можно назвать «пробор».

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

y'[i] = y[i-1] ^ y[i] ^ y[i+1].

Этот автомат при тех же начальных условиях, что и в предыдущем примере, порождает самовоспроизводящуюся структуру (рис. 4).

Двумерные клеточные автоматы

Окрестность из восьми клеток

В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь соседей. Для устранения краевых эффектов решетка так же, как и в предыдущем случае, «заворачивается» в тор. Это позволяет использовать для всех клеток автомата соотношение:

Пример 5. Наиболее известным из двумерных клеточных автоматов является автомат, моделирующий игру «Жизнь» [9]. В нем, как и во всех рассмотренных выше, клетки могут находиться в двух состояниях. Функция переходов клеток реализует следующие условия:

если данная клетка мертва (находится в состоянии "ноль"), то она оживет (перейдет в состояние "единица") при условии, что у нее имеются три живых соседа;
если данная клетка жива, то она останется живой только при условии, что у нее есть два или три живых соседа, в противном же случае она умрет.

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

Программа, реализующая игру «Жизнь», структура которой была описана выше, приведена в листинге 2. В ней решетка имеет размеры 23х23, а в качестве начальных условий выбран «планер» [9].

«Планер» был выбран в качества примера, так как является наиболее простым из «летающих» объектов. Он «летает» в том смысле, что перемещается за счет самовоспроизведения, происходящего с периодом в четыре шага.

Пример 6. В качестве примера самовоспроизведения рассмотрим клеточный автомат, функционирующий по правилу:

Данная функция принципиально не отличается от приведенной в примере 4, поскольку обе они вычисляют сумму по модулю два от состояний всех соседей и самой клетки.

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

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

где a и b — ширина и высота «зародыша» соответственно.

Для начальной конфигурации, изображенной на рис. 5, a = 3, b = 5. Поэтому T = 8, и следовательно, самовоспроизведение имеет место через 8, 16, 32, 64 и т. д. шагов.

Окрестность из четырех клеток

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

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

Пример 7. Для иллюстрации самовоспроизведения при помощи автомата с такой окрестностью выберем следующую функцию переходов:

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

При этом период полного самовоспроизведения вычисляется на основе соотношения:

Для рассматриваемого «зародыша» (рис. 5) период самовоспроизведения по горизонтали T_a равен 4 (рис. 7), а по вертикали, T_b равен 8 (рис. 8). Поэтому полный период самовоспроизведения T равен 8.

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

Пример 8. Если сохранить функцию переходов и выбрать в качестве начальной конфигурации единицу в центральной точке решетки, то на 15-м шаге получится конфигурация, изображенная на рис. 9, а на 29-м — на рис. 10.

Несмотря на то что решетка размером 23х23 способна находиться в 2 23?23 состояниях, для выбранных функции переходов и начальных условий она может быть лишь в 1024 различных состояниях, периодически повторяющихся. Сокращение числа состояний в данном случае обеспечивается только за счет размеров решетки и «заворачивания» ее в тор. Если бы решетка имела большие размеры, то на этих шагах состояния были бы другими, так как после 11-го шага противоположные края рассматриваемой решетки начинают влиять друг на друга. Это объясняется тем, что информация распространяется за шаг на одну клетку, и поэтому из центральной она дойдет до границы за (23-1)/2 шагов.

Автоматы с клетками без памяти

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

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

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

Поведение этого автомата во времени показано на рис. 11.

Интерактивная программа, реализующая пример двумерного автомата рассматриваемого класса с функцией переходов

приведена в работе [10].

Искусственная жизнь

Сейчас на смену термину «искусственный интеллект» пришел более широкий термин — «искусственный интеллект и искусственная жизнь» [11]. По мнению авторов, настоящую работу можно рассматривать как введение в «искусственную жизнь». Кроме того, отметим, что активно развивается такая наука, как синергетика. Ее название происходит от греческих слов «син» — совместный и «эргос» — действовать [12]. Поэтому синергетика — это наука о совместном согласованном поведении многих элементов как единого целого в составе сложной системы. Из изложенного следует, что данная работа может рассматриваться также и в качестве введения в «синергетику».

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

Работа выполнена при поддержке Российского фонда фундаментальных исследований по гранту №02-07-90114 «Разработка технологий автоматного программирования»

Хотелось бы поделиться с читателями Хабра довольно необычной разработкой: настоящим компьютером, сделанном в виде клеточного автомата, действующего по простому правилу Fireworld2 с четырьмя состояниями клеток. Текущая базовая версия компьютера называется "Ижора 1". Еще с 1950-х годов существует такая традиция: давать компьютерам географические названия.

Паттерн, состоящий из более 6 миллионов клеток, содержит 256 килобайт памяти и снабжен монохромным экраном 128x64 пикселей, отражающим состояние экранного раздела ОЗУ, примерно как в ZX Spectrum и других популярных исторических моделях персональных компьютеров. Программы можно писать на ассемблере, компилировать в машинный код, тестировать на симуляторе и вводить специальной утилитой в сам клеточный автомат. Другая утилита позволяет сохранять текущее состояние компьютера. Для запуска компьютера необходима программа Golly - лучшая на сегодня площадка для подобного рода исследований.

Ассемблер и эмулятор написаны на языке Common Lisp, скрипты для ввода программ в сам клеточный автомат и сохранения его состояния - в Python. Компьютер имеет 32-битную архитектуру и на данный момент в нем всего один регистр и одна операция: вычитание с условным переходом в случае отрицательного или нулевого результата (Subleq). Несмотря на примитивность такой модели, давно доказана ее универсальность. Существует даже операционная система Dawn OS, написанная для эмулятора Subleq-процессора.

Итак, суммируем: виртуальный компьютер с экзотической моделью программирования и ресурсами уровня древних ПК 1980-х, исполняющий всего около 10 операций в секунду, требующий современный компьютер с несколькими гигабайтами памяти (рекомендуемый минимум - 8 гигабайт), с эмулятором и ассемблером на Лиспе. Зачем и кому это нужно? Очень краткий ответ: ради хака и ретрокомпьютинга. Ниже - более подробно.

О клеточных автоматах

Клеточный автомат состоит из регулярной решетки ячеек, каждая из которых может находиться в нескольких состояниях. На каждом шаге или "поколении" состояние каждой ячейки меняется в соответствии с состояниями ее соседей. Чаще всего рассматриваются двухмерные автоматы с квадратными ячейками, действующие на теоретически бесконечном поле, имеющие небольшое число состояний (обычно не больше 5). Учитываются только ближайшие 8 соседей ячейки, т.н. окрестность Мура ранга 1. Наиболее знаменитый и исследованный автомат - игра "Жизнь" Джона Конуэя.

В целом клеточные автоматы можно рассматривать как обобщение машин Тьюринга с синхронным параллельным вычислением. Любая классическая машина Тьюринга может быть эмулирована клеточным автоматом. При исследовании того или иного клеточного правила, в свою очередь, часто ставится вопрос о полноте или неполноте его по Тьюрингу, то-есть о теоретической возможности использования к качестве универсального компьютера. В частности, полнота "Жизни" по Тьюрингу была доказана еще Конуэем. Я доказал ее для своего правила стандартным способом: путем эмуляции в нем другого, очень простого одномерного автомата, так называемого правила 110, о котором известно, что оно теоретически пригодно для сколь угодно сложных вычислений.Вышеупомянутая программа Golly позволяет определять и запускать также целый ряд других автоматов, включая одномерные и некоторые трехмерные, с большим радиусом окрестностей, с треугольными и шестиугольными ячейками. Можно там задать даже такие правила, в которых соседние ячейки никак не влияют на работу автомата, зато влияют находящиеся на некотором расстоянии (все или некоторые).

Джон фон Нейман еще в начале 1940-х создал сложный клеточный автомат с 29 состояниями, в котором возможно создать виртуального робота-репликатора, бесконечно копирующего самого себя. Надо заметить, что в момент разработки компьютеров еще не было: фон Нейман разработал свой автомат на бумаге! Конуэй показал, что чрезвычайно сложно может себя вести и удивительно простая модель с 2 состояниями.

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

В 2001 году я придумал клеточное правило с 4 состояниями, несколько напоминающее известные правила Brian's Brain и Starwars. Назвал я это правило Computer, но потом переименовал в Fireworld, по аналогии с правилом Wireworld, где еще в конце 1990-х был создан. скажем так, программируемый калькулятор. При всей элегантности этой штуки, 64 адреса программы и данных годятся лишь для демонстрации концепции. Хотя я знаком с человеком, написавшим для этого калькулятора целый язык программирования.

В Fireworld мне удалось еще 20 лет назад создать логические цепи, затем регистры памяти, сумматор, вычитатель, мультиплексоры и демультиплексоры, но что-либо более сложное там соорудить затруднительно из-за проблем синхронизации сигналов. В конце 2020 году, в ходе обсуждений на английском форуме Lifewiki, я попробовал добавить к Fireworld еще одно состояние: "провода", по поверхности которых могут бегать "сигналы". Правило оказалось весьма удачным: где-то за час я в нем, переставляя клетки на экране, нашел простые механизмы для всех побитных логических операций, а также для записи битов информации.

А. Fireworld:

"Красная" или живая клетка рождается, когда окружена двумя другими живыми клетками, одна из которых должна находиться рядом по диагонали, а другая - по горизонтали или вертикали. Легко запомнить, по аналогии с родителями обоих полов.

Красная клетка выживает, если у нее нет соседей, либо два соседа по горизонтали/вертикали (в любом положении) и еще один по диагонали.

Если клетка не выживает, на следующем шаге она становится "желтой". Мне не нравится обозначение "мертвая". В Wireworld это состояние именуется "хвостом электрона". Желтая клетка не мешает красным рождаться или выживать в соседних позициях, но предотвращает рождение живой клетки на ее месте. Такие правила называют Generations. В Golly это правило обозначается сегодня "03ajkr/2ak/3".

Б. Fireworld2:

Правила такие же, как в Fireworld, но клетка выживает еще и с 7 соседями. На работу компьютера это никак не влияет, однако позволяет сконструировать некоторые интересные вещи. Синие клетки "проводов" задаются раз и навсегда, работа автомата не может их никак изменить. Если пустая клетка окружена двумя или тремя клетками "провода", а также одной красной клеткой или двумя красными клетками, расположенными рядом по горизонтали или вертикали, на ее месте рождается красная клетка. Это позволяет легко "ловить" так называемые "фотоны" - "летящие" с максимальной скоростью объекты из двух живых и двух желтых клеток, подобные "космическим кораблям" в игре "Жизнь". В моем репозитории Fireworld собрано еще несколько десятков "фотонных" правил и сотни всяких паттернов.

Почему Лисп? Причем тут Ижора?

В некотором смысле, Лисп обладает таким же изяществом, как и клеточные автоматы: крайней простотой синтаксиса, позволяющей создавать сколь угодно сложные конструкции. Можно сказать, что синтаксиса как такового в классических диалектах Лиспа нет вообще: и данные, и программы представляют собой абстрактные деревья, которые на практике выглядят как заключенные в скобки списки элементов. Труда не составляет написать функцию, пишущую или изменяющую код, в том числе и свой собственный. В Common Lisp можно писать программу и тестировать ее "на лету" кусочек за кусочком. Не нужно каждый раз, как в C или Java, компилировать, а затем отдельно запускать: в Лиспе все это интегрировано. Можно даже во время работы программы ее кусками переписывать. Современные версии Лиспа компилируют сразу в машинный код, поэтому работают быстро, примерно как та же Java.

В 2017-2018 году, тоже на Лиспе, я написал виртуальную машину под названием Nutes, в честь советского троичного компьютера "Сетунь". Машина работает тоже на троичной логике и тоже всего с одной операцией симметричного двойного вычитания двух операндов: в одну ячейку записывается a-b, в другую b-a. Операция задана так, что любой код, инвертированный по знаку и записанный задом наперед, работает точно так же, как и оригинал. Поэтому Nutes - это Setun наоборот.

Опыты с той троичной машиной меня убедили, что одной операции вычитания действительно достаточно для практического синтеза всех прочих. Кстати, в одном из древнейших компьютеров, Manchester Baby, было тоже только вычитание. Он был разработан в 1948 году как чисто тестовая модель с крошечной памятью из 32 регистров, но уже позволял, например, вычислять последовательность простых чисел. Множество советских ЭВМ, да и не только советских, были названы в честь местностей, гор и рек, включая Днепр и Раздан. Сетунь - это нижний приток реки Москвы. Поэтому я решил так назвать свое сооружение: Ижора - левый приток Невы.

Краткое техническое описание

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

Сами сегменты гибкие и позволяют разные режимы адресации, от побитовых до 64-битных. Каждый сегмент содержит простой контроллер для записи и чтения. Обе операции совмещены: содержимое памяти переписывается логической операцией исключающего "или" (XOR). Таким образом, если послать на запись 0, сегмент просто выводит содержимое памяти, не меняя его, а если послать 0xFFFFFFFF, то содержимое инвертируется. Компьютер автоматически "ксорит" заранее данные операнда при записи, чтобы вписать в память нужную информацию.

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

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

Еще в схеме памяти присутствуют временные регистры для упаковки и распаковки битов. Внутри сегментов информация запакована вдвое плотнее рабочей частоты процессора и АЛУ (соответственно, 3 и 6 шагов автомата на бит). Упаковка позволяет намного уменьшить размер памяти и ускорить доступ.

Дисплей постоянно получает информацию из 4 сегментов, каждый пискель реагирует на нужный бит. В общей сложности, видеопамять занимает 1 килобайт и начинается с адреса 0x0400. Поскольку адресация 32-битная, 16 бит адреса позволяют адресовать как раз 256 килобайта. Для наиболее часто встречающихся данных и подпрограмм следует использовать нижние адреса, поскольку время обращения к памяти зависит от расстояния между процессором и данным сегментом (NUMA).

Команды одноадресные: старшие 16 бит расшифровываются как адрес условного перехода, младшие - как адрес операнда. Содержимое аккумулятора вычитается из содержимого операнда; результат записывается одновременно в аккумулятор и по адресу операнда. Если результат вычитания нулевой или отрицательный, вычисление переходит на адрес условного перехода; если положительный, счетчик команд увеличивается на единицу (инкрементируется).

Помимо самих сегментов памяти, весь обмен информацией идет по принципу, напоминающему модем: "пилотный" бит сообщает о том, что вслед за ним следуют n бит данных. Таким образом, 0 кодируется как 01, 1 - как 11, 2 - как 101, и так далее. Исключение составляют только T-триггеры, реагирующие на единичный сигнал. Последовательная модель обмена информацией намного упрощает схему: не нужно многобитовых шин. Важно еще заметить, что везде, кроме синхронизатора обмена данными с ОЗУ, используется асинхронный принцип: элементы компьютера содержат генераторы сигналов, которые включаются, как приходит предварительный бит, обрабатывают следующие за ним биты, прицепляют входной бит обратно к результату, если надо, а потом сами же выключаются. Поэтому не нужно каждый раз считать, как часто бывает в клеточных автоматах, когда именно в точности нужно послать тот или иной сигнал. Элементы сцепляются механически, в принципе можно создать и скрипты для автоматической генерации нужных "микросхем" на основе этого правила.

Практическое назначение

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

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

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

Если освещения достаточно, кубический блок почвы, имеющий по соседству блок зеленой лужайки, тоже прорастет травой. Блок воды понизит уровень и растечется на соседние участки, если перед ним не будет преград. При доступе к воде и солнечному свету урожай растет на один уровень с каждой итерацией временного цикла. Остывая, блок расплавленной лавы видоизменяется по простым правилам: лава (неподвижная) становится обсидианом, если верхний блок — вода; лава (текущая) становится камнем, если один из соседних блоков — вода.

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

перемещающаяся конфигурация из пяти клеток

Автомат становится машиной

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

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

Хищники и жертвы

Существуют клеточные автоматы, которые моделируют колебательные химические реакции и работу дыхательных устьиц растительного листа, турбулентные процессы и образование узора на раковинах моллюсков, динамику численности популяций травоядных и хищников. Правила просты. Особь может переместиться на случайную из клеток в окрестности Неймана. С определенной периодичностью она оставляет в исходной клетке потомка, с определенной — сама умирает от старости. Хищная особь может проглотить соседнее травоядное, а если не сделает этого в течение некоторого времени, то погибнет от голода. Такой клеточный автомат позволяет получить характерные S-образные кривые популяционного роста: численность хищников и травоядных выйдет на определенный уровень и будет колебаться около него. Всё как в жизни.

Эволюцию одномерного клеточного автомата

Наука | Научпоп

6.1K постов 68.7K подписчиков

Правила сообщества

ВНИМАНИЕ! В связи с новой волной пандемии и шумом вокруг вакцинации агрессивные антивакцинаторы банятся без предупреждения, а их особенно мракобесные комментарии — скрываются.

Основные условия публикации

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

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

- Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.

- Видеоматериалы должны иметь описание.

- Названия должны отражать суть исследования.

- Если пост содержит материал, оригинал которого написан или снят на иностранном языке, русская версия должна содержать все основные положения.

Не принимаются к публикации

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

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

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

Наказывается баном

- Оскорбления, выраженные лично пользователю или категории пользователей.

- Попытки использовать сообщество для рекламы.

- Многократные попытки публикации материалов, не удовлетворяющих правилам.

- Нарушение правил сайта в целом.

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

О, я "жизнь" ещё в школе писал на делфи, в своё время очень затянула эта тема

Golly, одна из самых популярных и продвинутых программ для симуляции клеточных автоматов:

Самый простой симулятор клеточных автоматов онлайн:

Трёхмерный онлайн симулятор клеточных автоматов с настраиваемыми правилами:

Комментарий удален. Причина: данный аккаунт был удалён

https://www.youtube.com/playlist?list=PLt5AfwLFPxWIL8XA1npoN.
Цикл - Видео интервью с создателем "Жизни", к сожалению на английском, но все же очень интересно)

Комментарий удален. Причина: данный аккаунт был удалён Очень много текста, но не понятно о чем пост. Прочитал 1/3, так не понял к чему разговор идет. Обзор майнкрафта?

Стрелы со взрывающимся наконечником: Рэмбо наших дней

Канал FullMag продемонстрировал, на что способна стрела с наконечником, начиненным взрывчатой смесью.

Лук и стрелы, начиненные взрывчаткой - грозное оружие Джона Рэмбо, героя знаменитой на весь мир серии фильмов о нелегкой судьбе ветерана Въетнамской войны. Канал FullMag решил проверить, возможно ли с помощью станка и реагентов изготовить это экзотическое оружие, а также выяснить, насколько разрушительным оно окажется в реальной жизни.

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

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

Мы теряем мозг: почему выживает глупейший

Происхождение человеческого мозга относится к главным загадкам эволюции и к одной из наиболее дискуссионных тем в биологической науке. Почему в какой-то момент времени эволюция поддержала развитие мозга у одной из ветвей приматов? Почему мозг так стремительно вырос за столь короткий период? И почему в течение 30 000 лет мозг homo sapiens постоянно теряет в весе?

АЛЬТРУИСТИЧЕСКИЙ ИНТЕЛЛЕКТ
Получается, что в стабильной социальной группе любых ранних и поздних гоминид действовал непреложный закон искусственного отбора. И именно в этом заключена квинтэссенция эволюции мозга человека.

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

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

Т. Тоффоли, Н. Марголус [Tof87]

Более или менее полная история возникновения и развития теории клеточных автоматов (КлА), а также обзор их возможных приложений требует отдельной и весьма объемистой статьи. Читателю, заинтересованному историей клеточных автоматов, можно предложить обзоры [Sar00], [Sut09] и книги [Bur70], [Mai07], [Mai12], [Neu66], [Tof87], [Scf08]. Здесь же мы ограничимся самыми общими историческими сведениями.

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

Приблизительно тогда же работавшие в Массачусетском технологическом институте (MIT) Норберт Винер (Norbert Wiener, 1894–1964) и Артуро Розенблют (Arturo Rosenblueth, 1900–1970) разработали клеточно-автоматную модель возбудимой среды для описания распространения импульсов в нервных узлах [Wie46].

Пятым "отцом" теории клеточных автоматов следует считать выдающегося немецкого инженера Конрада Цузе (Konrad Zuse, 1910–1995) – создателя первого в современном смысле программируемого компьютера Z3 (1941 г.) и первого языка программирования высокого уровня (1945 г.). Клеточные автоматы (под именем "вычисляющиеся пространства") рассматривались им в качестве возможной архитектуры вычислительных систем. В силу понятных политических и идеологических соображений Конрад Цузе не получил всемирной славы как "отец кибернетики", что, однако, не умаляет его заслуг.

В 1969 г. К. Цузе опубликовал книгу "Вычислимый космос" [Zus69], где выдвинул предположение, что по своей природе Вселенная является гигантским клеточным автоматом, а происходящие в ней физические процессы – суть производимые вычисления. В то время такой взгляд на Вселенную был шокирующим, тогда как сейчас идея вычисляющей саму себя Вселенной получила дальнейшее развитие [Ber09], [Fla98], [Ger89], [Ila02], [Kau95], [Mai12], [Pet03], [Scf08]. Книга К. Цузе положила начало так называемой цифровой физике – модному ныне направлению, относящемуся не столько к современной физике, сколько к философии.

Первая же фундаментальная книга, посвященная непосредственно клеточным автоматам, была создана по черновым записям и незавершенным статьям Дж. фон Неймана, законченным и переработанным его многолетним сотрудником А. Бёрксом (Burks A.W.), и вышла в свет в 1966 г. [Neu66].

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

Клеточные автоматы являются простыми моделями пространственно протяженных децентрализованных систем, состоящих из большого числа однородных составляющих компонент (клеток, ячеек), а внутреннее функционирование сводится к локальному взаимодействию между соседними компонентами [Cha97], [Cod68], [Del99], [Gan04], [Gri03], [Kar05], [Kar16], [Pre84], [Roz11], [Scf08], [Scf], [Tof90], [Tof87], [Viv03], [Бер93], [Куд90].

Классический клеточный автомат представляет собой упорядоченный набор ячеек памяти, образующих некоторую регулярную n-мерную решетку (на практике наибольшее распространение приобрели клеточные автоматы небольшой размерности – с одно- или двумерными решетками). Структура пространственной решетки зависит от формы входящих в нее ячеек. Так, например, в двумерном случае можно рассматривать ячейки прямоугольной, треугольной, шестиугольной формы (рис. 1); разумеется, возможны и иные варианты. Наибольшее внимание получили клеточные автоматы, в которых ячейки имеют квадратную форму, а сами решетки – прямоугольную.

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

Таким образом, для классических клеточных автоматов выполняются свойства:

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

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

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

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

В некоторых моделях решетка клеточного автомата считается бесконечной. Тогда считается, что все ячейки, кроме конечного числа, имеют в начальный момент "пустое" (нулевое) заполнение. Однако в большинстве приложений решетка клеточного автомата имеет конечные размеры. В этом случае возникает так называемая проблема краевых клеток – как задавать значения функции для ячеек, у которых отсутствует часть соседей. Чаще всего в соответствии со свойством однородности для разрешения проблемы краевых клеток противоположные края решетки клеточных автоматов отождествляются. Тогда одномерные клеточные автоматы можно представлять в виде набора ячеек памяти, объединенных в кольцо, решетку же двумерных автоматов принято отождествлять с тором (рис. 2). Реже вводится так называемая нулевая граница (Null-Boundary): значения для отсутствующих соседей полагаются равными нулю. Известны и другие варианты решения проблемы краевых клеток.

Автомат фон Неймана

Как указывалось выше, задача, которую в 40-х гг решал фон Нейман, состояла в исследовании возможности создания самовоспроизводящихся автоматов. В процессе решения он установил тесную связь самовоспроизводящихся автоматов с машиной Тьюринга – абстрактной логической конструкцией, предложенной Аланом Тьюрингом (Alan Mathison Turing, 1912–1954) в качестве идеализированной модели вычислителя. Машину Тьюринга можно представить себе в виде устройства, способного находиться в конечном числе внутренних состояний, снабженного бесконечной внешней памятью и набором инструкций, позволяющих в зависимости от данных, записанных во внешней памяти, менять свои внутренние состояния, переходить от одной ячейки памяти к другой, меняя при необходимости их содержание. Машины Тьюринга с разными наборами инструкций способны к выполнению различных задач. Достоинством машин Тьюринга является простота их устройства, однако они совершенно неэффективны даже для простейших вычислений и представляют интерес исключительно с теоретической точки зрения. Так, очень важным обстоятельством является тот теоретический факт, что существует машина Тьюринга, которая способна эмулировать работу любой другой машины Тьюринга, включая саму себя. Это так называемая универсальная машина Тьюринга, и она способна выполнять любые вычисления, которые выполнимы в принципе.

В 1952 г. фон Нейману удается решить проблему самовоспроизводящихся автоматов и построить соответствующий пример [Neu66]. Автомат фон Неймана представляет собой двумерный клеточный автомат с квадратными ячейками памяти, организованными в прямоугольную решетку, окрестность каждой клетки состоит из нее самой и четырех клеток, имеющих с ней общие границы (окрестность фон Неймана). Ячейка памяти, соответствующая клетке, может находиться в 29 возможных состояниях (включая состояние, называемое состоянием покоя). Двумерное пространство считается бесконечным, и все клетки, кроме конечного числа, первоначально находятся в "покоящемся" состоянии. Автомат задается определенным правилом взаимодействия клеток (локальной функцией связи) и конкретной исходной конфигурацией – начальным заполнением клеток.

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

С тех пор как фон Нейман впервые сконструировал свой автомат, многие другие исследователи либо улучшили его оригинальную конструкцию, либо разработали альтернативные конструкции. Так, в 1968 г. Кодд (Codd E.F.) упростил конструкцию фон Неймана (в которой ячейки принимают 29 возможных состояний) и построил КлА с теми же свойствами, в котором каждая ячейка может принимать восемь состояний [Cod68]. В 1971 г. Бэнкс (Banks E.R.) [Ban71] предложил аналогичный автомат, ячейки которого могли принимать четыре состояния (см. также работы Мура (Moore E.F.) [Moo62] и Бёркса [Bur70]). В 1984 г. Лэнгтон (Langton C.) опубликовал самовоспроизводящийся клеточный автомат, состоящий из 86 клеток, принимающих восемь состояний, который, правда, не проявляет свойства универсального вычислителя, как это делали автоматы фон Неймана и Кодда, а просто воспроизводит сам себя [Lan84].

Обзор пятидесятилетнего периода исследований по самовоспроизведению автоматов можно найти в статье Сиппера (Sipper М.) [Sip98], а также в более ранних книгах Бёркса и Кодда [Bur70], [Cod68].

Дальнейшее развитие

Начиная с 60-х гг. шло активное изучение клеточных автоматов как динамических систем. Обзор результатов, полученных в этом направлении, можно найти в работе Хедлунда (Hedlund G.A.) [Hed69].

В 70-е гг. широкую известность получил двумерный клеточный автомат, известный как игра "Жизнь" (Game of Life). Игра "Жизнь" была создана в 1970 г. Джоном Конвеем (Conway J.), математиком из Кембриджского университета, и получила широкую известность после публикаций статей Мартина Гарднера (Gardner M.) в журнале Scientific American [Gar70], [Gar71], см. также [Гар72]. Исходным мотивом для создания игры "Жизнь" была попытка построить математическую модель для изучения реальных процессов, происходящих при зарождении, развитии и гибели популяции живых организмов. В 1982 г. удалось получить конфигурацию клеток (состояние), способную к самовоспроизведению. Джон Конвей также доказал, что игра "Жизнь", как и самовоспроизводящийся автомат фон Неймана, имеет мощность универсальной машины Тьюринга: любая программа, которая может быть запущена на машине Тьюринга, может быть выполнена с помощью игры "Жизнь" с соответствующей первоначальной конфигурацией состояний. Эта первоначальная конфигурация кодирует и входные данные, и саму программу, которая будет обрабатывать входные данные.

Вообще исследованию вычислительных возможностей клеточных автоматов посвящен большой цикл работ (см., например, [Del99], [Mit98], [Mor89], [Oll08], [Roz11], [Tof77]). То, что клеточные автоматы могут моделировать машины Тьюринга и, следовательно, быть универсальными вычислителями, стало ясно после того, как фон Нейман построил свой автомат, который эмулировал работу универсальной машины Тьюринга. Спустя 20 лет Смит (Smith III, A.R.) доказал, что элементарный одномерный КлА с окрестностью радиуса 1 эквивалентен машине Тьюринга [Smi71], [Smi76]. Заметим, кстати, что моделирование работы машины Тьюринга клеточным автоматом немедленно влечет за собой доказательство неразрешимости ряда вопросов, связанных с поведением КлА.

Интерес к КлА еще больше усилился в начале 80-х гг. после того, как физик Стивен Вольфрам (Wolfram S.) опубликовал в 1983 г. первую из серии статей, исследующих различные классы клеточных автоматов [Wol83]. В следующие три года он публикует работы [Wol84a], [Wol84b], [Wol84c], [Wol85], [Wol86]), делающие его известным благодаря тем идеям, которые в них развиваются. В этих работах Вольфрам делает акцент на возможности использования клеточных автоматов в качестве математических моделей физических, биологических и вычислительных систем. Аргументами служат простота их конструкции, способность к сложному поведению, а также возможность точного математического анализа их поведения [Wol94]. В 2002 г. Вольфрам публикует монографию "Новый тип науки" (A New Kind of Science [Wol02]), 1280 страниц, где наглядно демонстрирует, что клеточные автоматы, будучи достаточно простой структурой, в процессе своего функционирования могут моделировать сложное поведение совокупности различных, порой весьма сложно устроенных взаимосвязанных однородных объектов.

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

International Conference on Cellular Automata for Research and Industry (ACRI) – с 1994 г.;
International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) – с 1995 г.;
International Conference "Advances in Information Technology" (IAIT);
International Conference "Network and Parallel Computing" (NPC);
International Conference on Unconventional Computation (UC).

Сейчас теория КлА является установившейся научной дисциплиной с многочисленными приложениями в очень многих областях науки ([Cha97], [Cho98], [Deu04], [Gayl96], [Gay98], [Gil99], [Gol99], [Hoe10], [Kru96], [Mai07], [OSu00], [Sce71], [Vic84], [Бер93]). Вольфрам упоминает более 10 тыс. статей, ссылающихся на его оригинальные работы по этому вопросу. Будучи математическим объектом, клеточные автоматы применимы не только в математике. Они играют важную роль в качестве моделей пространственно-распределенных динамических систем, поскольку изначально обладают рядом фундаментальных свойств, присущих физическому миру: параллелизмом, однородностью, локальностью взаимодействия. Другие свойства, такие как обратимость и законы сохранения, могут быть обеспечены надлежащим выбором локальных функций связи. Не удивительно, что КлА успешно применяются при моделировании сложных систем в биохимии и генетике, компьютерных технологиях и информатике, экономике и социологии. Это имитационное моделирование физических процессов и систем (моделирование течения жидкости, моделирование диффузионных процессов, модель Изинга), моделирование в теории хаоса и теории фракталов, биологические модели взаимодействующих клеточных систем, включая модели самовоспроизводства, моделирование городской транспортной сети и модели структурной лингвистики. Сюда же можно отнести исследования в области искусственного интеллекта, работы по созданию новых перспективных архитектур высокопроизводительной вычислительной техники, по использованию клеточных автоматов для обработки изображений и в теории помехоустойчивого кодирования. Применяются они и в криптографии.

Читайте также: