Problema de la mayoría

El problema de la mayoría , o tarea de clasificación de densidad , es el problema de encontrar reglas de autómatas celulares unidimensionales que realicen con precisión la votación por mayoría .

Mediante reglas de transición locales, las células no pueden conocer el número total de unos en el sistema. Para contar el número de unos (o, por simetría, el número de ceros), el sistema requiere un número logarítmico de bits en su tamaño total. Además, requiere que el sistema envíe mensajes a una distancia lineal con respecto a su tamaño y que reconozca un lenguaje no regular . Por lo tanto, este problema constituye un caso de prueba importante para medir la capacidad computacional de los sistemas de autómatas celulares.

Dada una configuración de un autómata celular de dos estados con un total de i + j celdas, i de las cuales están en el estado cero y j de las cuales están en el estado uno, una solución correcta al problema de votación debe eventualmente establecer todas las celdas en cero si i  > j y debe eventualmente establecer todas las celdas en uno si i < j . El estado final deseado no está especificado si i = j .     

El problema también puede generalizarse a comprobar si la proporción de ceros y unos está por encima o por debajo de algún umbral distinto del 50%. En esta generalización, también se proporciona un umbral.${\displaystyle \rho }$; una solución correcta al problema de votación debe eventualmente establecer todas las celdas a cero si${\displaystyle {\tfrac {i}{i+j}}<\rho }$y eventualmente debe establecer todas las celdas en uno si${\displaystyle {\tfrac {j}{i+j}}>\rho }$. El estado final deseado no está especificado si${\displaystyle {\tfrac {j}{i+j}}=\rho }$.

Gács, Kurdyumov y Levin encontraron un autómata que, aunque no siempre resuelve correctamente el problema de la mayoría, lo hace en muchos casos. ^{[ 1 ]} En su enfoque del problema, la calidad de una regla de autómata celular se mide por la fracción de la${\displaystyle 2^{i+j}}$posibles configuraciones iniciales que clasifica correctamente.

La regla propuesta por Gacs, Kurdyumov y Levin establece el estado de cada celda de la siguiente manera: si una celda es 0, su siguiente estado se forma como la mayoría entre los valores de sí misma, su vecina inmediata a la izquierda y su vecina tres espacios a la izquierda. Si, por el contrario, una celda es 1, su siguiente estado se forma simétricamente, como la mayoría entre los valores de sí misma, su vecina inmediata a la derecha y su vecina tres espacios a la derecha. En instancias generadas aleatoriamente, esto logra una precisión de aproximadamente el 78 % en la determinación correcta de la mayoría.

Das, Mitchell y Crutchfield demostraron que es posible desarrollar mejores reglas utilizando algoritmos genéticos . ^{[ 2 ]}

En 1995, Land y Belew ^{[ 3 ]} demostraron que ninguna regla de dos estados con radio r y densidad ρ resuelve correctamente el problema de votación en todas las configuraciones iniciales cuando el número de celdas es suficientemente grande (mayor que aproximadamente 4 r /ρ).

Su argumento muestra que, debido a que el sistema es determinista , cada celda rodeada completamente de ceros o unos debe convertirse en un cero. Del mismo modo, ninguna regla perfecta puede hacer que la proporción de unos supere${\displaystyle \rho }$si estaba por debajo (o viceversa). Luego muestran que cualquier regla perfecta asumida causará una aislada que empujó la proporción más allá de${\displaystyle \rho }$ser cancelados o, si la razón de unos es menor que${\displaystyle \rho }$, hará que un uno aislado introduzca unos espurios en un bloque de ceros, lo que hará que la proporción de unos sea mayor que${\displaystyle \rho }$.

En 2013, Busic, Fatès, Marcovici y Mairesse dieron una prueba más simple de la imposibilidad de tener un clasificador de densidad perfecto, que es válida tanto para sistemas celulares deterministas como estocásticos y para cualquier dimensión. ^{[ 4 ]}

Como observaron Capcarrere, Sipper y Tomassini, ^{[ 5 ] [ 6 ]} el problema de la mayoría puede resolverse perfectamente si se relaja la definición por la cual se dice que el autómata ha reconocido a la mayoría. En particular, para el autómata de la Regla 184 , cuando se ejecuta en un universo finito con condiciones de contorno cíclicas , cada celda permanecerá infinitas veces en el estado de mayoría durante dos pasos consecutivos mientras que solo un número finito de veces estará en el estado de minoría durante dos pasos consecutivos.

Alternativamente, un autómata híbrido que ejecuta la Regla 184 durante un número de pasos lineal en el tamaño del arreglo, y luego cambia a la regla de la mayoría (Regla 232), que establece cada celda como la mayoría de sí misma y sus vecinas, resuelve el problema de la mayoría con el criterio de reconocimiento estándar de todos ceros o todos unos en el estado final. Sin embargo, esta máquina no es en sí misma un autómata celular. ^{[ 7 ]} Además, se ha demostrado que la regla compuesta de Fukś es muy sensible al ruido y no puede superar al autómata ruidoso de Gacs-Kurdyumov-Levin, un clasificador imperfecto, para ningún nivel de ruido (por ejemplo, del entorno o de errores dinámicos). ^{[ 8 ]}

Dado que la tarea había pasado de ser imposible a bastante simple dependiendo de la definición del resultado deseado, el problema se generalizó a la siguiente definición: un autómata clasificador de densidad perfecto se define simplemente como un autómata donde el conjunto de configuraciones alcanzables cuando la densidad de la configuración inicial está por debajo del umbral es perfectamente disjunto con el conjunto de configuraciones alcanzables cuando la densidad de la configuración inicial está por encima del umbral. Usando esa definición, Capcarrere y Sipper ^{[ 9 ]} pudieron demostrar dos condiciones necesarias para que un autómata celular sea un clasificador de densidad perfecto: (1) la densidad de la configuración inicial debe conservarse en el tiempo, y (2) la tabla de reglas debe exhibir una densidad de 0,5 (incluso cuando el umbral para la clasificación es diferente de 0,5). Esa última propiedad es bastante única en el sentido de que asocia una condición sobre la forma de la regla a un comportamiento global.