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 .
Usando reglas de transición locales, las células no pueden conocer el recuento total de todas las del 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 el tamaño total del sistema. También requiere que el sistema envíe mensajes a una distancia lineal en el tamaño del sistema y que el sistema reconozca un lenguaje no regular . Por tanto, este problema es un caso de prueba importante en la medición de la potencia computacional de los sistemas de autómatas celulares.
Planteamiento del problema
Dada una configuración de un autómata celular de dos estados con i + j celdas en total, i de las cuales están en el estado cero yj de las cuales están en el estado único, una solución correcta al problema de votación debe eventualmente establecer todas las celdas en cero si i > j y eventualmente debe establecer todas las celdas en una si i < j . El estado final deseado no se especifica si i = j .
El problema también se puede generalizar para probar 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 le da un umbral; Una solución correcta al problema de la votación debe eventualmente poner a cero todas las celdas si y eventualmente debe establecer todas las celdas en una si . El estado eventual deseado no se especifica si.
Soluciones aproximadas
Gács, Kurdyumov y Levin encontraron un autómata que, aunque no siempre resuelve correctamente el problema mayoritario, 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 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 vecino inmediato a la izquierda y su vecino tres espacios a la izquierda. Si, por el contrario, una celda es 1, su siguiente estado se forma simétricamente, ya que la mayoría entre los valores de sí misma, su vecino inmediato a la derecha y su vecino tres espacios a la derecha. En casos generados aleatoriamente, esto logra aproximadamente un 78% de precisión para determinar correctamente la mayoría.
Das, Mitchell y Crutchfield demostraron que es posible desarrollar mejores reglas utilizando algoritmos genéticos . [2]
Imposibilidad de un clasificador perfecto
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 por ceros o unos debe convertirse en un cero. Del mismo modo, cualquier regla perfecta nunca puede hacer que la proporción de unos superesi estaba por debajo (o viceversa). Luego muestran que cualquier regla perfecta asumida causará una aislada que empujará la relación por encima de cancelarse o, si la proporción de unos es menor que , causará que uno aislado introduzca unos falsos en un bloque de ceros haciendo que la proporción de unos sea mayor que .
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 sea válido tanto para celulares deterministas y estocásticos como para cualquier dimensión. [4]
Solución exacta con condiciones de terminación alternativas
Como lo observaron Capcarrere, Sipper y Tomassini, [5] [6] el problema de la mayoría puede resolverse perfectamente si uno 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á infinitamente a menudo 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 para un número de pasos lineales en el tamaño de la matriz, y luego cambia a la regla de la mayoría (Regla 232), que establece cada celda en la mayoría de sí misma y sus vecinas, resuelve la mayoría. Problema con el criterio de reconocimiento estándar de todos los 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 ruidoso autómata Gacs-Kurdyumov-Levin, un clasificador imperfecto, para cualquier nivel de ruido (por ejemplo, del entorno o de errores dinámicos). . [8]
Referencias
- ^ Gács, Péter; Kurdyumov, GL; Levin, LA (1978). "Matrices uniformes unidimensionales que lavan islas finitas" . Problemy Peredachi Informatsii (en ruso). 14 : 92–98.
- ^ Das, Rajarshi; Crutchfield, JP; Mitchell, Melanie ; Hanson, JE (1995). Eshelman, Larry J. (ed.). Evolución de los autómatas celulares sincronizados globalmente (PDF) . Actas de la Sexta Conferencia Internacional sobre Algoritmos Genéticos . San Francisco: Morgan Kaufmann.
- ^ Punto de referencia; Belew, Richard (1995). "No existe ningún autómata celular perfecto de dos estados para la clasificación de densidad". Cartas de revisión física . 74 (25): 1548-1550. Código Bibliográfico : 1995PhRvL..74.5148L . doi : 10.1103 / PhysRevLett.74.5148 . PMID 10058695 .
- ^ Bušić, Ana; Fatès, Nazim; Marcovici, Irène; Mairesse, Jean (2013). "Clasificación de densidad en celosías y árboles infinitos" . Revista Electrónica de Probabilidad . 51 . doi : 10.1214 / EJP.v18-2325 .
- ^ Capcarrere, Mathieu S .; Sipper, Moshe; Tomassini, Marco (1996). " Autómata celular de dos estados, r = 1 que clasifica la densidad" . Phys. Rev. Lett . 77 (24): 4969–4971. Código Bibliográfico : 1996PhRvL..77.4969C . doi : 10.1103 / PhysRevLett.77.4969 . PMID 10062680 .
- ^ Sukumar, N. (1998). "Efecto de las condiciones de contorno en los autómatas celulares que clasifican la densidad". arXiv : comp-gas / 9804001 . Código bibliográfico : 1998comp.gas..4001S . Cite journal requiere
|journal=
( ayuda ) - ^ Fukś, Henryk (1997). "Solución del problema de clasificación de densidad con dos reglas de autómatas celulares". Revisión E física . 55 (3): 2081-2084. arXiv : comp-gas / 9703001 . Código Bibliográfico : 1997PhRvE..55.2081F . doi : 10.1103 / physreve.55.r2081 . S2CID 118954791 .
- ^ Mendonça, JRG (2011). "Sensibilidad al ruido y ergodicidad de una línea de montaje de autómatas celulares que clasifica la densidad". Revisión E física . 83 (3): 031112. arXiv : 1010.0239 . Código bibliográfico : 2011PhRvE..83c1112M . doi : 10.1103 / PhysRevE.83.031112 . PMID 21517459 . S2CID 118494753 .