Автомат Файра – Уорбертона

Улама -Уорбертона Клеточный автомат (UWCA) представляет собой двумерный фрактальный узор, который растет на регулярной сетке ячеек, состоящих из квадратов. Начиная с одного квадрата, изначально включенного, а всех остальных выключенных, последующие итерации генерируются путем включения всех квадратов, которые имеют ровно один общий край с включенным квадратом. Это район фон Неймана . Автомат назван в честь польско-американского математика и учёного Станислава Улама. и шотландский инженер, изобретатель и математик-любитель Майк Уорбертон.

Первые двадцать итераций клеточного автомата Улама-Уорбертона

Свойства и отношения

UWCA — это двумерный внешний тоталистический клеточный автомат с 5 соседями, использующий правило 686.

Обозначается количество ячеек, включенных на каждой итерации. $u(n),$ с явной формулой:

$u(0)=0,u(1)=1,$ и для $n\geq 2$

$u(n)=4\cdot 3^{wt(n-1)-1}$

где $wt(n)$ — это весовая функция Хэмминга , которая подсчитывает количество единиц в двоичном разложении числа. $n$

$wt(n)=n-\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{2^{k}}}\right\rfloor$

Минимальная верхняя граница суммирования для $k$ таков, что $2^{k}\geq n$

Общее количество включенных ячеек обозначается $U(n)$

$U(n)=\sum _{i\mathop {=} 0}^{n}u(i)={\frac {4}{3}}\sum _{i\mathop {=} 0}^{n-1}3^{wt(i)}-{\frac {1}{3}}$

Таблица wt(n) , u(n) и U(n)

В таблице показано, что различные входные данные для $wt(n)$ может привести к тому же результату.

Это сюръективное свойство вытекает из простого правила роста: новая клетка рождается, если она разделяет только одно ребро с существующей ON-клеткой; процесс выглядит беспорядочным и моделируется функциями, включающими $wt(n)$ но внутри хаоса есть закономерность.

$n$	$wt(n)$	$u(n)$	$U(n)$	$n$	$wt(n)$	$u(n)$	$U(n)$
0	0	0	0	10	2	12	101
1	1	1	1	11	3	12	113
2	1	4	5	12	2	36	149
3	2	4	9	13	3	12	161
4	1	12	21	14	3	36	197
5	2	4	25	15	4	36	233
6	2	12	37	16	1	108	341
7	3	12	49	17	2	4	345
8	1	36	85	18	2	12	357
9	2	4	89	19	3	12	369

$U(n)$ - это OEIS последовательность A147562 и $u(n)$ это OEIS последовательность A147582

Подсчет ячеек с квадратиками

Общее количество включенных ячеек $U(n)$ в КА Улама – Уорбертона и квадратичных уравнениях $U_{1},U_{3}$ и $U_{17}$

Для всех целочисленных последовательностей вида $n_{m}=m\cdot 2^{k}$ где $m\geq 1$ и $k\geq 0$

Позволять

$a_{m}=\sum _{i\mathop {=} 0}^{m-1}3^{wt(i)}$

( $a_{m}$ это OEIS последовательность A130665 )

Тогда общее количество включенных ячеек в целочисленной последовательности $n_{m}$ дается

$U_{m}(n_{m})={\frac {a_{m}}{m^{2}}}{\frac {4}{3}}n_{m}^{2}-{\frac {1}{3}}$

Или с точки зрения $k$ у нас есть

$U_{m}(k)=a_{m}{\frac {4}{3}}2^{2k}-{\frac {1}{3}}$

Таблица целочисленных последовательностей n _m и U _m

$k$	$n_{1}$	$U_{1}$	$n_{3}$	$U_{3}$	$n_{5}$	$U_{5}$	$n_{7}$	$U_{7}$
0	1	1	3	9	5	25	7	49
1	2	5	6	37	10	101	14	197
2	4	21	12	149	20	405	28	789
3	8	85	24	597	40	1,621	56	3,157
4	16	341	48	2,389	80	6,485	112	12,629
5	32	1,365	96	9,557	160	25,941	224	50,517

Верхняя и нижняя границы

Общее количество ON-клеток в клеточном автомате Улама – Уорбертона

$U(n)$ имеет фрактальное поведение с резкой верхней границей для $n\geq 1$ данный

$U_{\text{sub}}(n)={\frac {4}{3}}n^{2}-{\frac {1}{3}}$

Верхняя граница касается только контактов $U(n)$ в точках «паводка», когда $n=2^{k}$.

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

Верхняя и нижняя границы $U(n)/n^{2}$

Ограничьте верхнее и ограничьте худшее

У нас есть

$0.9026116569...=\liminf _{n\to \infty }{\frac {U(n)}{n^{2}}}<\limsup _{n\to \infty }{\frac {U(n)}{n^{2}}}={\frac {4}{3}}$

Нижний предел был получен Робертом Прайсом ( OEIS последовательность A261313 ), расчет занял несколько недель и, как полагают, вдвое превышает нижний предел ${\frac {T(n)}{n^{2}}}$ где $T(n)$ общее количество зубочисток в последовательности зубочисток до поколения $n$

Отношение к

Хекс-Улама-Уорбертона Клеточный автомат - поколение 11

Шестиугольный УЗКА

Гексагональный клеточный автомат Улама-Уарбертона (Hex-UWCA) представляет собой двумерный фрактальный узор, который растет на регулярной сетке ячеек, состоящих из шестиугольников. Применяется то же правило роста для UWCA, и через несколько поколений шаблон возвращается к шестиугольнику. $n=2^{k}$, когда первый шестиугольник рассматривается как поколение $1$.UWCA имеет две линии отражения, которые проходят через углы исходной ячейки, делящей квадрат на четыре квадранта, аналогично Hex-UWCA имеет три линии отражения, делящие шестиугольник на шесть секций, и правило роста соответствует симметрии. Клетки, центры которых лежат на линии отражательной симметрии, никогда не рождаются.

Паттерн Hex-UWCA можно изучить здесь .

Треугольник Серпинского

Основная статья: треугольник Серпинского

Треугольник Серпинского - поколение 16.

Треугольник Серпинского появляется на итальянских напольных мозаиках XIII века. Вацлав Серпинский описал треугольник в 1915 году.

Если мы рассмотрим рост треугольника, где каждая строка соответствует поколению, а верхняя строка — поколению. $1$ представляет собой одиночный треугольник, затем, как и UWCA и Hex-UWCA, он возвращается к своей исходной форме через несколько поколений. $n=2^{k}.$

Последовательность зубочисток

Основная статья: Последовательность зубочисток

Последовательность зубочисток - поколение 13

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

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

Последовательность зубочисток возвращается к своей базовой повернутой форме буквы «H» через несколько поколений. $n=2^{k}$ где $k\geq 1$

Последовательность зубочисток и различные последовательности, подобные зубочисткам, можно изучить здесь .

Комбинаторная теория игр

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

История

Истоки автоматов восходят к разговору Улама со Станиславом Мазуром в кофейне во Львове, Польша, когда Уламу было двадцать лет в 1929 году. Улам работал с Джоном фон Нейманом в годы войны, когда они стали хорошими друзьями и обсуждали клеточные автоматы. Фон Нейман использовал эти идеи в своей концепции универсального конструктора и цифрового компьютера. Улам сосредоточился на биологических и «кристаллоподобных» закономерностях, опубликовав в 1962 году эскиз роста квадратной клеточной структуры с использованием простого правила. Майк Уорбертон — математик-любитель, работающий в области вероятностной теории чисел, получивший образование в школе Джорджа Хериота в Эдинбурге. Курсовая работа его сына по математике на выпускном экзамене в школе включала исследование роста равносторонних треугольников или квадратов на евклидовой плоскости с использованием правила: новое поколение рождается тогда и только тогда, когда оно соединено с предыдущим только одним ребром. Эта курсовая работа завершилась рекурсивной формулой для количества ON-клеток, рожденных в каждом поколении. Позже Уорбертон нашел формулу точной верхней границы, которую он написал в заметке в журнале M500 Открытого университета в 2002 году. Дэвид Сингмастер прочитал статью, проанализировал структуру и в своей статье 2003 года назвал объект клеточным автоматом Улама-Уорбертона. С тех пор он породил множество целочисленных последовательностей.

Внешние ссылки

• Изучите UWCA, Hex-UWCA и связанные с ними анимации целочисленных последовательностей.
• Нил Слоан: Потрясающие узоры из зубочисток — Numberphile. (Начало UWCA в 8:20)