Осциллятор (конфигурация клеточного автомата)

У этого термина существуют и другие значения, см. Осциллятор.

Осцилля́тор (англ. oscillator) — класс конфигураций в «Жизни» — модели клеточного автомата, созданной Конвеем.

Описание

Осциллятор — конфигурация клеточного автомата, которая после конечного числа поколений повторяется в изначальном виде и положении. Другими словами, осциллятор — это любой образец, который является предшественником самого себя^[1], хотя до очередного повтора его состояния может проходить сколь угодно большое количество поколений.

Минимальное число поколений, через которое осциллятор возвращается в исходное состояние, называется периодом осциллятора. Осциллятор с периодом 1 обычно называется устойчивой конфигурацией^[2], так как он не изменяется в ходе эволюции.

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

Примеры

В «Жизни» конечные осцилляторы известны для всех периодов, после нахождения в июле 2023 последних недостающих осцилляторов с периодами 19^[3] и 41^[4]. Это открытие доказало, что «Жизнь» является омнипериодическим^[5] клеточным автоматом, так как существует метод, позволяющий сконструировать осциллятор с любым периодом большим или равным 43^[6].

Кроме того, до июля 2022^[7] все известные примеры осцилляторов с периодом 34 были тривиальными, поскольку они состояли из отдельных компонент, осциллирующих с ме́ньшими периодами. К примеру, осциллятор с периодом 34 можно получить путём размещения во вселенной двух независимых осцилляторов с периодами 2 и 17. Осциллятор считается нетривиальным, если он содержит хотя бы одну клетку, период осцилляции которой равен периоду осциллятора^[5][8].

• 
  Мигалка, период 2^[9][10]
• 
  Звезда, период 3^[11]
• 
  Крест, период 3^[12]
• 
  Французский поцелуй, период 3^[13]
• 
  Часы-2, период 4^[14]
• 
  Вертушка, период 4^[15]
• 
  Октагон-2, период 5^[16]
• 
  Фумарола, период 5^[17]
• 
  Пятигушка, период 5^[18]
• 
  Галактика Кока, период 8^[19]
• 
  Пентадекатлон, период 15^[20]