Cellular Automata (CA) have a long history as computation models, but only in the last few years have serious attempts started to implement them in terms of molecules. Such nano-technological innovations promise very cost-effective fabrication because of the regular structure of CA, which allows assembly through molecular self-organization. The small sizes of molecules combined with their availability in Avogadro-scale numbers promises a huge computational power, in which the massive parallelism inherent in CA can be effectively exploited. This paper discusses critical background aspects of our recent results on the implementation of a CA by a molecular assembly (Bandyopadhyay et al., Nature Physics 2010). © 2010 Springer-Verlag.