Computando com autômatos celulares e suas composições temporais ou espaciais

Resumo

Autômatos celulares são sistemas complexos totalmente discretos que, por possuírem uma natureza dual, apresentam-se tanto como um sistema dinâmico quanto um modelo computacional. Estruturalmente eles consistem de um reticulado regular de células, tal qual uma grade, e uma regra de transição de estados que governa como a transição de estado de cada célula do reticulado deve ocorrer, em função dos estados das células vizinhas. Uma forte motivação para estudar autômatos celulares é sua habilidade de realizar computações, motivação esta que está no centro deste projeto. Compreender como os autômatos celulares computam e como eles devem ser projetados de forma a realizar uma dada tarefa computacional poderia ter profundo impacto em tecnologia da informação e na teoria da computação, uma vez que esse conhecimento proveria um modelo de computação completamente novo, totalmente paralelo, descentralizado, discreto e local.No entanto, o entendimento de como estas computações são realizadas ainda é extremamente vago; de fato, apesar de mais de quatro décadas de pesquisa em autômatos celulares, seu uso para computar funções em geral ainda está em estágio embrionário. E a principal razão para esta deficiência é a falta de um método robusto para projetar autômatos celulares que tenham comportamento pré-definido. Autômatos celulares interessantes conhecidos na área, e praticamente em qualquer área onde eles tenham sido aplicados, foram todos encontrados através de engenharia minuciosa e detalhada, buscas exaustivas em domínios restritos, métodos formais em problemas extremamente particulares, e métodos de busca especializados, em geral evolutivos, aplicados em espaços delimitados.Embora cada uma destas abordagens individuais tenha tido sucesso a seu próprio modo, a dissociação entre elas tem impedido avanços reais no sentido de preencher a necessidade de um método de projeto mais geral e flexível, que possa ser útil em ampla gama de áreas e problemas. Perseguir este alvo é o objetivo deste projeto, sendo que a maneira de perseguí-lo é através da combinação dos vários conhecimentos individualmente adquiridos nas abordagens acima. Dada a habilidade inconteste dos algoritmos evolutivos no projeto de sistemas complexos, em domínios muito diversos, é esta família de algoritmos que guiará prioritariamente nossos esforços. Algoritmos evolutivos são métodos de busca inspirados na evolução biológica, que são particularmente apropriados para problemas onde o espaço de busca é muito grande, ou quando métodos diretos alternativos inexistem, como usualmente acontece no projeto de sistemas complexos em geral, e no de autômatos celulares, em particular. O caminho a ser seguido combina técnicas de computação evolutiva, com buscas enumerativas em pequenas regiões do espaço de busca, ambos os processoss guiados por informação estática derivada da tabela de transição de estados dos autômatos celulares envolvidos.Em sintonia com a motivação geral do projeto, três tópicos relacionados aos autômatos celulares elementares também serão investigados, especificamente, o comportamento limite de regras elementares, o produto da combinação de suas evoluções temporais, e a combinação espacial de diferentes regras no mesmo reticulado. O quadro geral resultante do projeto é, portanto, avançar no entendimento e exploração da habilidade computacional de autômatos celulares (seja através de suas regras individuais, ou através de suas combinações temporais ou espaciais), bem como o desenvolvimento de formas efetivas para projetá-los através de técnicas enumerativas e de computação evolutiva. O projeto se dará principalmente no contexto uma seleção de três problemas - a tarefa de classificação de densidade, o reconhecimento de dígitos decimais manuscritos, e o problema da paridade - muito embora outros também possam vir a ser considerados, à medida em que as investigações progridam e o próprio grupo de trabalho cresça. (AU)