Комментарии 19
Правило 30 чрезвычайно просто:
Существует последовательность строк черных и белых клеток (ячеек) и, учитывая конкретную строку чёрно-белых ячеек, определяются цвета ячеек в строке ниже, рассматривая каждую ячейку в отдельности и ее смежных соседних ячеек, затем к ним применяется следующее простое правило подстановки...
Чрезвычайно просто?
Вы просто делаете подстановки на основе цветов ячеек на предыдущем ярусе. Это довольно просто. Что вас смущает?)
Смущает не само правило, а его формулировка :)
А вот в Вашем комментарии сформулировано куда проще (хоть и не совсем полно).
А вот в Вашем комментарии сформулировано куда проще (хоть и не совсем полно).
Меня, например, смущает то что математики вместо изложения фактов используют эти вот «очевидно», " просто" и т.п. Куда вот применить 1/0, которые написаны под паттернами ячеек, непонятно ни из вашего здесь текста, ни из описания Правила 30 в статье…
Куда решения засылать?
Уже есть?
www.rule30prize.org
www.rule30prize.org
Требует ли вычисление n-й ячейки центрального столбца хотя бы O(n) операций?
По сути вопрос — можно ли вычислить быстрее, чем за O(n)?
А силуэт человека на одном примере это так и получилось случайно?
Это парейдолия.
Мне кажется, что самые интересные вопросы Вольфрам упустил. Ну например:
— Почему именно правило 30? Что в нём такого, что выделяет его среди остальных?
— Можно же рассматривать не просто средний столбец, а каждый ряд эволюции как число, записанное в бинарном формате — получаем последовательность целых чисел. Какие у неё свойства? Можно ли по n-му числу найти предыдущее? Можно ли по n-му числу определить, существует ли предыдущее?
— Почему именно правило 30? Что в нём такого, что выделяет его среди остальных?
— Можно же рассматривать не просто средний столбец, а каждый ряд эволюции как число, записанное в бинарном формате — получаем последовательность целых чисел. Какие у неё свойства? Можно ли по n-му числу найти предыдущее? Можно ли по n-му числу определить, существует ли предыдущее?
— Почему именно правило 30?
Правило 30 и эквивалентные ему: 86, 135 и 149. Эквивалентные — это инвертированные и зеркальные.
Еще одно правило с хаотичным средним столбцом — правило 45 и эквивалетные ему правила: 75, 89 и 101.
Можно ли по n-му числу найти предыдущее?
Одномерные клеточные автоматы первого порядка — необратимы. Для следующего состояния существует несколько возможных предыдущих.
Есть еще один интересный вопрос. Если рассматривать автомат в кольце (левая граница соединена с правой) — каждый столбец становится периодическим. Вопрос:
— Как длина периода зависит от размеров кольца?
В качестве примера, кольцо с десятью клетками:
Длина периода — 15.
Для первых 12-ти колец, длина периода: 0, 0, 0, 8, 5, 0, 4, 40, 72, 15, 154, 102
Для следующего состояния существует несколько возможных предыдущих.Для любого ли? В игре «Жизнь» есть понятие "Сад Эдема" — состояние, недостижимое эволюцией. Как много здесь таких?
Все возможные состояния автомата можно представить в виде ориентированного графа, ребра которого — переход из одного состояния в другое. Если у каждой вершины не больше трех ребер (два входа, один выход или один вход и один выход) — тогда количество Садов Эдема совпадет с количеством вершин, у которых три ребра.
Для небольших колец, можно перебрать все возможные начальные состояния автомата, далее записать для них следующее состояние и тем самым отсеять те состояния, для которых не существует предыдущего состояния (Сады Эдема).
Результат:
Для кольца из 10-ти клеток существует 101 Сад Эдема.
Можно отметить все Сады Эдема для автоматов с правилами от 0 до 255 в кольце из 9-ти клеток (чтобы картинка влезла в комментарий). Далее сложить их стопочкой:
По оси X — все комбинации автомата с правилом, отмеченным по оси Y. Белый пиксель — Сад Эдема.
На второй картинке, белыми пикселями отмечены состояния, для которых существует только одно предыдущее состояние:
Для небольших колец, можно перебрать все возможные начальные состояния автомата, далее записать для них следующее состояние и тем самым отсеять те состояния, для которых не существует предыдущего состояния (Сады Эдема).
Говнокод:
var rule=[0,0,0,1,1,1,1,0];
var sizex=9;
var pow=2**sizex;
var arr=[];
for(var i=0;i<pow;i++) arr[i]=0;
var b, temp, q;
for(var i=0;i<pow;i++){
b=[];
var ii=i.toString(2);
for(var j=ii.length;j<sizex;j++) ii='0'+ii;
for(var j=0;j<sizex;j++) b[j]=ii[j]*1;
temp=[];
for(var x=0;x<sizex;x++){
xm=x-1;
if(xm<0) xm=sizex+xm;
xp=x+1;
if(xp>=sizex) xp=xp-sizex;
q=''+b[xm]+b[x]+b[xp];
q=parseInt(q, 2);
temp[x]=rule[q];
}
b=temp;
q=b[0];
for(var j=1;j<sizex;j++) q=(q<<1)+b[j];
arr[q]++;
}
console.log(arr.join(','));
var s0=0;
var s1=0;
var s2=0;
for(var i=0;i<pow;i++){
if(arr[i]==0) s0++;
if(arr[i]==1) s1++;
if(arr[i]>=2) s2++;
}
console.log(s0, s1, s2);Результат:
Для кольца из 10-ти клеток существует 101 Сад Эдема.
Можно отметить все Сады Эдема для автоматов с правилами от 0 до 255 в кольце из 9-ти клеток (чтобы картинка влезла в комментарий). Далее сложить их стопочкой:
По оси X — все комбинации автомата с правилом, отмеченным по оси Y. Белый пиксель — Сад Эдема.
На второй картинке, белыми пикселями отмечены состояния, для которых существует только одно предыдущее состояние:
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
30.000$ за решение задач о Правиле 30 для клеточных автоматов — конкурс от Стивена Вольфрама