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

[stzozo]

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

Comments

вроде бы

[a_shen]

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

Re: вроде бы

[stzozo]

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

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

Re: вроде бы

[a_shen]

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

Re: вроде бы

[stzozo]

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

[dig386]

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

[ichthuss]

По-моему, логичнее границу проводить не по O(log(n)), а по O(log(n)*n) (со строгим неравенством). "Жизнь" на площади s клеток должна либо зациклиться, либо выйти за пределы площади не более чем за 2s шагов. Следовательно, "честный" алгоритм, тратящий время на просчёт каждой клетки, будет затрачивать O(log(n)*n) шагов программы на моделирование n шагов "жизни". Алгоритм, считающий быстрее, срезает углы.

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