Найти обратное преобразование

[tetricka12]

Пусть у нас есть матрица
$\begin{equation*} X = \begin{pmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 \end{pmatrix} \end{equation*}$

и на нее действует преобразование

$F(X) = Y$
$\begin{equation*} Y = \begin{pmatrix} 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0 \end{pmatrix} \end{equation*}$

Преобразование работает следующим образом:
сначала для каждого элемента матрицы вычисляется сумма его и его 8 соседей(для крайних элементов,
представляем что матрица склеена как тор) и затем из этой матрицы вычитается исходная матрица X

$\begin{equation*} \hat{X} = \begin{pmatrix} 3 & 5 & 3 & 4\\ 3 & 4 & 4 & 5\\ 2 & 4 & 2 & 3\\ 2 & 4 & 3 & 5 \end{pmatrix} \end{equation*}$


Затем, для каждого элемента делаем следующее
Если $(\hat{x}_{ij}=3) | (x_{ij}= 1\quad \& \quad \hat{x}_{ij}=2)$ истинно то 1 иначе 0.

Так вот, вопрос.
Пусть нам известна матрица Y и преобразование $F()$
Можно ли найти $ X $

$X = F^{-1}(Y)$.

Ну то есть вопрос следующий.
Как, зная преобразование $F()$ найти $F^{-1}()$, и существует ли оно?

P.S. Я понимаю, что условие задачи сформулировал очень коряво, и отвечу на любой вопрос, если не поняли условие.

[ИСН]

Это самое запутанное описание игры "Жизнь", которое я видел.

[abicorios]

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

[Pphantom]

ИСН в сообщении #1472995 писал(а):

Это самое запутанное описание игры "Жизнь", которое я видел.

Кстати, если я правильно помню, конфигурации типа "Сад Эдема" (у которых нет предков) были найдены еще где-то в 80-х годах.

[tetricka12]

ИСН в сообщении #1472995 писал(а):

Это самое запутанное описание игры "Жизнь", которое я видел.

Да, загуглил, обычная игра жизнь. Спасибо, не знал как называется.

ИСН в сообщении #1472995 писал(а):

Это самое запутанное описание игры "Жизнь", которое я видел.

abicorios в сообщении #1472997 писал(а):

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

А можно ли предсказать не обратное преобразование, а условную вероятность обратного преобразования?
ну то есть в каждой ячейки будет не 0 или 1, а вероятность того, что он 1

[alisa-lebovski]

tetricka12 в сообщении #1473292 писал(а):

А можно ли предсказать не обратное преобразование, а условную вероятность обратного преобразования?
ну то есть в каждой ячейки будет не 0 или 1, а вероятность того, что он 1

Да, если у Вас есть вероятностное распределение на множестве всех конфигураций (допустим, из конечного числа $N$ клеток, тогда их $2^N$) на предыдущем шаге, то каждому прообразу конфигурации, имеющейся на текущем шаге, можно сопоставить условную вероятность, равную отношению вероятности этого прообраза к сумме вероятностей прообразов. Далее для условной вероятности того, что в данной клетке 1, можно просуммировать условные вероятности всех тех прообразов, у кого там стоит 1. Проблема в другом: какое распределение предполагать на множестве конфигураций? Если в исходный момент времени оно равномерное (все $2^N$ конфигураций равновероятны), то на следующем шагу уже так не будет. Получается, результат зависит от того, как давно у Вас идет процесс.

[alisa-lebovski]

Кстати, игра "Жизнь" - наиболее известный, но лишь один представитель из класса подобных игр. Их можно изучать на разные свойства, например, насколько они благоприятны или нет для роста клеток. Мне как-то попалась статья об этом, может кому-то будет интересно - http://www.mathnet.ru/php/archive.phtml ... n_lang=rus

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