Наибольшую популярность получил клеточный автомат в виде игры "Жизнь", придуманной английским математиком Джоном Конвеем в 1970 г.
Если рядом с пустой клеткой есть ровно три непустых (живых) клетки, то в данной клетке зарождается жизнь. Если непустых соседей меньше двух или больше трех, то клетка умирает (помечается как пустая).
Но вообще клеточные автоматы прекрасно подходят для моделирования самых разных процессов. Это может быть распространение тепла и всевозможных волн, хоть от взрыва, хоть на море, в проводах, в эфире.
Например, можно следующим образом смоделировать распространение тепла в стержне, одна половина которого холодная, а другая горячая. Представим стержень в виде последовательного набора клеток. Клеткам, соответствующим холодной части стержня, припишем по нулю, а клеткам горячей части - по единичке.
На первом шаге для каждой клетки вычислим среднее арифметическое от трех чисел: значения в самой клетке и в двух соседних. Тогда на краях стержня значения не изменятся, а в середке образуются: 1/3 и 2/3.
На следующем шаге аналогичное вычисление среднего арифметического даст в середке уже 4 числа, отличных от 0 и от 1. Это: 1/9, 1/3, 2/3, 8/9. И т.д. Таким образом холодная часть стержня начинает постепенно нагреваться, а горячая - охлаждаться.
Преимущество клеточных автоматов состоит в том, что они не требуют огромных формул и быстро приводят к численным результатам.
Как это ни парадоксально, но в математической энциклопедии вообще нет определения клеточного автомата. По разной литературе разбросаны определения, охватывающие лишь частные случаи. Трудность состоит в том, что всевозможные обобщения, идущие от вполне наглядных клеточных автоматов на плоскости, быстро уходят в такие дебри, которые сложно отличить от вычислений вообще.
Например, после плоских клеточных автоматов естественно напрашиваются и широко используются клеточные автоматы в пространстве. Но чем хуже в качестве пространства многочисленные алгебраические и топологические объекты? Поэтому даже опытный специалист затруднится отнести те или иные вычисления к клеточным автоматам.
В свое время я предложил математически точное определение клеточного автомата, которое отражает широчайшую применимость клеточных автоматов и одновременно все-таки ставит четкие границы этому понятию. Когда даже в науку потоком хлынула халтура, а в Интернет нередко просто галлюцинации, то я думаю, что нелишне будет напомнить о существовании надежных точных знаний.
Впрочем, дальнейшее неспециалистам можно не читать, все популярное уже сказано мною выше.
Клеточный автомат - это
1) отображение G непустого подмножества N заданного множества M в k-ую степень M
и
2) отображение F k-мерного вещественного пространства в одномерное вещественное.
Перед очередной итерацией имеется вещественная функция f на M, после итерации появляется функция h на M. Для этого по каждому x из N берется G(x), т.е. упорядоченный набор элементов x1,x2,...,xk из M. Затем с помощью f формируется набор ( f(x1), f(x2), ... , f(xk) ) , который является элементом k-мерного вещественного пространства. И, наконец, F переводит его в вещественное число h(x).
Пример. Множество M={a,b,c,d,e}, подмножество N={b,c,d}, степень k=2, отображение G переводит элемент b в пару (a,c), c - (b,d), d - (c,e). отображение F(u,v)=(u+v)/2. Тогда h(b)=(f(a)+f(c)/2, h(c)=(f(b)+f(c))/2, h(d)=(f(c)+f(e))/2. Если представить a,b,c,d,e как точки, лежащие на прямой в такой же последовательности, то на очередной итерации значение в каждой точке (кроме крайних) заменяется на полусумму соседних.
Предложенное определение не привязано к плоскости (и клеткам в чистом виде) или трехмерному пространству. В качестве множества M может фигурировать граф, топологическое пространство и вообще любое множество со своей внутренней структурой или без таковой. Отображение G может использовать внутреннюю структуру M (например, брать некую окрестность для каждой точки из M), а может и не использовать, будучи просто задано в форме списка.
В определении не требуется конечность множества M, теоретически можно вычислять h(x) и на бесконечном множестве.
Определение не привязано к каким-либо краевым условиям, но фактически M\N можно использовать для краевых точек, в которых значения меняются по особым правилам (либо не меняются). В определении эти правила никак не регламентируются, что отвечает широкому спектру реальных ситуаций. Если в двумерном случае значения на границе пересчитываются, то для множества M\N можно аналогично ввести отображения по образцу G и F, но при меньшей степени, чем k.
В определении для F за основу взяты вещественные числа, чтобы не усложнять суть определения. Но оно аналогично может быть сформулировано для комплексных или целых чисел, а также для любых специальных наборов значений, например, векторов скоростей или 64-мерного вектора, задающего положение фигур на шахматной доске.
Определение далеко отходит от ходовых представлений о неизменных клетках и статичных соседях (хотя охватывает, конечно, и этот случай). Соседи здесь назначаются номинально и физически могут быть весьма подвижны. Например, в задаче о движении нескольких тел под действием гравитации у каждого тела все остальные являются соседями, а значения F есть координаты в пространстве и векторы скоростей. По сути клеточный автомат смыкается с игровой ситуацией, когда несколько участников действуют по определенным правилам, руководствуясь некой стратегией, возможно, с элементом случайности.
Таким образом, в отличие от других довольно многословных определений, здесь в наиболее абстрактной форме выделяются существенные части клеточного автомата. Во-первых, это отображение G, которое фактически задает некие отношения между элементами множества M, определяя для каждого элемента x из M упорядоченное множество из k его "родственников". Во-вторых, это отображение F , которое задает правило вычисления нового значения на x по значениям на "родственниках". Это, так сказать, строение механизма. И отдельно, исходя из строения, описан один шаг работы этого механизма вне зависимости от того, есть или нет понятие времени, и сколько этот механизм будет работать.
Авторская публикация. Свидетельство о публикации в СМИ № J108-47740.
Обсуждения Клеточные автоматы
Валерий, это сообщение поступило к Вам с Луны, или прямо от Платона и компании, или с самых дремучих уровней инфополя?
Всё производство, энергетические системы, транспорт и в значительной мере люди уже давненько находятся под неусыпным контролем матриц, автоматов и компьютеров, потому что человеку не по силам операции, на которые отводятся микроскопические доли секунды и просто не хватит никакого мозга, чтобы хранить всю оперативную информацию.
Именно человек не справляется с решением элементарных шахматных и шашечных задачек и практически все люди - с доказательством теорем. А машины щелкают их, как орехи!
Поэтому прошу от Вас примеров, иллюстрирующих Ваше неожиданное сообщение.
систем просто не справятся с решением элементарных задачек и теорем.
Во всяком случае, я оперативно могу объяснить каждое слово в своей статье про истину, как и в других статьях.
Вообще, я встречал немало сюрпризов о себе в Интернете, да и в др. местах. Даже коллеги по работе беззастенчиво публиковали мою продукцию под своими именами.
В данном случае саму статью я сочинил только вчера, так что она никак не могла раньше быть в Интернете. А собственно определение КА я распространял среди узких специалистов, но оно точно мое. Спецы по КА - технари и до таких математических абстракций не доходят.
Про понятие информации уже много раз я тут всем напоминал, что у меня здесь есть статья с математически точным определением информации. Но кому приятно ничего не знать (или надеть сандалии на глаза, как сделал один наш коллега), те и далее будут упорно твердить, что ничего нет.