Representação de autômatos celulares unidimensionais balanceados, por meio de templates

William Barbosa dos Santos¹; Pedro Paulo Balbi de Oliveira²

¹ Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, São Paulo,; ² Pós-Graduação em Engenharia Elétrica e Computação, Universidade Presbiteriana Mackenzie, São Paulo

Resumo

Discute-se a criação de uma representação para regras balanceadas de autômatos celulares unidimensionais, utilizando-se a noção de templates de regras, que é uma forma de se representar um conjunto de regras de determinada característica. Uma regra é balanceada quando sua representação k-ária apresenta todos os estados de um espaço de regras em quantidades iguais; tal propriedade é importante, por exemplo, no estudo de regras reversíveis. Implementou-se um algoritmo capaz de gerar todas as regras que o template representa, com posterior análise das mesmas quanto à presença da propriedade de balanceamento. Apesar de o método desenvolvido ser custoso computacionalmente, sua utilização em conjunto com outras propriedades de autômatos celulares faz como que a solução aqui proposta possa ser de extrema valia como ferramenta de redução do espaço de regras, em casos onde o balanceamento seja desejável.