Игра "жизнь" Конвея

[ya2500]

Думаю, мне с моей темой подойдёт именно этот раздел.
===

На всякий случай и для порядку:

Тех, кто не знает, что это, думаю, лучше всего отправить в википедию - Игра «Жизнь» (англ. Conway's Game of Life) — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.[1] Это игра без игроков[2][3], в которой

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

Фанаты этой "игры" ищут и находят разные интересные популяции. Например, как "Сады Эдема" - такие популяции, которые не могут быть порождены никакой другой, а могут появиться в этом мире только путём изначального размещения их на поле игроком. Или, например, была найдена самовоспроизводящаяся популяция, причём - скорее построена, чем найдена. Её автор построил механизм, который может порождать разные популяции и самовоспроизведение - лишь частный случай его применения. Вообще, эта "игра" полна по Тьюрингу, со всеми вытекающими.

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

Похожие темы:

Игра "жизнь" и моделирование эволюции - какие достижения?
- вопрос темы поставлен странно - насколько мне известно, игра Конвея никогда не предназначалась для такого. Тем не менее, сам вопрос таки интересен. Последнее сообщение там 2019 года

Такова "Жизнь"
- приведены ссылки на рекомендуемые ресурсы(ныне не доступны), приведены скриншоты чего-то имеющего отношение к продвинутым "цветным" правилам игры(ныне утеряны). Последнее сообщение там 2006 года.

-- 10.03.2023, 19:01 --

===

Рассмотрим поведение бесконечной популяции, представляющей из себя "случайный посев" бесконечного поля.
Что мы получаем:

0) Изначально на нашем поле можно будет найти абсолютно любую возможную конфигурацию. Все возможные конфигурации во всех их сочетаниях.

1) После первой итерации исчезнут все "Сады Эдема".

2) Далее возможны варианты: ЕСЛИ существуют такие популяции, которые не могут появиться на поле после шага N (частным случаем которых являются Сады Эдема, которые не могут появиться после шага 0), то постепенно такие конфигурации будут "выпадать" с нашего бесконечного поля и это приведёт к чему-то??. ИНАЧЕ - ситуация скатывается в вечный танец самоповторения, а на нашем поле в каждый момент можно будет найти любую конфигурацию, кроме Садов Эдема.

Однако,
ВОПРОС: возможно ли найти такую функцию, однозначно ставящую в соответствие координатам ячейки(x,y) значение 0(пуста) или 1(жива) таким образом, чтобы соблюдалось выполнение пункта 0 - то есть, чтобы на засеянном таким образом поле можно было гарантированно найти абсолютно любую возможную конфигурацию?

[mihaild]

Если под конфигурацией понимать конечную, то, конечно, очень легко подобрать начальную конфигурацию $A$, такую что для любого шага $N$, числа $k$ и конфигурации $B$ выполнено следующие условия:
1) конфигурация $B$ помещается в квадрат $k \times k$
2) существует конфигурация $C$, в результате эволюции которой за $N$ шагов возникает квадрат, $k \times k$, содержащий конфигурацию $B$
то
в результате эволюции конфигурации $A$ на $N$-м шаге будет существовать квадрат $k \times k$, содержащий конфигурацию $B$.

(насколько я знаю, вопрос о том, существует ли конфигурация, которая может получиться из какой-то за один шаг, но не может получиться ни из какой за два шага, открыт)

-- 10.03.2023, 16:33 --

UPD: решил перепроверить, оказывается этот вопрос решили совсем недавно - в 2016 доказали, что есть конфигурации, у которых есть отец, но нет дедушки, или есть дедушка, но нет прадедушки, а в 2022 доказали, что для любого $n$ есть конфигурация, которая может получиться на $n$-м шаге, но не может на $n + 1$-м https://arxiv.org/abs/2202.07346.