Четыре оттенка нуля или 5-ти битное кодирование в ЭКА

[Soul Friend]

Стивен Вольфрам анонсировал приз для правила 30: https://blog.wolfram.com/2019/10/01/announcing-the-rule-30-prizes/
Решил попробовать поискать закономерности в последовательности A051023, пытался установить связи между нулями и единицами используя метод декомпозиции : Пяти-битное кодирование в элементарных клеточных автоматах. Так и не смог доказать непериодичность этой последовательности, делюсь мыслями, может у кого-то получится продвинуть идею дальше. В книге ''New kind of Science" , демонстрирующая сорокалетний труд автора, ничего схожего не нашел. Но сама книга, с третьей главы, где начинаются картинки, понравилась. Но здесь, на форму, кажется книга не всем пришлась по душе : «Новый вид науки Вольфрама»

[arseniiv]

И не только здесь

-- Чт ноя 14, 2019 02:34:23 --

Ну сами-то вопросы разумны, хотя я не имею понятия, сколько стоят ответы на них.

Для тех, кто не хочет открывать ссылку. Берётся линейный клеточный автомат с правилом 30:

сосед старое сосед → новое
000 → 0
001 → 1
010 → 1
011 → 1
100 → 1
101 → 0
110 → 0
111 → 0

и берётся начальное состояние $(\ldots, 0, 0, 1, 0, 0,\ldots)$; интересует последовательность значений столбца, где вначале стоит единица.

Вольфрам писал(а):

Problem 1: Does the center column always remain non-periodic?

Problem 2: Does each color of cell occur on average equally often in the center column?

Problem 3: Does computing the $n$-th cell of the center column require at least $O(n)$ computational effort?

То есть первая вроде обозначает, имеет ли эта последовательность вид $abbbb\ldots$ или нет.

[Утундрий]

Первая спрашивает не зациклится ли последовательность с каким-то астрономическим периодом.

[arseniiv]

Ну да, я имел в виду под $a, b$ конечные подпоследовательности.

[Soul Friend]

Предложил две последовательности в OEIS : A329444, A329458.
Может кто поможет найти для этих последовательностей правильное название и код в PARI/GP.

[arseniiv]

Там пока ничего нет.

[Soul Friend]

Просто надо авторизоваться в OEIS, и зайти в draft edits этих последовательностей.

[Dmitriy40]

arseniiv
Они зарезервированы за автором. Но пока не подтверждены. Смотреть надо на страницу history для каждой. Типа тут. Или на страницу draft edits, там внизу есть нормальный вид.
Можно и без авторизации, руками подправить ссылки.

Soul Friend
Никак не могу найти где же всё таки 5 бит то из названия темы? Пока нашёл только 3, а интересно же про 5 ... Или слепой?

[Soul Friend]

Dmitriy40
Про пять бит это A329458. Значения этой последовательности не превышают $2^5$ .

Dmitriy40 в сообщении #1425930 писал(а):

а интересно же про 5 ...

В первом посте я давал ссылку про 5-ти битное кодирование, название выдуманное, может не соответствовать вашим ожиданиям.

[Dmitriy40]

(Оффтоп)

Ааа, понял, это извращение перекодирование состояний автомата в десятичные цифры и потом трансформация правила 30 в новое уже над десятичными цифрами, потому и 5 бит надо ... Вопрос только "а нафига?!" если никакой новой информации это не даёт, да и счёт особо не ускоряет. Ну человеку чуть поприятнее, не одни 0 и 1, а цифры от 0 до 7, но и только.
Я просто сначала не вникал, увидел что известный автомат и дальше не полез разбираться в наворотах над ним.
Собственно и не понимаю как из строки "1" получают строку "124", должно же получаться "34" (ну или "13764" если сдвигаться на 1 бит, а не на 3), правило 30 не изменилось же, лишь перенумеровали битовое поле по другому.
Не, нафик, не моё, лень вдумываться в непонятную нумерологию, не обещающую никакого выигрыша.

[wrest]

Чтобы вам помочь в написании проги на PARI надо чтобы вы внятно изложили алгоритм, чего вы хотите.
Ясно что вам не надо (или надо?) держать в памяти предыдущие состояния автомата, а только текущее (и из него вычислять следующее), и хранить (или сразу печатать) только центральную колонку. Ясно что каждое новое состояние длиннее предыдущего на минимум на два бита, так что миллионное состояние потребует минимум два миллиона бит на хранение (что в общем и немного, но миллиард бит уже и немало).

[Dmitriy40]

Кучу if-ов можно заменить на выбор из массива. Во всяком случае обычно - можно. Для исходного правила (хоть 30, хоть любого) достаточно массива в 8 ячеек, для этого модифицированного - сами считайте.
Плюс хранить левую и правую границу (если они могут быть не симметричны) и считать только в их рамках.

Примерно так:

? rule=[0,1,1,1,1,0,0,0]; \\для исходного правила 30
? m=vector(9);m[5]=1; \\начальное состояние
? n=vector(#m);
? for(i=4,6,n[i]=rule[m[i-1]*4+m[i]*2+m[i+1]+1]);m=n \\тут границы счёта 4..6 поставлены руками
%1 = [0, 0, 0, 1, 1, 1, 0, 0, 0]
? for(i=2,#m-1,n[i]=rule[m[i-1]*4+m[i]*2+m[i+1]+1]);m=n \\тут границы максимальны
%2 = [0, 0, 1, 1, 0, 0, 1, 0, 0]
? for(i=2,#m-1,n[i]=rule[m[i-1]*4+m[i]*2+m[i+1]+1]);m=n
%3 = [0, 1, 1, 0, 1, 1, 1, 1, 0]

Разумеется тут простор для дальнейшей оптимизации скорости: отказ от второго массива, хранение левых двух бит отдельно, сразу в переменной-индексе, один доступ к исходному массиву на каждом шаге, один сдвиг влево и сложение вместо суммы произведений, вычисление границ.
Если нужен только центральный столбец (ну плюс-минус), то можно прогнать счёт вперёд, а потом назад, с уменьшением границ счёта обратно до центра, ведь влияние ячеек ограничено, это позволит удвоить количество итераций (для центрального участка).

(Оффтоп)

Хотел прикинуть как быстро можно считать на асме под AVX2 - ну люблю я это дело, да - но там видно даже на глаз, что нужно два битовых сдвига на каждый выходной бит в байте, т.е. 14 сдвигов на весь регистр 256 битов, они не параллелятся и идут в один порт, так что скорость не выше 18 битов на такт. Краевые эффекты (пересечения границ 64 бит) будут малы, их всего 3шт на 256 битов, скорость из-за них упадёт ну пусть даже в идеале до 16 битов на такт. На миллиард битов и 3ГГц на ядро скорость порядка 50 итераций в секунду на ядро. И это хорошо оптимизированный ассемблер! Плюс чтение и запись памяти ограничит скорость примерно до тех же цифр, порядка 50-100 Гбит/с. Так что не раскатывайте губу на десятки миллиардов битов или даже на миллионы битов на PARI, у меня одна итерация кода выше занимает 0.4с для миллиона ячеек, ускорить можно раза в три-четыре думаю. Хотя, если запустить на GPU, вот тогда да, скорость будет ещё на порядок-два выше, можно думать и о сотне миллиардов битов. Или на процессоре с AVX512, там есть удобная команда вычисления бита, вместо 14-20 тактов на регистр может хватить и 3-5.

[Soul Friend]

Dmitriy40 в сообщении #1425936 писал(а):

Собственно и не понимаю как из строки "1" получают строку "124"

$00100$ берем по три клетки с лева на право $001_2=1_{10}$, $010_2=2_{10}$, $100_2=4_{10}$, итого 124, никакой нумерологии, простое десятичное представление ЭКА.

[Dmitriy40]

Soul Friend
Т.е. состояние 124 - начальное? Это так записано двоичное 0001000? Почему тогда оно во второй строке, а в первой начальное таки 0001000? Путаница.
А с пятибитным представлением путаница уже в первых двух строках, где уединённая 1, правильное начальное состояние в третьей строке, "1 2 4 8 16" (дальше проверять лень, ясно же что банальный пересчёт из двоичной системы в десятичную и лично мне двоичный автомат намного проще и понятнее).

[Soul Friend]

Dmitriy40 в сообщении #1425960 писал(а):

Т.е. состояние 124 - начальное?

нет, начальное $00100_2=1_{10}$, 124 это следующий шаг по правилу 30: $1_{10}=1_2$, $2_{10}=1_2$, $4_{10}=1_2$ - равенство по правилу 30. Поэтому $124$ на втором ряду. Ведь начальное $00100_2$ появляется по щучьему веленью по моему хотенью, и вычислить его не получится.