Проблема большинства (клеточный автомат) - Majority problem (cellular automaton)

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

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

Постановка задачи

Учитывая конфигурацию клеточного автомата с двумя состояниями с я + j ячеек всего, я из которых находятся в нулевом состоянии и j из которых находятся в одном состоянии, правильное решение проблемы голосования должно в конечном итоге обнулить все ячейки, если я > j и должен в конечном итоге установить для всех ячеек единицу, если я < j. Желаемое конечное состояние не указано, если я = j.

Проблема также может быть обобщена для проверки того, находится ли доля нулей и единиц выше или ниже некоторого порога, отличного от 50%. В этом обобщении также дана порог ; правильное решение проблемы голосования должно в конечном итоге обнулить все ячейки, если и должен в конечном итоге установить для всех ячеек единицу, если . Желаемое конечное состояние не указано, если .

Примерные решения

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

Правило, предложенное Гачем, Курдюмовым и Левиным, устанавливает состояние каждой ячейки следующим образом. Если ячейка равна 0, ее следующее состояние формируется как большинство среди значений самой ячейки, ее ближайшего соседа слева и его соседа на три пробела слева. Если, с другой стороны, ячейка равна 1, ее следующее состояние формируется симметрично, так как большинство из значений самой ячейки, ее ближайшего соседа справа и его соседа на три пространства справа. В случайно сгенерированных экземплярах это дает около 78% точности при правильном определении большинства.

Дас, Митчелл, а Кратчфилд показал, что можно разработать лучшие правила, используя генетические алгоритмы.[2]

Невозможность идеального классификатора

В 1995 году Land and Belew[3] показал, что не существует правила двух состояний с радиусом р а плотность ρ правильно решает проблему голосования на всех начальных конфигурациях, когда количество ячеек достаточно велико (больше примерно 4р/ ρ).

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

В 2013 году Бузич, Фатес, Марковичи и Майрес представили более простое доказательство невозможности создания идеального классификатора плотности, которое справедливо как для детерминированных, так и для стохастических клеточных и любых измерений.[4]

Точное решение с альтернативными условиями прекращения

Как отмечали Капкарере, Сиппер и Томассини,[5][6] проблема большинства может быть решена полностью, если ослабить определение, согласно которому автомат, как говорят, распознал большинство. В частности, для Правило 184 автомат, когда запускается в конечной вселенной с циклические граничные условия, каждая ячейка бесконечно часто будет оставаться в состоянии большинства в течение двух последовательных шагов, в то время как только конечное число раз будет находиться в состоянии меньшинства в течение двух последовательных шагов.

В качестве альтернативы гибридный автомат, который выполняет Правило 184 для ряда шагов, линейных по размеру массива, а затем переключается на правило большинства (Правило 232), которое устанавливает для каждой ячейки большую часть себя и своих соседей, решает большинство проблема со стандартным критерием распознавания либо всех нулей, либо всех единиц в конечном состоянии. Однако эта машина сама по себе не является клеточным автоматом.[7] Более того, было показано, что составное правило Фукша очень чувствительно к шуму и не может превзойти зашумленный автомат Гача-Курдюмова-Левина, несовершенный классификатор, для любого уровня шума (например, от окружающей среды или от динамических ошибок).[8]

Рекомендации

  1. ^ Гач, Петер; Курдюмов, Г.Л .; Левин, Л.А. (1978). «Одномерные однородные массивы, размывающие конечные острова». Проблемы передачи информации (на русском). 14: 92–98.
  2. ^ Дас, Раджарши; Кратчфилд, Дж. П .; Митчелл, Мелани; Хэнсон, Дж. Э. (1995). Эшелман, Ларри Дж. (Ред.). Развитие глобально синхронизированных клеточных автоматов (PDF). Материалы Шестой Международной конференции по генетическим алгоритмам. Сан-Франциско: Морган Кауфманн.
  3. ^ Земля, Марка; Белью, Ричард (1995). «Не существует идеальных клеточных автоматов с двумя состояниями для классификации плотности». Письма с физическими проверками. 74 (25): 1548–1550. Bibcode:1995ПхРвЛ..74.5148Л. Дои:10.1103 / PhysRevLett.74.5148. PMID  10058695.
  4. ^ Бушич, Ана; Фатес, Назим; Марковичи, Ирен; Mairesse, Жан (2013). «Классификация плотности на бесконечных решетках и деревьях». Электронный журнал вероятностей. 51. Дои:10.1214 / EJP.v18-2325.
  5. ^ Capcarrere, Mathieu S .; Сиппер, Моше; Томассини, Марко (1996). «Два государства, р = 1 клеточный автомат, определяющий плотность ». Phys. Rev. Lett. 77 (24): 4969–4971. Bibcode:1996PhRvL..77.4969C. Дои:10.1103 / PhysRevLett.77.4969. PMID  10062680.
  6. ^ Сукумар, Н. (1998). «Влияние граничных условий на клеточные автоматы, классифицирующие плотность». arXiv:комп-газ / 9804001. Bibcode:1998comp.gas..4001S. Цитировать журнал требует | журнал = (помощь)
  7. ^ Фуксь, Хенрик (1997). «Решение задачи классификации плотности с двумя правилами клеточных автоматов». Физический обзор E. 55 (3): 2081–2084. arXiv:комп-газ / 9703001. Bibcode:1997PhRvE..55.2081F. Дои:10.1103 / Physreve.55.r2081. S2CID  118954791.
  8. ^ Мендонса, Дж. Р. Г. (2011). «Чувствительность к шуму и эргодичность конвейера клеточных автоматов, классифицирующая плотность». Физический обзор E. 83 (3): 031112. arXiv:1010.0239. Bibcode:2011PhRvE..83c1112M. Дои:10.1103 / PhysRevE.83.031112. PMID  21517459. S2CID  118494753.