Explorando a noção de reversibilidade parcial de autômatos celulares elementares em reticulados cíclicos

• Ano de defesa: 2010
• Autor(a) principal: Freitas, Rodrigo da Silva
• 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ômatos celulares; regras reversíveis; regras parcialmente reversíveis; padrão de reversibilidade; espaço elementar
• Palavras-chave em Inglês: cellular automata; reversible rules; partially reversible rules; reversibility pattern; elementary space
• Área do conhecimento CNPq: CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA
• Link de acesso: http://dspace.mackenzie.br/handle/10899/24311

Cellular automata have been studied as computer models in many different forms. Several of its properties have been widely explored, among which reversibility stands out. This property is able to provide a cellular automaton the possibility of having their temporal evolution regenerated backward in time, regardless of its initial configuration, through an inverse cellular automaton. Reversibility is such a well characterized concept that many fundamental results associated with it have been obtained, such as the development of algorithms to enumerate all reversible one-dimensional cellular automata and the undecidability of this property for cellular automata in dimensions larger than 1. The driving force for the present research is to introduce a new concept involving the reversibility ability of a cellular automaton, the concept of partial reversibility, which is analysed herein according to the pre-images of all initial configurations of a rule, up to a certain length. This new concept may be useful for evolutionary searches for reversible cellular automata, to allow the use of cellular automata in tasks related somehow to the reversibility degree of a rule, or in applications where reversible rules are demonstrably employed, such as in cryptography. To that end, some parameters presumably related to reversibility are studied and compared, and empirical measures (lexicographical and numerical) are addressed. The results involving these empirical measures, showed that is possible to refer to a more partially reversible rule than another, besides revealing properties, apparently unknown so far, involving the pre-images of elementary rules.