Проблема большинства

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

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

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

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

Проблему также можно обобщить, проверив, находится ли соотношение нулей и единиц выше или ниже некоторого порога, отличного от 50%. В этом обобщении также даетсяпорог $\rho$; правильное решение задачи голосования должно в конечном итоге обнулить все ячейки, если ${\tfrac {i}{i+j}}<\rho$ и в конечном итоге должен установить все ячейки в единицу, если ${\tfrac {j}{i+j}}>\rho$. Желаемое конечное состояние не указано, если ${\tfrac {j}{i+j}}=\rho$.

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

2D расширение алгоритма «Гача, Курдюмова, Левина». Белые пиксели составляют лишь 52% от общего числа в случайном стартовом наборе.

Гач, Курдюмов и Левин нашли автомат, который хотя и не всегда правильно решает задачу большинства, но во многих случаях делает это. В своем подходе к проблеме Качество правила клеточного автомата измеряется долей $2^{i+j}$ возможные стартовые конфигурации, которые он правильно классифицирует.

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

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

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

В 1995 году Ленд и Белью показал, что ни одно правило двух состояний с радиусом r и плотностью ρ не решает правильно проблему голосования во всех начальных конфигурациях, когда количество ячеек достаточно велико (больше примерно 4 r /ρ).

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

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

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

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

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