CLASSIFICAÇÃO DE COMPLEXIDADE DE AUTÔMATOS CELULARES POR MEIO DE ANÁLISE DE VETORES DE TEXTURA

Resumo

Autômatos Celulares (ACs) são sistemas definidos a partir de regras simples, baseadas em células, os estados dessas e a relação entre elas. Contudo, essas definições básicas podem gerar comportamentos extremamente complexos e até imprevisíveis antes de serem propriamente simulados. A partir disso, estudos tem tentado classificá-los a partir dessas propriedades de complexidade de comportamento. Uma das classificações que surgiu foi a de Wolfram (1984), que se baseou nos padrões na evolução temporal dos ACs, para definir quatro classes de complexidade: Classe I, Classe II, Classe III e Classe IV. Baseado nessa classificação, conjectura-se (WOLFRAM, 2002) que regras da Classe IV apresentam computabilidade universal.

É possível classificar os ACs manualmente em espaços de regras mais básicas, porém, ao tratar de espaços maiores e mais complexos, a classificação manual se torna inviável, surgindo assim a necessidade de desenvolver modelos de classificação automática.

Nesse projeto é implementado um método de classificação a partir da análise de características de um vetor de texturas extraídas da evolução temporal da execução das regras dos ACs unidimensionais binários com configurações iniciais aleatórias. Para automatizar e testar a análise das características, são utilizados os algoritmos k-NN (k-Nearest Neighbors) e o percéptrons de múltiplas camadas (PMCs).

Os resultados obtidos apontam que o algoritmo desenvolvido tem 67% de precisão, porém, esse método ainda pode ser explorado mais profundamente.