Проблема сверхжизни в "жизни" Конуэя

[stzozo]

Игра "жизнь", которую придумал Конуэй - это не игра с игроками, а виртуальная вселенная со своими очень простыми физическими законами

Comments

вроде бы

[a_shen]

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

Re: вроде бы

[stzozo]

Вы не поняли.
Вопрос - существует ли такой алгоритм на каждое начальное положение?

Например, для стационарной фигуры существует. Просто сравниваем координаты по списку.
Для планерного ружья существует. Если координаты внутри ружья - берем от времени остаток от деления на тридцать и сравниваем с шаблоном. Если координаты вне ружья - сравниваем координату со временем (успели ли туда долететь планеры), берем остаток от деления на тридцать времени и координаты и опять же сравниваем с шаблоном.

Re: вроде бы

[a_shen]

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

Re: вроде бы

[stzozo]

Я же привел примеры фигур, для которых он существует.

Re: вроде бы

[a_shen]

так вопрос был про алгоритм, который годится для любой фигуры?

Re: вроде бы

[stzozo]

Нет.
Говорю же - Вы неправильно поняли.