Nova caracterização da noção de reversibilidade parcial para autômatos celulares unidimensionais em reticulado cíclico, com foco no espaço elementar

• Ano de defesa: 2015
• Autor(a) principal: Corrêa, Ronaldo de Castro
• Orientador(a): Oliveira, Pedro Paulo Balbi de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Presbiteriana Mackenzie
• Palavras-chave em Português: Autômato celular unidimensional; regra reversível; regra parcialmente reversível; reversibilidade parcial; espaço elementar
• Palavras-chave em Inglês: one-dimensional cellular automaton; reversible rule; partially reversible rule; partial reversibility; elementary space
• Área do conhecimento CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
• Link de acesso: http://dspace.mackenzie.br/handle/10899/24383

Autômatos celulares são sistemas dinâmicos discretos que, por meio de regras de ação local, até mesmo muito simples, podem apresentar processamento global arbitrariamente complexo. A reversibilidade é uma propriedade que poucas regras possuem e que garante a existência de uma regra inversa capaz de reverter a evolução temporal da regra original. Para uma regra ser reversível, todas as configurações possíveis de reticulado devem possuir somente uma única configuração antecessora, ou seja, uma única pré-imagem. Nesse contexto, havia sido proposto na literatura o conceito de regras poderem ser caracterizadas por sua reversibilidade parcial relativa, ou seja, regras poderem ser mais ou menos reversíveis que outras. Essa noção é representada por meio do padrão de pré-imagem da regra, que é composto pelas quantidades ordenadas de pré-imagens de todas as configurações possíveis de reticulado, até um tamanho máximo. Para classificar as regras das mais reversíveis para as menos reversíveis, ou agrupá-las caso possuíssem a mesma reversibilidade, era feita a ordenação lexicográfica dos padrões de pré-imagens. Este trabalho reavaliou a definição original, com base nos autômatos celulares elementares, apesar de os resultados serem aplicáveis a qualquer outra família unidimensional de regras. Assim, foi proposta uma grandeza que representa o nível de reversibilidade de uma regra, também baseada em seu padrão de pré-imagem, mas agora a partir da probabilidade de reverter corretamente cada configuração possível de reticulado, até um tamanho máximo dado. Tal medida permite analisar o nível de reversibilidade de uma regra em termos absolutos, e não mais relativamente a outras regras. Dessa forma, torna-se possível analisar individualmente os níveis de reversibilidade das regras, o que possibilitou inferir o nível de reversibilidade de regras para reticulados arbitrariamente maiores que os calculados, em particular, identificando regras que tendem a ser reversíveis conforme o tamanho do reticulado tende a infinito. Também foi possível definir uma operação que, a partir das próprias transições de estado de uma regra, permite obter parcialmente as regras que possuem o mesmo nível de reversibilidade, sem a necessidade do cálculo do padrão de pré-imagem, que é extremamente custoso computacionalmente.