Aspects of algorithms and dynamics of cellular paradigms

Abstract

Els paradigmes cel·lulars, com les xarxes neuronals cel·lulars (CNN, en anglès) i els autòmats cel·lulars (CA, en anglès), són una eina excel·lent de càlcul, al ser equivalents a una màquina universal de Turing. La introducció de la màquina universal CNN (CNN-UM, en anglès) ha permès desenvolupar hardware, el nucli computacional del qual funciona segons la filosofia cel·lular; aquest hardware ha trobat aplicació en diversos camps al llarg de la darrera dècada. Malgrat això, encara hi ha moltes preguntes a obertes sobre com definir els algoritmes d'una CNN-UM i com estudiar la dinàmica dels autòmats cel·lulars. En aquesta tesis es tracten els dos problemes: primer, es demostra que es possible acotar l'espai dels algoritmes per a la CNN-UM i explorar-lo gràcies a les tècniques genètiques; i segon, s'expliquen els fonaments de l'estudi dels CA per mitjà de la dinàmica no lineal (segons la definició de Chua) i s'il·lustra com aquesta tècnica ha permès trobar resultats innovadors.

Los paradigmas celulares, como las redes neuronales celulares (CNN, en<br/>inglés) y los autómatas celulares (CA, en inglés), son una excelente<br/>herramienta de cálculo, al ser equivalentes a una maquina universal de<br/>Turing. La introducción de la maquina universal CNN (CNN-UM, en<br/>inglés) ha permitido desarrollar hardware cuyo núcleo computacional<br/>funciona según la filosofía celular; dicho hardware ha encontrado<br/>aplicación en varios campos a lo largo de la ultima década. Sin<br/>embargo, hay aun muchas preguntas abiertas sobre como definir los<br/>algoritmos de una CNN-UM y como estudiar la dinámica de los autómatas<br/>celular. En esta tesis se tratan ambos problemas: primero se demuestra<br/>que es posible acotar el espacio de los algoritmos para la CNN-UM y<br/>explorarlo gracias a técnicas genéticas; segundo, se explican los<br/>fundamentos del estudio de los CA por medio de la dinámica no lineal<br/>(según la definición de Chua) y se ilustra como esta técnica ha<br/>permitido encontrar resultados novedosos.

Cellular paradigms, like Cellular Neural Networks (CNNs) and Cellular Automata (CA) are an excellent tool to perform computation, since they are equivalent to a Universal Turing machine. The introduction of the Cellular Neural Network - Universal Machine (CNN-UM) allowed us to develop hardware whose computational core works according to the principles of cellular paradigms; such a hardware has found application in a number of fields throughout the last decade. Nevertheless, there are still many open questions about how to define algorithms for a CNN-UM, and how to study the dynamics of Cellular Automata. In this dissertation both problems are tackled: first, we prove that it is possible to bound the space of all algorithms of CNN-UM and explore it through genetic techniques; second, we explain the fundamentals of the nonlinear perspective of CA (according to Chua's definition), and we illustrate how this technique has allowed us to find novel results.