Как вечная жизнь в Голли продолжается?

Question

В хэш-жизни поле обычно рассматривается как теоретически бесконечная сетка с рассматриваемым узором в центре около начала координат. Quadtree используется для представления поля. Учитывая квадрат 2 ^ (2k) ячеек, 2k на стороне, на k-м уровне дерева, хеш-таблица хранит 2 ^ (k-1) на 2 ^ (k-1) квадрата клеток в центре , 2 ^ (к-2) поколения в будущем. Например, для квадрата 4x4 хранится центр 2x2, 1 поколение вперед; а для квадрата 8x8 хранится центр 4x4, 2 поколения вперед.

Таким образом, при начальной конфигурации 8x8 мы получаем квадрат 4x4 на 1 поколение вперед по центру w.r.t. квадрат 8x8 и квадрат 2x2 2 поколения вперед (1 поколение вперед по квадрату 4x4) по центру 8x8. С каждым новым поколением наше представление о сетке уменьшается, в свою очередь мы получаем следующее состояние автоматов. Мы не можем идти дальше после того, как продвинулись внутренние 2x2 квадратные 2 ^ (k-2) поколения вперед.

Так как же жизнь хаш в Голли продолжается вечно? Также его вид на поле никогда не уменьшается. Кажется, он показывает состояние всех автоматов после 2 ^ (k-2) поколений. Более того, учитывая начальную конфигурацию, которая расширяется со временем, вид алгоритма, кажется, увеличивается. Вид сетки уменьшается, чтобы показать расширяющиеся автоматы?

Answer 1

Есть хорошая статья о докторе Доббе , в которой подробно рассказывается о том, как работает HashLife. Основной ответ заключается в том, что вы не просто запускаете алгоритм на существующих узлах, вы также используете новые смещенные узлы для получения следующего поколения.

Answer 2

Чтобы быть понятным (потому что ваши символы ^ отсутствовали), вы спрашиваете:

Учитывая квадрат 2 ^ (2k) клеток, 2 ^ k на стороне, на k-м уровне дерево, хеш-таблица хранит квадрат 2 ^ (k-1) -by-2 ^ (k-1) клеток в центр, 2 ^ (к-2) поколений в будущем. [...]

Итак, при первоначальной конфигурации 8x8 [...] с каждым новым поколением наше представление о сетке уменьшается, в свою очередь мы получаем следующее состояние автоматы. Мы не можем идти дальше после получения внутреннего 2x2 квадрат 2 ^ k-2 поколения вперед.

Так как же жизнь хаш в Голли продолжается вечно? Также его мнение о поле никогда не уменьшается.

Вместо того, чтобы начинать с вашего шаблона 8x8, представьте себе, что вы начинаете с большего шаблона, который содержит внутри себя ваш шаблон 8x8. Например, вы могли бы начать с шаблона 16x16, который имеет ваш шаблон 8x8 в центре, и с 4 рядами полей пустых ячеек по краям. Такой шаблон легко построить, собрав пустые узлы 4x4 с подузлами 4x4 вашего начального шаблона 8x8.

Учитывая такой шаблон 16x16, алгоритм HashLife может дать вам ответ 8x8, 4 поколения в будущем.

Вы хотите больше? Хорошо, начните с шаблона 32x32, который содержит в основном пустое пространство, с шаблоном 8x8 в центре. С этим вы можете получить ответ 16x16, который будет через 8 поколений в будущем.

Что если в вашем паттерне есть движущиеся объекты, которые движутся достаточно быстро, чтобы выйти за пределы этой области 16x16 через 8 поколений? Просто - начните с шаблона запуска 64x64, но вместо того, чтобы пытаться запустить его целых 16 поколений, просто запустите его для 8 поколений.

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

Answer 3

Центрированные квадраты - это только предварительно вычисленные данные. Алгоритм действительно постоянно поддерживает всю вселенную и обновляет все ее части, а не только центры.