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

Книга американских специалистов, излагающая теорию клеточных автоматов Дж. фон Неймана и описание машины клеточных автоматов на базе персональной ЭВМ (ШМ-РС). Такие машины могут использоваться для моделирования физических процессов, при решении комбинаторных и вычислительных задач, задач прикладной кибернетики. Изложение отличается простотой и ясностью и рассчитано на первоначальное ознакомление с предметом. [c.4]

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

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

Итак, эта книга является вводным руководством по гармонии и оркестровке для композиторов миров на клеточном автомате. [c.7]

В этой книге мы исследуем выразительные возможности (в плане синтеза систем) конкретного набора средств, а именно законов, структур и явлений, поддерживаемых клеточными автоматами, с тем чтобы эти системы стали реально доступными для экспериментирования посредством использования машины клеточных автоматов с адекватными характеристиками. [c.8]

Данная глава является введением в клеточные автоматы и включает краткие исторические замечания и ссылки. [c.8]

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

Как отмечено во введении, клеточный автомат может мыслиться как стилизованный мир. Пространство представлено равномерной сеткой, каждая ячейка которой, или клетка, содержит несколько битов данных время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет свое новое со- [c.8]

Прежде чем поручать машине управлять миром на клеточном автомате, необходимо иметь ясное представление о том, как то же задание могло бы быть выполнено вручную. [c.9]

С другой стороны, структура клеточного автомата идеально пригодна для реализации на ЭВМ, обладающей высокой степенью параллелизма, локальными и единообразными взаимо- [c.11]

И в самом деле, машины клеточных автоматов, имеющие размеры, скорость и гибкость, подходящие для общего экспериментирования, и умеренную стоимость, стали в последнее время доступны широким научным кругам (см. гл. 2). Эти машины представляют собой лабораторные установки, в которых идеи, приведенные в этой книге, могут быть испытаны в конкретной форме и применены к синтезу огромного многообразия систем. [c.12]

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

Клеточные автоматы ввел в конце сороковых годов Дж. фон Нейман, следуя идее С. Улама [64 ], для того чтобы обеспечить более реалистические модели поведения сложных, пространственно протяженных систем [68] в клеточном авто- [c.12]

Тем временем профессиональные математики обратили внимание на итерационные преобразования, действующие на пространственно распределенные структуры с дискретным набором состояний [25], - опять-таки клеточные автоматы Недостаточность общения и единой терминологии вели к значительному дублированию работ. Важные характерные особенности клеточных автоматов, доказанные Ричардсоном [48 ] на [c.13]

Этот подход был использован для того, чтобы обеспечить предельно простые модели обычных дифференциальных уравнений физики, таких как уравнение теплопроводности, волновое уравнение [61] и уравнение Навье-Стокса [23, 18], которые могут мыслиться как предельные случаи исключительно простых процессов комбинаторной динамики. В частности, клеточные автоматы были созданы для того, чтобы дать точные модели динамики жидкостей, которые не только будят мысль, но и конкурентоспособны, по крайней мере в некоторых обстоятельствах, с точки зрения их вычислительной эффективности. [c.15]

В этой книге стандартная среда моделирования, которая будет постепенно вводиться, начиная с настоящей главы, представлена конкретной имеющейся в продаже машиной клеточных автоматов, а именно САМ-6. Основная причина этого выбора состоит в том, что аппаратные средства и программное обеспечение этой машины доступны в настоящее время широкому кругу пользователей. [c.16]

Однако, если вы хотите уметь добавлять новые элементы к своему набору миров, вам для описания правил клеточного автомата потребуется язык, удобный пользователю и понятный машине. Этот процесс создания правил формально вводится в гл. 4, а полностью разрабатывается в последующих главах. [c.20]

САМ-6 является машиной клеточных автоматов, предназначенной для того, чтобы служить лабораторией экспериментатора, средством сообщения результатов и средой для интерактивной демонстрации в режиме реального времени. [c.16]

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

При написании правила клеточного автомата мы определяем, как на каждую клетку повлияют некоторые соседние клетки. Точнее, мы определяем, как на каждый из четырех битов, составляющих клетку, повлияют несколько соседних битов некоторые из них могут располагаться на той же самой плоскости битов, а некоторые на остальных трех плоскостях. Насколько далеко может распространяться это влияние [c.19]

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

Кривые пространственные элементы. Мембраны, мицеллы, спирали. Более сложные высокоорганизованные структуры, получаемые изгибом низких структур Одно из многих квазиэквивалент-ных состояний метастабильная регистрация произвольной информации (учет пути) прогрессивное выделение и специализация информационной структуры Конечное число элементов Кластеры кристаллоиды Агрегирование путем включения других компонент ( кристалла-за -фермент). Информационноуправляемое агрегирование. Иерархическое агрегирование Иерархия уровней организации. Малая ширина каждого уровня Повторение по программе. Клеточные автоматы [c.434]

Идея клеточных автоматов была сформулирована независимо Дж. фон Нейманом и К. Цусе в конце 40-х годов. Оба рассматривали их как универсальную вычислительную среду для построения алгоритмов, эквивалентную по своим выразительным возможностям машине Тькч)инга. Эта идея породила волну многочисленных теоретических и прикладных исследований. Прежде всего это касается работ по созданию формальных моделей и алгоритмов на основе локальных взаимодействий, универсальных клеточных процессоров и нейрокомпьютеров. Начиная с 1976 г. в Берлине регулярно проводятся международные конференции по параллельной обработке информации на клеточных автоматах. Современный интерес к ним усиливается возможностью реализации на СБИС с высокой степенью интеграции, перспективами обработки информации на молекулярном уровне. [c.5]

Это в сущности все, что нужно для клеточного автомата. Измените начальные условия, и вы получите несколько иную историю. Измените рецепт, и вы получите ноьое множество Тчинамических законов - новый мир. Вы можете использовать сетку иной формы (скажем, гексагональную), или, может быть, трехмерную. Рецепт может относиться к окрестности с другой формой и размером, чем окрестность 3x3, и может включать чернила более чем одного цвета однако как число соседей, так и число цветов (т. е. число возможных состояний клетки) должны быть конечными, потому что мы хотим, чтобы обновление состояния клетки требовало конечного числа операций. [c.10]

Давайте прямо признаем, что общность и гибкость клеточноавтоматного подхода к синтезу систем достигаются не бесплатно. Вместо небольшого число переменных, взаимодействие которых может быть задано произвольным образом, клеточный автомат использует много переменных (одна на клетку), но требует, чтобы они взаимодействовали только локально и единообразно. [c.11]

В связи с этим обычные компьютеры здесь мало пригодны. Моделирование события в клеточном автомате может потребовать около тридцати мапшнных операций, содержащих каждая несколько машинных циклов, скажем 10 мс на быстродействующем компьютере. Для того чтобы вычислить 10 событий, при таком подходе потребовалось бы несколько лет [c.11]

Термин не-фон-иеймаиовская архитектура часто используется для различения параллельных компьютеров этого вида и более привычных последовательных компьютеров. Необходимо, однако, заметить, что теория клеточных автоматов была введена самим фон Нейманом примерно в то же время, ко1да он работал над конструированием универсальных электронных компьютеров. [c.12]

Хотя фон Нейман был ведущим физиком в такой же степени, как и математиком, точные физические рассуждения отсутствуют в его работе по клеточным автоматам его больше интересовало редукционистское объяснение определенных аспектов биологии. Действительно, механизмы, которые он предложил для получения самовоспроизводящихся структур на клеточном автомате, сильно напоминают открытые в следующем десятилетии механизмы, которые на самом деле наблюдаемы в биологических системах. [c.13]

В конце войны, коща фон Нейман создавал один из первых электронных компьютеров, немецкий инженер К. Цусе прятался от нацистов в Австрии там, в уединении на вершине горы, у него возникли наброски многих идей параллельной обработки, включая языки программирования высокого уровня и вычисляющие пространства [76] - т. е. клеточные автоматы. К. Цусе особенно интересовался численными моделями в механике, и физические мотивы играли основную роль в его работе. К несчастью, исторические обстоятельства воспрепятствовали более широкой известности его работ в то время. [c.13]

Работа фон Неймана по самовоспроизводящимся автоматам была завершена и описана А. Берксом [68], который сохранил активный интерес к этой области на протяжении нескольких последующих лет. Его Очерки по клеточным автоматам [10] являются хорошим введением в вопросы о клеточных автоматах, которые ставились в годы формирования вычислительных наук. В той же среде, т. е. в группе компьютерной логики Университета шт. Мичиган, Дж. Голланд приступил к использованию клеточных автоматов в задачах адаптации и оптимизации [27 ] был разработан программный имитатор универсальных клеточных автоматов общего назначения. Месяцы работы с этим имитатором (см. [55]) убедили одного из авторов (Тоффоли) в необходимости более непосредственной и эффективной аппаратной реализации - машины клеточных автоматов. [c.13]

Игра Джона Конвея жизнь , представленная широкой общественности ведущим рубрику математических игр и развлечений в журнале Сайентифик Америкен М. Гарднером [20], некоторое время пользовалась популярностью, близкой к культу, и сделала выражение клеточные автоматы частью бытового жаргона целого поколения молодых ученых. [c.14]

Мы интересуемся клеточными автоматами прежде всего как автономными системами, т. е. как мирами, замкнутыми в себе, а не как трансдьюсерами (системы, которые порождают постоянный выходной поток информации в ответ на постоянный входной поток). По этой причине мы совсем не будем касаться обширной литературы, посвященной итерационно-цепным массивам в контексте арифметических вычислений, обработки изображений и распознавания образов. В качестве введения в эти области и руководства к машинам, разработанным для этих более специализированных приложений, может быть использована книга Престона и Даффа Современные клеточные автоматы [46 ]. [c.14]

Вопрос о том, могут ли клеточные автоматы моделировать непосредственно законы физики, а не только общие феноменологические аспекты нашего мира, был вновь поставлен Э. Фредкином, который проявлял активность и в более традиционных областях исследований клеточных автоматов (см. [3]), и Т. Тоффоли [55]. Основной целью настоящего исследования является рмулировка компьютероподобных моделей в физике, сохраняющих информацию, а значит и одно из наиболее фундаментальных свойств микроскопической физики, а именно обратимость [17, 58, 35]. [c.14]

Бурно развивающийся раздел теории динамических систем изучает возникновение хорошо описанных коллективных явлений - упорядочение, турбулентность, хаос, нарушение симметрии, фрактальность и др. в системах, состоящих из большого числа частиц, взаимодействующих друг с другом нелинейно цели исследований и их математический аппарат здесь больше похожи на присущие макроскопической физике и материаловедению. Клеточные автоматы обеспечивают богатую и непрерывно растущую коллекцию типичных моделей, в которых эти явления могут быть изучены относительно легко [66, 15, 5]. Систематическое использование клеточных автоматов в этом контексте энергично проводилось С. Вольфрамом [70-73, 43] его сборник статей по теории и применениям клеточных автоматов [74] содержит обширную библиографию. [c.15]

Итак, клеточные автоматы, по-видимому, нашли устойчивое (и все более важное) применение в качестве концептуальных и практических моделей пространственнораспределенных динамических систем, для которых физические системы являются первыми и наиболее важными прототипами. [c.15]

Физически САМ-6 состоит из модуля, который вставляется в один разъем IBM-P (XT, АТ или совместимых с ними моделей), и управляющего программного обеспечения, работающего в среде P -D0S2. В то время как этот легко доступный головной компьютер обеспечивает размещение, экранирование, электропитание, дисковую память, монитор и стандартную операционную среду, вся действительная работа по моделированию клеточных автоматов с очень высокой скоростью совершается самим модулем с быстродействием, сравнимым (для этого частного приложения) с быстродействием RAY-1. [c.17]

Несколько модулей САМ могут быть объединены так, чтобы получить больший клеточный автомат. В этом случае склеивание краев соответствующим образом модифищ1руется, так что обертывание правильно применяется и к большему листу. [c.19]

Справочник химика 21

Химия и химическая технология