2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Математика ищется (автоматы)
Сообщение15.01.2009, 21:05 
Аватара пользователя
Не знаю как подступиться к одной задачке - может кто что подскажет...

Будем рассматривать бесконечное поле $P$ клеточного автомата (cellular automata), каждая клетка которого может принимать значения из некоторого множества $V$. Пусть у нас задан порядок обхода клеток в любой произвольно выбираемой области этого поля. Введём операцию "$+$" конкатенации (объединения) значений соседних клеток и построим множество $S$ всевозможных последовательностей из $V$ (при этом $V \subset S$). На $S$ зададим некоторую функцию переходов $g: S \to S$.

Будем теперь рассматривать произвольную область поля $A$, пусть её начальное состояние есть $a_0 \in S$ а состояние остальной части поля $B = P \setminus A$ есть $b_0 \in S$. Пусть после итерации состояния областей получат значения $a_1$ и $b_1$ соответственно. Отсюда можно видеть, что последовательности $a_0$ можно сопоставить некоторую функцию на $S$: $b_{n+1} = a_0(b_n)$.

Если при тех же начальных условиях мы будем рассматривать другую область того же поля, то в той же итерации будет вычислено значение другой функции, скажем $c_{n+1} = d_0(c_n)$, то есть порядок обхода наряду с функцией переходов определяет некоторое множество функций $F: S \to S$.

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

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

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group