Redes booleanas como modelos discretos da realidade

Abstract

É conhecido que, no caso dos autómatos celulares elementares unidimensionais, o espaço das regras possui cardinalidade 256. No entanto, rapidamente se observou que, na realidade, este espaço podia ser reduzido devido à introdução de certas transformações de equivalência dinâmica. O número de regras não equivalentes, isto é, o número de classes de equivalência de regras, passa então para apenas 88. Motivados por estas pesquisas, começamos por estudar as diferentes transformações dinamicamente equivalentes possíveis para o caso de autómatos celulares elementares bidimensionais, tendo constatado que, das 65 536 regras distintas, existem apenas 4 856 classes de equivalência. Apesar deste número ser ainda muito grande, achámos que seria possível efectuar uma análise exaustiva sobre a dinâmica dos autómatos celulares elementares no plano. Neste trabalho apresentamos a classificação, de forma análoga à feita por Wolfram para os autómatos celulares elementares unidimensionais, das 4 856 dinâmicas não equivalentes dos autómatos celulares elementares bidimensionais.

It is known that, in the case of elementary one-dimensional cellular automata, the space of the rules has cardinality 256. However, it was quickly observed that, in reality, this space could be reduced due to the introduction of certain transformations of dynamic equivalence. The number of non-equivalent rules, that is the number of classes of rules equivalence, then goes to only 88. Motivated by these researches, we began by studying the different possible transformations dynamically equivalent in what concerns the two dimensional elementary automata, concluding that, from 65 536 distinct rules, there are only 4 856 equivalence classes. Although this number was still too big, we thought it would be possible to effectuate an exhaustive analysis about the dynamic of the elementary cellular automata in the plan. In this work, we present the classification, similar to the one presented by Wolfram for the one-dimensional elementary cellular automata, of the 4 856 non- equivalent dynamics of the two-dimensional elementary cellular automata.