La Sobreyectividad es cuando hay un mapeo de elementos de tal forma que cualquier elemento en la configuración en la cual evolucionó el autómata es la imagen de al menos un elemento del conjunto anterior al cual se le aplicó la regla, es decir que todas las células pueden ser producidas por alguna vecindad o que no hay Jardín del Edén.
Una regla de los autómatas celulares es sobreyectiva si cualquier configuración tiene un predecesor. Es inyectiva si este predecesor es único. Será sobreyectiva si y solo si tiene un jardín del edén vacío.[5]
Hay Jardín del Edén cuando hay al menos un elemento en un conjunto el cual no es la imagen de un elemento en otro conjunto, o sea que no puede ser producido por alguna de las vecindades que forman a ese autómata aplicando la regla de evolución.
Las ideas de sobreyectividad y jardines del edén fueron introducidas en primera instancia por Moore.
Figure 2.1: Representación gráfica de la sobreyectividad. Se observa
que cada elemento en la evolución tiene al menos una imagen en los ancestros
Se le llama ancestro de una célula a aquella vecindad que la produjo al aplicársele la regla de evolución o que la puede producir en un momento dado, puede ser posible que varias vecindades producen a la misma célula por lo que esta tendrá múltiples ancestros.
Se han obtenido resultados de que el número total de pre-imagenes de ciertas secuencias bien definidas escalan con la longitud de la secuencia.