ads:
1
UNIVERSIDADE PRESBITERIANA MACKENZIE
MESTRADO EM ENGENHARIA ELÉTRICA
Algumas Propriedades de Autômatos Celulares
Unidimensionais Conservativos e Reversíveis
Angelo Schranko de Oliveira
Texto de dissertação apresentado ao Programa
de Pós-Graduação em Engenharia Elétrica
como requisito das exigências do exame para
obtenção do título de Mestre em Engenharia
Elétrica.
Orientador: Dr. Pedro Paulo Balbi de Oliveira
São Paulo
Dezembro / 2008
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
2
Banca Examinadora
Dr. Pedro Paulo Balbi de Oliveira
Orientador
Universidade Presbiteriana Mackenzie
Dr. Elbert Einstein Nehrer Macau
Examinador Externo
Instituto Nacional de Pesquisas Espaciais
Dr. Leandro Nunes de Castro
Examinador Interno
Universidade Presbiteriana Mackenzie
ads:
3
Dedicatória
Aos que enxergam um universo num cair de uma gota d’água – e se maravilham com isso.
À minha querida noiva, Memi, por seu amor, carinho, compreensão e ajuda, sem os quais o
desenvolvimento do presente trabalho teria sido consideravelmente mais árduo.
À toda minha família e, em particular, à minha querida mãe, Expedita Maria – meu grande
exemplo de persistência e de luta – por sempre acreditar e confiar incondicionalmente em mim, e, com
sua simplicidade, jamais ter me questionado sobre o que tanto eu fazia por de trás dos meus cálculos e
livros desde sempre, ou até mesmo quando eu tentara observar o Halley (com sucesso), aos meus 6
anos de idade.
“
A Filosofia está escrita nesse grande livro – o Universo –
que permanece continuamente aberto.”
Galileo Galilei
4
Agradecimentos
À Universidade Presbiteriana Mackenzie, por sua vocação ao ensino e à pesquisa em nossa
sociedade.
Aos pesquisadores referenciados, pois suas obras foram de fundamental importância para o
desenvolvimento desta pesquisa.
Aos familiares, amigos e todos aqueles que me acompanharam de forma direta ou indireta no
desenvolvimento do presente trabalho.
Em particular e especialmente ao professor Dr. Pedro Paulo Balbi de Oliveira, que conduziu-
me ao mundo da pesquisa científica e me orientou de forma exemplar. Por suas inúmeras revisões,
sugestões, correções, críticas e elogios, os quais foram indispensáveis à minha formação. Sou-lhe
imensamente grato.
Aos meus colegas Paulo Florêncio e Rogério Ywassa, por sua importante colaboração na
produção de um artigo que foi apresentado no Workshop AUTOMATA 2008, em Bristol, Reino
Unido, e que deu origem a uma outra versão, [Schranko e de Oliveira, 2009], anexa a este documento,
aceita para o Journal of Cellular Automata.
À Coordenadoria de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) pela bolsa de
estudos a mim concedida. Ao Fundo Mackenzie de Pesquisa (MackPesquisa) pelo apoio financeiro
que me permitiu apresentar os primeiros resultados deste trabalho em evento internacional. À
FAPESP, pelo apoio financeiro através do projeto de pesquisa Processo 2005/04696-3, à Wolfram
Research, através do Mathematica Academic Grant 1149, e novamente ao MackPesquisa, por projeto
de pesquisa através do Edital 2007, todos concedidos a meu orientador. Meus sinceros
agradecimentos.
5
Sumário
Resumo ............................................................................................................................... 6
Abstract............................................................................................................................... 7
Capítulo 1: Introdução ............................................................................................................. 8
Capítulo 2: Autômatos Celulares........................................................................................... 10
2.1 Autômatos Celulares e Leis de Conservação............................................................... 13
2.2 Autômatos Celulares e Reversibilidade....................................................................... 15
Capítulo 3: Relações entre Autômatos Celulares Unidimensionais Reversíveis e as Pré-
Imagens de seus Blocos Básicos........................................................................................................ 19
3.1 Definições .................................................................................................................... 19
3.2 O Parâmetro α de Caracterização Dinâmica................................................................ 19
Capítulo 4: Autômatos Celulares Conservativos e Reversíveis............................................. 26
Capítulo 5: Algumas Relações entre Autômatos Celulares Lineares e Autômatos Celulares
Conservativos e Reversíveis .............................................................................................................. 31
Capítulo 6: Dinâmica dos Autômatos Celulares Conservativos e Reversíveis...................... 36
Capítulo 7: Considerações Finais........................................................................................... 43
Referências Bibliográficas................................................................................................ 45
Apêndice I......................................................................................................................... 50
6
Resumo
Autômatos celulares (ACs) podem ser definidos como sistemas dinâmicos sobre redes n-
dimensionais de componentes localmente conectados, cuja evolução ocorre de forma discreta, síncrona
e homogênea. Dentre suas diversas aplicações, têm sido utilizados como ferramenta para modelagem
de sistemas complexos regidos por leis fundamentais de conservação (autômatos celulares
conservativos) ou reversibilidade (autômatos celulares reversíveis). Outra propriedade fundamental
que pode ser observada nos ACs diz respeito à sua linearidade (autômatos celulares lineares) ou não-
linearidade. Fenômenos lineares normalmente apresentam menor complexidade dinâmica, enquanto
fenômenos não-lineares podem apresentar propriedades tais como sensibilidade às condições iniciais e
rotas para caos. O presente trabalho concentra-se na investigação de propriedades de autômatos
celulares unidimensionais pertencentes à interseção dessas quatro classes, isto é, autômatos celulares
unidimensionais conservativos, reversíveis, e lineares ou não-lineares. Após definições básicas, são
revisitados os conceitos de conservabilidade e reversibilidade. Em seguida, introduz-se um parâmetro
de caracterização dinâmica que relaciona a distribuição do número de pré-imagens dos blocos básicos
à reversibilidade de autômatos celulares unidimensionais e apresentam-se algumas demonstrações de
suas propriedades gerais. Observações empíricas aqui realizadas sugerem que um autômato celular
unidimensional é conservativo e reversível se, e somente se, sua função local de transição de estados é
uma composição das funções locais de transição de estado dos autômatos celulares conservativos e
reversíveis de vizinhança de comprimento n=2; tal observação foi constatada para vizinhanças de
comprimento n∈{2, 3, 4, 5, 6} e quantidade de estados q=2; n∈{2, 3} e q=3; n∈{2, 3} e q=4. Uma
demonstração para tal conjectura permitiria estabelecer uma enumeração entre os comprimentos das
vizinhanças e a quantidade de autômatos celulares unidimensionais conservativos e reversíveis no
espaço correspondente, os quais podem ser facilmente identificados através do cálculo das
composições das funções locais de transição de estados com n=2. Por fim, apresentam-se relações
entre as classes dos ACs conservativos, reversíveis, lineares e não-lineares, suas dinâmicas espaço-
temporais e campos de bacias de atração.
Palavras-chave: Autômato celular; conservabilidade; reversibilidade; não-linearidade; sistema
dinâmico discreto; NKS.
7
Abstract
Cellular automata (CAs) can be defined as discrete dynamical systems over n-dimensional networks of
locally connected components, whose evolution occur in a discrete, synchronous and homogeneous
fashion. Among their several applications, they have been used as a tool for complex systems
modeling governed by fundamental laws of conservation (number-conserving cellular automata) or
reversibility (reversible cellular automata). Another fundamental property that can be observed in CAs
is regarding to their linearity (linear cellular automata) or nonlinearity. Usually, linear phenomena
present low dynamic complexity, however, nonlinear phenoma can present complex behaviours like
sensitive dependence on initial conditions and routes to chaos. This work focuses on investigating
properties of cellular automata belonging to the intersection of those four classes, namely, reversible,
number-conserving, and linear or nonlinear cellular automata. After presenting basic definitions, the
notions of number-conserving cellular automata, conservation degree and reversibility are reviewed.
Following, a dynamical characterisation parameter which relates the reversibility property of a one-
dimensional cellular automaton and the pre-images of their basic blocks is introduced, and some
proofs of its general properties are given. Empirical observations herein suggest that a cellular
automaton is reversible and number-conserving if, and only if, its local transition function is a
composition of the local transition functions of the reversible, number-conserving cellular automata
with neighbourhood size n=2; such an observation was drawn for neighbourhood sizes n∈{2, 3, 4, 5,
6} and number of states q=2; n∈{2, 3} and q=3; n∈{2, 3} and q=4. A proof for such a conjecture
would allow the enumeration between neighbourhood lengths and the quantity of reversible, number-
conserving cellular automata in the corresponding space, which can be easily identified by working
out the compositions of the local transition functions with n=2. Finally, some relationships between
reversible, number-conserving, linear and nonlinear CA rules, their spatio-temporal diagrams and
basin of attraction fields are presented.
Keywords: Cellular automaton; conservativity; reversibility; nonlinearity; discrete dynamical system;
NKS.
8
Capítulo 1: Introdução
Autômatos celulares (ACs) estão entre os primeiros modelos de computação natural,
introduzidos por John von Neumann e Stanislaw Ulam, ao final da década de 40, com intuito de se
projetar um mecanismo artificial auto-replicante e computacionalmente universal [Burks, 1970]. Sua
arquitetura massivamente paralela e de processamento local é particularmente útil na modelagem de
sistemas complexos, onde podem-se observar fenômenos emergentes como auto-organização e
formação de padrões [Wuensche e Lesser, 1992]. ACs podem também ser definidos de tal forma que
satisfaçam certas leis de conservação [Boccara e Fukś, 2002], reversibilidade [Margolus, 1984] ou
ambas, tornando-se assim úteis na modelagem de sistemas naturais que apresentam tais propriedades.
O presente trabalho investiga propriedades de ACs conservativos (no sentido apresentado por
Boccara e Fukś [2002]) e reversíveis (ACCRs). A seguir, no Capítulo 2, apresentam-se as definições
básicas ao desenvolvimento dos capítulos posteriores. Introduz-se o conceito de leis de conservação no
contexto dos ACs e apresentam-se alguns dos principais resultados relacionados à decibilidade e
dinâmica. Também é introduzida a classe dos ACs reversíveis, onde apresentam-se de forma breve
alguns dos principais conceitos e resultados históricos. Em seguida, no Capítulo 3, introduz-se um
parâmetro de caracterização dinâmica que relaciona ACs unidimensionais reversíveis às pré-imagens
de seus blocos básicos e demonstram-se algumas de suas propriedades fundamentais. No Capítulo 4,
investigam-se propriedades relacionadas aos ACCRs unidimensionais. Baseando-se nas composições
das funções de transição de estado para n=2, verificou-se empiricamente, através de buscas exaustivas,
que se um AC unidimensional é reversível e conservativo, então sua função de transição de estados é
uma composição como a definida acima. O Capítulo 5 apresenta relações entre as classes dos ACs
conservativos, ACs reversíveis e ACs lineares, apresentando como se dá a interseção destas classes e
demonstrando um teorema relacionado à natureza dos ACCRs não-lineares, bem como as diferenças
fundamentais entre os diagramas espaço-temporais dos ACCRs lineares e não-lineares. O Capítulo 6
fornece uma análise da complexidade dos ACs, baseada em características apresentadas em seus
diagramas espaço-temporais e campos de bacias de atração. Finalmente, no Capítulo 7, apresentam-se
as conclusões da presente pesquisa, bem como questões em aberto e possíveis extensões.
Esta dissertação iniciou-se com investigações a respeito de uma definição e interpretação para
uma grandeza capaz de medir o grau de conservabilidade de ACs unidimensionais. O artigo resultante
destas investigações [Schranko et al, 2008] foi apresentado no Workshop AUTOMATA 2008 (Bristol,
UK) e deu origem a uma outra versão, [Schranko e de Oliveira, 2009], que foi aceita para o Jornal of
Cellular Automata, e encontra-se atualmente no prelo. Paralelamente, diversas hipóteses relacionadas
à classe dos ACCRs foram levantadas e demonstradas, incluindo a definição do parâmetro α,
diretamente relacionado à classe mais geral dos AC reversíveis e, portanto, também aos ACCRs.
Decidiu-se então, que este trabalho seria baseado no desenvolvimento de tais idéias e, posteriormente,
um novo artigo com base em tais resultados seria confeccionado e submetido. Dessa forma, incluiu-se
o texto [Schranko e de Oliveira, 2009] como Apêndice I. Contudo, vale ressaltar que ambos os textos
9
são independentes e não se esgotam em si mesmos, pois além das referências apresentadas, há também
diversas questões em aberto em ambos os trabalhos.
10
Capítulo 2: Autômatos Celulares
ACs são sistemas dinâmicos completamente discretos, isto é, tanto sua composição espacial quanto
sua evolução temporal e variáveis de estado se dão em domínios discretos. Todo processamento é
distribuído, de modo que as computações ocorrem localmente e sem a presença de uma unidade
central de processamento ou mecanismos de armazenamento [Wolfram, 1994]. Basicamente, são
constituídos por um conjunto de células, dispostas lado a lado em uma grade regular n-dimensional,
onde cada célula possui um número finito de estados. A dinâmica de sua evolução espaço-temporal é
determinada através de uma função de transição de estados, a qual leva em consideração os estados de
uma dada célula e o de outras na sua vizinhança em um dado instante de tempo. Assim, o estado da
célula de posição i no instante t é dado por c(i,t) e seu novo estado após uma iteração é dado por
c(i,t+1), conforme a Figura 1.
Figura 1. Evolução local de um AC unidimensional de vizinhança de comprimento n = r
+ r
r
+1.
Dessa forma, sendo Z o conjunto dos números inteiros e N o conjunto dos números inteiros
não negativos, a dinâmica local dos ACs é definida pela função (ou regra) de transição de estados
f:S
n
→S, onde n = r
+ r
r
+1, e r
, r
r
∈ Z
+
são, respectivamente, os raios à esquerda e à direita da regra
considerada, resultando numa regra de n-entradas. Um estado é dito quiescente se satisfaz f(q, q, ..., q)
= q, q∈N. Portanto, formalmente, ACs unidimensionais podem ser definidos [Boccara e Fukś, 2002] a
partir de uma função c:Z×N→ S que satisfaz:
c(i, t+1) = f(c(i – r
, t), c(i – r
+ 1, t), ..., c(i + r
r
, t))
(1)
onde S = {0, 1, ..., q-1}, q∈N representa um conjunto finito de estados, sendo que, para todo i∈Z,
t∈N.
11
De forma geral é possível definir um vetor (n-dimensional) de vizinhança N, onde cada
coordenada determina a posição relativa das células consideradas pela função local de transição de
estados. Por exemplo, considerando-se N = (0, 1, 2), a função local de transição de estados será em
função do estado das células nas posições i+0, i+1 e i+2, ou seja, serão considerados os estados tanto
da própria célula quanto das duas outras células imediatamente à direita, o que equivale a definir r
= 0
e r
r
= 2. Note-se que N permite definir posições relativas não-consecutivas, isto é, vizinhança não-
locais (daí sua generalidade), onde o conceito de raio não é aplicável. Variações nas coordenadas N
para um mesmo AC podem implicar em alterações qualitativas em sua dinâmica espaço-temporal
[Nishio, 2006], contudo, certas propriedades tais como reversibilidade, são invariantes com relação a
permutações das coordenadas de N.
Para cada função local de transição f é possível associar biunivocamente um número W(f)∈Z
+
,
usualmente denominado número da regra do AC [2], tal que:
∑
∈
+⋅⋅⋅++
−−
=
n
n
n
nn
Sxxx
xqxqxq
n
qxxxffW
),...,,(
21
21
0
2
2
1
1
),...,,()(
(2)
Como exemplo, considere-se a regra de número 30, com S = {0, 1} e n = 3. Sua representação binária
é dada por 00011110
2
, fazendo com que sua função local de transição de estado seja definida por:
f(0,0,0) = 0, f(0,0,1) = 1, f(0,1,0) = 1, f(0,1,1) = 1
f(1,0,0) = 1, f(1,0,1) = 0, f(1,1,0) = 0, f(1,1,1) = 0
(3)
Uma configuração é qualquer elemento C∈S
Z
e o conjunto de todas as configurações é
representado por C. Dessa forma, a função global de transição de estados G:C→C associa cada
elemento C∈C
a um outro elemento do mesmo conjunto, através da aplicação da função local de
transição de estados a todas as vizinhanças da configuração considerada. Como exemplo, a Figura 2
apresenta a aplicação da função global de transição de estados da regra de número 30 a uma
configuração de comprimento finito. Neste trabalho são considerados apenas ACs unidimensionais de
comprimento finito, donde substitui-se S
Z
por S
L
, L∈Z
+
sendo o comprimento da configuração. Dessa
forma, um AC pode ser representado pela tripla (S, N, f).
12
Figura 2. Aplicação da função global de transição referente à regra 30, considerando-se S = {0, 1},
N = (0, 1, 2) e configuração inicial 01100101.
Na Figura 2, observa-se a configuração inicial (t = 0) dada por 01100101 e, após uma iteração
(aplicação da função global de transição), obtem-se 10111010. A transição 010→1 é parte da definição
da função local de transição de estados da regra 30, conforme apresentado em (3). A aplicação da
função local de transição ocorre de forma síncrona e paralela em todas as vizinhanças. Além disso,
uma vez tratando-se de configurações de comprimento finito e dada a homogeneidade dos ACs, pode-
se definir uma ‘condição de contorno periódica’ de tal forma que, considerando N = (0, 1, 2) por
exemplo, a aplicação da função local de transição à célula da extrema direita (a última) do reticulado
leva em consideração a vizinhança formada por esta, pela primeira e pela segunda células
respectivamente. Assim, na Figura 2, observa-se que na configuração inicial (isto é, em t = 0) a última
célula tem estado igual a 1 e a célula de mesma posição na próxima iteração tem estado igual a 0. Isso
ocorre pois 101→1, conforme a definição da regra 30 (3).
Representa-se o espaço elementar de regras pela tripla (S, N, f), onde S = {0, 1} e N = (-1, 0, 1).
Com isso enumeram-se 2
8
regras distintas, pois cada uma das 2
3
vizinhanças são mapeadas a 2
estados. Entretanto, após a aplicação dos operadores de conjugação C e reflexão R, conforme definidos
em (4) e explicados a seguir, verifica-se o particionamento do espaço elementar de regras em 88
classes de equivalências dinâmicas, onde regras dinamicamente equivalentes pertecem a uma mesma
classe [Wolfram, 1994].
Cf(x
1
, x
2
, …, x
n
) = q – 1 – f(q – 1 – x
1
, q – 1 – x
2
, …, q – 1 – x
n
)
Rf(x
1
, x
2
, …, x
n
) = f(x
1
, x
2
, …, x
n
)
(4)
De fato, regras de uma mesma classe de equivalência dinâmica – induzida a partir da aplicação
do operador de conjugação, do operador de reflexão, ou da composição entre eles – são
qualitativamente equivalentes, como ilustra a Figura 3. Dessa forma, parâmetros de caracterização
13
dinâmica que sejam definidos devem ser numericamente iguais quando aplicados a tais regras
[Oliveira et al, 2001].
Figura 3. Diagramas espaço-temporais das regras 30 e 149.
Na Figura 3, observam-se os diagramas espaço-temporais das regras 30 e 149,
respectivamente. Nota-se que seus diagramas espaço-temporais são qualitativamente equivalentes. De
fato, a regra 149 nada mais é que o resultado da aplicação dos operadores C e R à regra 30,
equivalendo-se portanto à troca de estados {0→1, 1→0}, seguida por uma rotação de 180 graus em
relação ao eixo das ordenadas (i.e. espelhamento). Vale notar também que os operadores C e R
comutam, ou seja: CR(f) = RC(f). Neste trabalho a operação de composição de funções é denotada
pelo operador ‘bola’, isto é: . Ainda com relação à dinâmica espaço-temporal dos ACs, Wolfram
propôs uma classificação informal baseada na análise dos diagramas espaço-temporais e em conceitos
advindos da teoria dos sistemas dinâmicos, tais como pontos-fixos, ciclos periódicos e transientes
[Wolfram, 1994]. Segundo Wolfram, na Classe-I, quase todas as configurações iniciais convergem
para a um ponto-fixo homogêneo (por exemplo, todas as células no estado 0). Já na Classe-II, as
configurações iniciais tipicamente convergem para algum ponto-fixo ou algum ciclo periódico de
configurações. Já na Classe-III as configurações iniciais usualmente resultam em um comportamento
caótico e, finalmente, na Classe-IV, algumas configurações iniciais podem resultar em estruturas
complexas duradouras, possivelmente periódicas no limite, mas com longos transientes.
2.1 Autômatos Celulares e Leis de Conservação
Observam-se leis de conservação em muitos sistemas naturais, tais como sistemas mecânicos
(conservação de massa e momento), sistemas químicos (conservação de matéria) e, de forma geral,
conservação de energia. Idealmente, ACs como modelos de fenômenos naturais conservativos devem
apresentar comportamento equivalente a tais fenômenos, isto é, devem ser regidos por certas leis de
conservação. Hattori e Takesue [1991] introduziram o conceito de conservação de quantidades
aditivas, onde as invariantes nas iterações dos ACs estão relacionadas a somas de valores numéricos
14
locais. Uma das formas mais conhecidas de leis de conservação em ACs foi introduzida por Boccara e
Fukś [2002], onde a invariante é dada pela somatória dos estados das células, isto é, a soma dos
estados de cada configuração permanece constante durante a evolução do sistema. Por exemplo, a
iteração de qualquer regra conservativa (segundo Boccara e Fukś) considerando-se a configuração
inicial 1001110110, resulta numa permutação da mesma, pois a soma dos seus estados é preservada.
De fato, tal propriedade é válida para qualquer configuração inicial e qualquer número de iterações;
contudo, a densidade de estados (considerando q>2) não é necessariamente preservada, pois, por
exemplo, após uma iteração da regra de número 6772834745301, com q=3 e N=(-1, 0, 1), a
configuração inicial 102212100 resulta em 011121201, ambas com a mesma soma (valor 9) de
estados, mas densidades distintas de cada estado. ACs que satisfazem as condições de Boccara-Fukś
são denominados ACs conservadores de quantidades (number-conserving cellular automata), ou
simplesmente ACs conservativos (ACCs). O presente trabalho considera apenas ACCs no sentido de
Boccara-Fukś, isto é, aqueles que, ∀(x
1
,x
2
,...,x
n
)∈S
n
, a função local de transição de estados satisfaz:
∑
−+=
−
=
−+−
1
1
21132
121
)),...,,,0,...,0,0(),,,0,...,0,0((),...,,( ,...
n
k
kn
k
kn
k
n
xxxfxxxfxxxxf
(5)
Como exemplo, considere-se a regra 184 do espaço elementar. As condições de Boccara-Fukś
são como se segue:
f(0,0,0) = 0 ⇔ 0 = 0 →Verdade
f(0,0,0) = 0 ⇔ 0 = 0 →Verdade
f(0,0,1) = f(0,0,1) – f(0,0,0) ⇔ 0 = 0 – 0 →Verdade
f(0,1,0) = f(0,1,0) – f(0,0,0) ⇔ 0 = 0 – 0 →Verdade
f(0,1,1) = f(0,1,1) – f(0,0,0) ⇔ 1 = 1 – 0 →Verdade
f(1,0,0) = 1 + 2f(0,0,0) – f(0,0,1) – f(0,1,0) ⇔ 1 = 1 + 2.0 – 0 – 0 →Verdade
f(1,0,1) = 1 + f(0,0,0) – f(0,1,0) ⇔ 1 = 1 + 0 – 0 →Verdade
f(1,1,0) = 1 + f(0,1,0) – f(0,1,1) ⇔ 0 = 1 + 0 – 1 →Verdade
f(1,1,1) = 1 ⇔ 1 = 1 →Verdade
(6)
O diagrama espaço-temporal da regra 184 pode ser observado na Figura 4.
15
Figura 4. Diagrama espaço-temporal da regra 184 do espaço elementar para uma condição inicial aleatória de
comprimento 100 e 100 iterações.
Na Figura 4, observa-se a evolução espaço-temporal de uma configuração inicial aleatória de
comprimento 100. Nota-se que, a partir de um certo instante t, a regra 184 emula a regra 170, que
também é conservativa, pois é equivalente à aplicação do operador de deslocamento para a esquerda
(shift-left). Isto é, a partir de um certo instante t e dada uma certa configuração inicial, as dinâmicas
espaço-temporais de ambas as regras 170 e 184 são equivalentes [Moreira, 2003].
Do ponto de vista aplicado, ACCs podem ser utilizados para modelagem de sistemas físicos
isolados [Boccara e Fukś, 2002]. Por exemplo, no trabalho pioneiro de Nagel e Schreckenberg [1992]
introduziu-se um modelo para simulação do fluxo de veículos, onde a quantidade total de elementos se
mantém constante, ou seja, um sistema onde não ocorrem nem entradas ou saídas de novos veículos.
Seu modelo é baseado na regra conservativa 184 apresentada anteriormente.
2.2 Autômatos Celulares e Reversibilidade
Reversibilidade implica em preservação da informação [Toffoli e Margolus, 1990]. Do ponto
de vista da computação não-convencional, um sistema físico, químico ou biológico que emulasse um
AC computacionalmente universal, como por exemplo o AC 110 do espaço elementar [Wolfram,
2002], teria gasto energético minimizado se apresentasse também reversibilidade [Toffoli e Margolus,
1990]. Já do ponto de vista da computação convencional, ACs reversíveis têm aplicações na
modelagem de sistemas físicos termodinâmicos, tais como dinâmica de fluidos [Wolfram, 2002]. A
Figura 5 mostra o diagrama espaço-temporal da regra 85 do espaço elementar, a qual apresenta
reversibilidade.
16
Figura 5. Diagrama espaço-temporal da regra 85 do espaço elementar, com configuração inicial de
comprimento 100 e 100 iterações.
Considere um AC e seja G:C→C sua função global de transição. Hedlund [1969] demonstrou
em seu trabalho pioneiro sobre dinâmica simbólica que um AC G é reversível se, e somente se, G é
uma função bijetora. Equivalentemente, um AC é reversível se, e somente se, dada qualquer
configuração em seu espaço de estados, existe apenas uma pré-imagem relacionada a esta
configuração, conforme apresenta-se, a título de exemplo, na Figura 6.
Figura 6. Campo de bacias de atração da regra 85 do espaço elementar, para configurações de comprimento 4.
17
Observa-se, na Figura 6, o campo de bacias de atração da regra 85 para as configurações de
comprimento 4. Cada configuração C, representada por um vértice, é ligada a outra configuração C’ de
tal forma que C’ = G(C). Evidentemente, dada a reversibilidade da regra 85, não há configurações
Garden-of-Eden (isto é, configurações que não apresentam predecessores). Portanto, qualquer campo
de bacias de atração será constituído apenas por órbitas periódicas.
Toffoli [1977] demonstrou que, para qualquer AC d-dimensional, que define uma função
global de transição G, existe um AC reversível no espaço de dimensão d+1, cuja função global
associada G’ emula G. Uma vez que a regra 110 do espaço elementar apresenta computabilidade
universal, o teorema anterior implica na existência de um AC bidimensional reversível e também
computacionalmente universal. Um AC unidimensional reversível e com computabilidade universal
foi apresentado por Morita [2007]. [Amoroso e Patt, 1972] demonstraram que a decibilidade sobre a
reversibilidade de um AC unidimensional pode ser efetivamente estabelecida e construíram um
algoritmo aplicando seu resultado. Contudo, Kari [1994] demonstrou que não existem algoritmos
capazes de determinar se um dado AC com dimensão maior ou igual a dois é ou não reversível e
portanto, no caso geral, a reversibilidade de um dado AC é um problema indecidível. Por um longo
período, questões relacionadas à reversibilidade de ACs foram consideradas em segundo plano
[Toffoli e Margolus, 1990], principalmente devido à inexistência de uma ferramenta prática para sua
criação. Mais tarde, Margolus [1984] introduziu uma técnica relativamente simples para construir um
AC bidimensional reversível, denominada vizinhança de Margolus, que é uma ferramenta importante
para a criação de ACs bidimensionais reversíveis que satisfazem certas propriedades pré-estabelecidas;
além disso, sua técnica está relacionada tanto à Física quanto à Computação. Modelos sofisticados de
ACs reversíveis vem sendo desenvolvidos e utilizados para a simulação de sistemas termodinâmicos,
em especial os denominados lattice-gas automata, LGAs [Toffoli e Margolus, 1990], conforme
apresenta a Figura 7. Pode-se também citar aplicações às arquiteturas computacionais não-
convencionais, como por exemplo a computação baseada em colisões [Toffoli e Margolus, 1987].
Figura 7. Lattice-gas automaton.
18
A Figura 7 apresenta uma configuração de um lattice-gas automaton. Tais modelos discretos,
baseados em interações locais e de curto alcance, demonstram alta precisão na modelagem do
comportamento de gases e fluidos. De fato, dada uma configuração inicial, sua evolução pode ser
observada de forma exata [Toffoli e Margolus, 1990], sendo portanto superior às discretizações das
equações diferenciais parciais de Navier-Stokes, as quais admitem sempre um erro maior que zero.
19
Capítulo 3: Relações entre Autômatos Celulares Unidimensionais
Reversíveis e as Pré-Imagens de seus Blocos Básicos
Seja G:C→C a função global de transição de um AC reversível. Richardson [1972] demonstrou
que, nessas circunstâncias, a inversa G
-1
:C→C, também é um AC reversível de tal forma que G
-1
G =
GG
-1
= I
d
, onde I
d
é a função identidade global de transição no espaço correspondente. Tal resultado
mostra que, considerando um mapeamento local que induz a um processo global reversível, existe um
mapeamento local que induz ao processo global inverso. Assim, a conexão entre os mapeamentos
locais diretos e inversos se dá de forma indireta. Um problema ainda não completamente solucionado
diz respeito a tal conexão, isto é, sob quais condições é possível estabelecer uma conexão direta entre
os mapeamentos locais direto e inverso? É esta questão que procura-se responder, pelo menos
parcialmente, nas seções seguintes deste capítulo.
3.1 Definições
A seguir, apresentam-se algumas definições complementares ao Capítulo 1. Um bloco de
comprimento L é um conjunto ordenado b
0
b
1
...b
L-1
onde L∈
+
e b
i
∈S, onde
+
é o conjunto dos
números inteiros não negativos. Seja B
L
o conjunto de todos os blocos de comprimento L sobre S;
então, evidentemente, |B
L
| = |S|
L
, onde, para qualquer conjunto enumerável E, o operador |E| equivale à
cardinalidade de E. Dessa forma, o operador de evolução de bloco associado à função local de
transição de estados f:S
n
→S é dado por f:B
n
→B
1
: f(b
0
b
1
...b
n-1
) = b
i ,
b
i
∈S onde B
n
é denominado
conjunto dos blocos básicos de comprimento n. Como exemplo, seja S = {0, 1}, então B
2
={00, 01, 10,
11} e |B
2
|=4. Considerando N = (0, 1, ..., n-1), o operador global de transição de bloco pode ser
definido como G:B
L
→B
L
, aplicando-se f às todas as vizinhanças da configuração considerada. Por
exemplo, considerando n=3, tem-se que G(10101) = f(101)f(010)f(101)f(011)f(110). Finalmente, dado
um bloco b∈B
n
, o conjunto das pré-imagens de b é dado por f
-1
(b) e, conseqüentemente, a
cardinalidade do conjunto das pré-imagens de b é dado por |f
-1
(b)|.
3.2 O Parâmetro α de Caracterização Dinâmica
A previsão do comportamento dinâmico global de um AC a partir unicamente de sua função
local de transição de estados é um problema indecidível [Culik II et al, 1990]. Contudo, tal abordagem
se mostra útil quando o que se pretende é uma análise qualitativa da dinâmica de um dado AC, sem
necessariamente a análise de diagramas espaço-temporais ou mesmo bacias de atração. Diversos
parâmetros têm sido propostos para tanto [Binder, 1993; Langton, 1990; Li, 1991; Oliveira et al, 2001;
20
Voorhees, 1995; Wuensche, 1999; Zwick e Shu, 1995]. Todavia, independentemente de qual
característica dinâmica o parâmetro se propõe a medir, espera-se que tal medida seja equivalente
(numericamente igual) entre regras de uma mesma classe de equivalência dinâmica.
Considere-se a tripla (S, N, f), onde S = {0, 1,..., q-1}, q∈
+
e N = (0, 1,..., n-1), n∈
+
. O
conjunto de pré-imagens de b∈B
n
é dado por f
-1
:B
n
→B
2n-1
pois, qualquer que seja b∈B
n
:
f
-1
(b) = f
-1
(b
0
b
1
...b
n-1
) ≠ { }, ∃ b’∈B
2n-1
: f(b’) = f(b’
0
b’
1
...b’
n-1
)f(b’
1
b’
2
...b’
n
)...f(b’
n-1
b’
1
...b’
2n-2
) = b, e,
dessa forma, o número máximo de pré-imagens de B
n
é dado por |B
2n-1
| = q
2n-1
. No caso em que
b∈B
n
: |f
-1
(b)| = { }, isso implica que tal bloco básico não possui qualquer pré-imagem. Na Figura 8,
observam-se algumas árvores de pré-imagens dos blocos básicos para regras binárias, com dois
vizinhos, isto é, n=2.
Figura 8. Campos de bacias de atração das pré-imagens dos blocos fundamentais.
Na Figura 8, apresentam-se três campos de bacias de atração das pré-imagens dos blocos
básicos para as regras 8, 10 e 11, respectivamente, considerando-se S = {0, 1} e N = (0, 1). Para a
regra 8, o bloco básico 00 tem 5 pré-imagens, enquanto os demais obedecem a uma relação “um para
um”. Para a regra 10, o número de pré-imagens está igualmente distribuído entre os blocos básicos.
Finalmente, para a regra 11, nota-se que o bloco básico 00 não apresenta qualquer pré-imagem.
No atual contexto, uma pergunta natural que surge após observação da Figura 8 é: existiria
alguma relação entre as pré-imagens dos blocos básicos e reversibilidade de ACs unidimensionais? No
intuito de contribuir para solucionar esta questão, define-se o parâmetro α de caracterização dinâmica
como se segue:
21
∑
∈
−
−
=
∪
n
Bb
n
b
B
|})({|
||
1
1
12
f
α
(7)
A título de exemplo, considere a regra 11, onde S = {0, 1} e N = (0, 1). Assim, como n=2,
B
2
= {00, 01, 10, 11} e |B
2*2-1
| = |B
3
| = 2
3
= 8. Aplicando-se f
-1
a cada bloco básico b∈B
2
obtém-se:
{|f
-1
(00)|} = {0}, {|f
-1
(01)|} = {2}, {|f
-1
(10)|} = {2} e {|f
-1
(11)|} = {4}, conforme pode-se observar na
Figura 8. Assim, dado que a união de cada {|f
-1
(b)|} para todo b∈B
2
resulta na eliminação de um dos
valores 2, a soma dos valores restantes resulta em Σ{0, 2, 4} = 6 e, conseqüentemente, α = 6/8 = 0.75.
De fato, há uma relação entre α, a distribuição das pré-imagens dos blocos básicos, e
reversibilidade, de tal forma que, se um dado AC é reversível, então o número de pré-imagens para
cada bloco básico está igualmente distribuído e, conseqüentemente, α assume valor mínimo. Dessa
forma, estabelecem-se os seguintes teoremas:
Lema 1. Fixado k∈
+
, onde
+
é o conjunto dos números racionais não-negativos, seja
A = {a
1
, a
2
,..., a
n
}, a
i
∈
+
de tal forma que kaaA
n
=++=
∑
...
1
. Então
∑
A é mínima se, e somente
se, qualquer que seja a
i
∈A,
n
A
n
k
a
i
∑
== .
Demonstração. Fixado k∈
+
, seja A = {a
1
, a
2
,..., a
n
}, a
i
∈
+
, de tal forma que kaaA
n
=++=
∑
...
1
.
Se
∑
A
é mínima, então cada a
i
∈A assume valor mínimo a
min
, de tal maneira que n.a
min
= k ⇒
n
A
n
k
a
min
∑
==
. Analogamente, se a
1
= a
2
= ... = a
n
= a ⇒ n.a = k ⇒
min
a
n
A
n
k
a ===
∑
⇒
∑
A é
mínima. Q.E.D.
Teorema 1. Seja a tripla (
S, N, f), onde S = {0, 1,..., q-1}, q∈
+
e N = (0, 1,..., n-1), n∈
+
. Considere
α como definido em (7), B
n
como o conjunto dos blocos básicos de comprimento n, e f
-1
:B
n
→B
2n-1
a
função que produz as pré-imagens dos blocos básicos de comprimento n. Então α é mínimo e igual a
q
-n
se, e somente se, o número de pré-imagens está igualmente distribuído entre os blocos básicos.
Demonstração. Por hipótese, considere-se α mínimo, fixados n e q. Assim, α torna-se dependente
apenas de
∑
∈
−
∪
n
Bb
b |})({|
1
f
, que, pela hipótese, assume valor mínimo. Pelo Lema 1, tem-se que
qualquer que seja b∈B
n
, |f
-1
(b)| assume um mesmo valor. Assim
n
nn
n
q
BB
B
−
−
−
==
||||
||
12
12
α
.
22
Analogamente, fixados n e q, considere-se por hipótese que, para qualquer b∈B
n
, |f
-1
(b)| assume um
mesmo valor; conseqüentemente, pelo Lema 1, segue que
∑
∈
−
∪
n
Bb
b |})({|
1
f
é mínima e, portanto,
α é
mínimo. Q.E.D.
Teorema 2. Seja a tripla (S, N, f), onde S = {0, 1,..., q-1}, q
∈
+
e N = (0, 1,..., n-1), n∈
+
e
G:
B
L
→B
L
, L∈
+
, o operador global de evolução de bloco, com condição de contorno periódica.
Considere
α como definido em (7), B
n
como o conjunto dos blocos básicos de comprimento n, e
f
-1
:B
n
→B
2n-1
a função que produz as pré-imagens dos blocos básicos de comprimento n. Se G é
reversível, então o número de pré-imagens está igualmente distribuído entre os blocos básicos.
Demonstração. Considere, por absurdo, que o número de pré-imagens não está igualmente distribuído
entre os blocos básicos. Assim,
∃ b, d∈B
n
: |f
-1
(b)| - |f
-1
(d)| ≥ 1. Considere, sem perda de generalidade,
|f
-1
(b)| - |f
-1
(d)| = 1. Assim,
11
||
||
|)(
1
12
+=+=
−
−
n
n
n
q
B
B
b
1-
f|
. Dessa forma, seja c'∈B
2n-1
a pré-imagem
adicional, então f(c'
0
c'
1
... c'
n-1
)f(c'
1
c'
2
... c'
n
)...f(c'
n-1
c'
n
... c'
2n-2
) = b
0
b
1
...
b
n-1
e, dessa forma, G(c') = b
0
b
1
...b
n-1
f(c'
n
c'
n+1
... c'
0
)f(c'
n+1
c'
n+2
... c'
1
)...f(c'
2n-2
c'
0
... c'
n-2
). Assim, G(c')
pode assumir q
n-1
blocos distintos, coincidentes até a (n-1)-ésima posição a qualquer outro bloco
c
∈B
2n-1
: f(c
0
c
1
... c
n-1
)f(c
1
c
2
... c
n
) ... f(c
n-1
c
n
... c
2n-2
) = b
0
b
1
... b
n-1
. Uma vez dada a reversibilidade de
G, cada um dos q
n-1
blocos distintos está associado a exatamente uma das pré-imagens e, portanto, a
pré-imagem adicional é igual a uma das q
n-1
pré-imagens previamente consideradas, o que é uma
contradição! Logo, se G é reversível, então o número de pré-imagens está igualmente distribuído entre
os blocos básicos. Q.E.D.
Corolário. Fixados n e q, se G é reversível, então, pelos Teoremas 1 e 2,
α é mínimo.
Observe-se que, contrariamente ao que se poderia pensar em princípio, o fato de G ser
reversível (e, portanto, bijetora), não implica que cada bloco teria apenas uma pré-imagem. Afinal,
para q
n
blocos básicos, existem q
2n–1
pré-imagens destes no total, conforme a definição de f
-1
. A
questão é que
α não se relaciona diretamente com as pré-imagens das configurações globais, mas sim
com as pré-imagens dos blocos básicos. O Teorema 2 mostra que, se G é reversível, isso implica numa
certa distribuição dos blocos básicos, isto é, cada bloco básico tem o mesmo número de pré-imagens.
Em outras palavras, a dinâmica global reversível implica numa certa dinâmica local (não
23
necessariamente reversível) onde as pré-imagens dos blocos básicos estão igualmente distribuídas
entre os mesmos, qualquer que seja o AC unidimensional reversível considerado.
Assim como acontece com outros parâmetros de caracterização dinâmica (conforme
mencionado no início desta seção), o teorema a seguir prova que o valor do parâmetro
α é invariante
em uma mesma classe de equivalência dinâmica.
Teorema 3. Seja a tripla (S, N, f), onde S = {0, 1,..., q-1}, q
∈
+
e N = (0, 1,..., n-1), n∈
+
. Considere-
se
α como definido em (3), B
n
como o conjunto dos blocos básicos de comprimento n, e f
-1
:B
n
→B
2n-1
a
função que produz as pré-imagens dos blocos básicos de comprimento n. Então,
α assume um mesmo
valor entre regras de uma mesma classe de equivalência dinâmica.
Demonstração. Sejam C e R os operadores de Conjugação e Reflexão dados por (4). Então,
α = α
R
⇔
∑∑
∈
−
∈
−
=
∪∪
nn
BbBb
bb
'
11
|})'({||})({| ff
⇔ ∃ b, b’∈B
n
: b = b
0
b
1
...b
n-1
⇒ b’ = b
n-1
b
n-2
...b
0
. Assim,
definidos f:S
n
→S e o operador de evolução de bloco correspondente f:B
n
→B
1
, é claro que
|f
-1
(b)| = |Rf
-1
(b’)|, o que mantem α. Analogamente, α=α
C
⇔
∑
∑
∈
−
∈
−
=
∪∪
nn
BbBb
bb
'
11
|})'({||})({| ff
⇔
∃ b, b’∈B
n
: b = b
0
b
1
...b
n-1
⇒ b’ = (q-1-b
n-1
)(q-1-b
n-2
)...(q-1-b
0
), onde (.) é o operador de concatenação
de bloco (não confundir com produto). Logo |f
-1
(b)| = |Cf
-1
(b’)| e assim, preserva-se α. Aplicando-se os
mesmos argumentos anteriores, demonstra-se que
α se mantem também para a composição CR.
Q.E.D.
A Figura 9 apresenta os valores de
α para as 88 classes de equivalência no espaço elementar,
isto é S = {0, 1} e N = (-1, 0, 1). Nota-se que
α assume valor mínimo (α=0,125) para 12 regras, cujos
números são: 15, 30, 45, 51, 60, 90, 105, 106, 150, 154, 170 e 204. De fato, as regras 15, 51, 170 e 204
são reversíveis e, portanto, necessariamente, apresentam
α mínimo. Entretanto, regras não-reversíveis
que apresentam distribuição das pré-imagens dos blocos básicos equivalente à de regras reversíveis,
também apresentam
α mínimo. Ou seja, α mínimo é uma condição necessária à reversibilidade, porém
não suficiente. Surge naturalmente a seguinte questão (em aberto): é possível decidir sobre a
reversibilidade de um AC unidimensional considerando-se apenas análises relativas às pré-imagens de
seus blocos básicos? E, em caso afirmativo, quais são as condições necessárias e suficientes nesse
contexto? Conforme já mencionado, de forma geral trata-se de um problema indecidível para ACs de
duas ou mais dimensões [Kari, 1996]. Observa-se também que
α assume valor máximo (α=1,0)
somente para a regra 0 (ou para sua equivalente dinâmica, a regra 255). Isso ocorre devido ao fato de o
24
bloco básico 000 (ou 111 para a regra 255) apresentar todas as pré-imagens, acarretando que todos os
outros blocos básicos deixam de possuir qualquer pré-imagem.
Figura 9. Valores de α em função das classes de equivalência dinâmica do espaço elementar de regras.
A Figura 10 ilustra a distribuição do parâmetro α para S = {0, 1}, N = (-2, -1, 0, 1, 2), isto é,
regras unidimensionais com q=2 e n=5.
Figura 10. Distribuição de α para q =2 e n =5 e amostragem de 100.000 regras distintas.
25
Na Figura 10, a distribuição de
α é obtida para uma amostragem de 100.000 regras distintas do
espaço onde q=2 e n=5, o que lembra uma distribuição normal. A título de comparação, a Figura 11
mostra a distribuição dos parâmetros Z [Wuensche e Lesser, 1992],
λ [Langton, 1990], Sensitividade e
Domínio da vizinhança [Oliveira et al, 2001], nas mesmas condições da Figura 10. Nota-se claramente
a maior quantidade de valores que o parâmetro
α pode assumir, apesar de não se compreender bem
ainda as implicações de tal característica.
Figura 11. Distribuição dos parâmetros Z, λ, Sensitividade e Domínio da Vizinhança para q =2, n=5 e
amostragem de 100.000 regras distintas.
Dentre as aplicações do parâmetro
α, além é claro de condição necessária à reversibilidade de
ACs unidimensionais, conjectura-se, com base em experimentos numéricos, sua aplicação como
medida de grau de reversibilidade. Contudo, mais estudos fazem-se necessários para uma melhor
compreensão e interpretação, tanto das propriedades do parâmetro
α quanto de suas aplicações.
26
Capítulo 4: Autômatos Celulares Conservativos e Reversíveis
Este capítulo investiga propriedades dos ACs unidimensionais conservativos e reversíveis
(ACCRs). Deste ponto em diante, considera-se apenas a classe dos ACCRs unidimensionais, a menos
quando explicitamente especificado.
ACs unidimensionais conservativos e reversíveis são aqueles que satisfazem tanto as condições
(3) de Boccara-Fukś [2002] quanto as condições de Hedlund [1969], isto é, a função global de
transição do AC deve ser conservativa e bijetora. Casos triviais de ACCRs podem ser construídos
considerando-se as funções locais de transição de estados como funções deslocamento (shift) e
identidade, pois, no primeiro caso, ocorrem apenas deslocamentos à esquerda ou à direita nas
configurações e, no segundo caso, ocorre a replicação da configuração.
Dessa forma, considere-se a tripla (S, N, f), onde S = {0, 1} e N = (0, 1), isto é, o espaço de
regras de dois estados e vizinhança de comprimento 2. Uma busca exaustiva neste espaço enumera
rapidamente os ACCRs, os quais apresentam os seguintes números de regras: 10 (identidade) e 12
(shift); para espaços de maior cardinalidade, a enumeração dos ACs unidimensionais reversíveis pode
ser estabelecida através de técnicas algébricas [Boykett, 2004]. Considerem-se ainda os operadores de
evolução de bloco f:
B
n
→B
1
e g:B
m
→B
1
relacionados, respectivamente, às funções locais de transição
f:S
n
→S com N = (0, 1, ..., n-1), n∈
+
e g:S
m
→S com N = (0, 1, ..., m-1), m∈
+
. A composição fg
pode ser obtida a partir de f
g, a qual se define como segue:
fg:B
m+n-1
→B
1
: fg(b
0
b
1
...b
m+n-2
) = f(g(b
0
b
1
...b
m-1
)g(b
1
b
2
...b
m
)...g(b
n-1
b
n
...b
m+n-2
))
(8)
Note-se que deve-se aplicar g a todas as vizinhanças de comprimento m dos blocos de comprimento n.
Dessa forma, ao aplicar g ao (n-1)-ésimo elemento do bloco, são necessários ainda m-1 elementos para
completar a vizinhança de m elementos sobre a qual g é definida. Assim, os blocos considerados para a
composição f
g devem ter comprimento m+n-1, isto é, pertencem a B
m+n-1
.
Sejam os ACCRs acima mencionados, cujos números são W(f)=10 e W(g)=12. Dessa forma, os
operadores de evolução de bloco f e g, associados respectivamente às funções locais de transição f e g,
podem ser escritos como:
f(00) = 0, f(01) = 1, f(10) = 0, f(11) = 1
g(00) = 0, g(01) = 0, g(10) = 1, g(11) = 1
(9)
27
Assim, a composição f
g é dada por:
fg(000) = f(g(00)g(00)) = f(00) = 0
fg(001) = f(g(00)g(01)) = f(00) = 0
fg(010) = f(g(01)g(10)) = f(01) = 1
fg(011) = f(g(01)g(11)) = f(01) = 1
fg(100) = f(g(10)g(00)) = f(10) = 0
fg(101) = f(g(10)g(01)) = f(10) = 0
fg(110) = f(g(11)g(10)) = f(11) = 1
fg(111) = f(g(10)g(01)) = f(11) = 1
(10)
Logo, W(f
g) = 11001100
2
= 204, que, conforme visto anteriormente, trata-se de um ACCR do
espaço elementar. De fato, uma vez que f:S
n
→S e g:S
m
→S definem os ACs F e G conservativos e
reversíveis, isso implica que suas funções globais de transição são conservativas e bijetoras. Dado que
a composição de funções bijetoras é uma função bijetora, e que a conservabilidade também se preserva
entre composições [Boccara e Fukś, 2002], a composição f
g: S
m+n-1
→S é, portanto, conservativa e
bijetora, induzindo assim à função global de transição (conservativa e reversível) F
G.
Considerando-se ainda S = {0, 1} e N = (0, 1), podem-se definir as seguintes composições: f
f
= f
2
, gg = g
2
, e, finalmente, fg = gf (esta última igualdade demonstrada no Teorema 4 a seguir),
tais que W(f
f) = 10101010
2
= 170, W(gg) = 1111000
2
= 240 e W(fg) = W(gf) = 11001100
2
= 204.
Lema 2. Sejam S = {0, 1} e N = (0, 1), então f
g = gf.
Demonstração. Sejam S = {0, 1} e N = (0, 1). Basta aplicar a definição (8) para f
g e gf e notar que
W(f
g) = W(gf), o que resulta fg = gf.
Teorema 4. Sejam as triplas (S, N, f) e (S, N, g), onde S = {0, 1} e N = (0, 1). Então
f
n
g
m
= g
m
f
n
quaisquer que sejam m, n∈
+
.
Demonstração. Pelo Lema 2, segue que: f
g = gf ⇒ f
n
g
m
= f
n-1
fgg
m-1
= f
n-1
gfg
m-1
=
f
n-2
fgfgg
m-2
= f
n-2
ggffg
m-2
= ... = g
m
f
n
. Q.E.D.
28
Nota-se que as composições anteriormente apresentadas definem todos os ACCRs do espaço
elementar de regras. De fato, buscas exaustivas considerando-se n
∈{2, 3, 4, 5, 6} e q=2; n∈{2, 3, 4} e
q=3; e n
∈{2, 3} e q=4 indicam que todo ACCR é uma composição dos ACCRs para n=2 e um dado q.
Conjectura-se pois que:
Conjectura 1. Sejam S = {0, 1,..., q-1}, q
∈
+
e N∈
n
. A tripla (S, N, ζ) define um ACCR se, e
somente se,
n
y
k
yy
fff ...
21
21
=
ζ
onde k∈
+
, y
i
∈
+
, f
i
é uma função local de transição f:S
2
→S
que define um ACCR nesse espaço e
1
1
−=
∑
=
ny
n
i
i
.
Em outras palavras, a Conjectura 1 afirma que dado um ACCR, pode-se sempre defini-lo como
uma composição dos ACCRs do espaço onde a vizinhança tem comprimento n=2, para um dado q, os
quais podem ser encontrados através de uma busca exaustiva [Boykett, 2004]. Umas das implicações
da Conjectura 1 é obviamente verdadeira, isto é, que qualquer composição de ACCRs sempre é um
ACCR. Contudo, existe algum ACCR que não seja composição dos ACCRs com n=2 para um dado q?
Experimentos numéricos (citados anteriormente) sugerem que a resposta é negativa, contudo, uma
demonstração ou contra-exemplo ainda se faz necessário. De fato, uma demonstração para tal
conjectura permitiria estabelecer uma enumeração entre os comprimentos das vizinhanças e a
quantidade de ACCRs no espaço correspondente, os quais podem ser facilmente identificados através
do cálculo das composições das funções de transição de estados com n=2.
A Tabela 1 apresenta todos os ACCRs obtidos de forma analítica (através do cálculo das
composições) e experimentalmente (através de buscas exaustivas em todos os espaços
correspondentes). Ambas as abordagens resultaram no mesmo conjunto de regras. A Conjectura 1
baseia-se fortemente nesse resultado.
N q Composições Qtd. W(.)
2 2 f, g 2 10, 12
3 2 f
2
, fg, g
2
Onde fg = gf
3 170, 204, 240
4 2 f
3
, f
2
g, fg
2
, f
3
4 43690, 52428, 61680, 65280
5 2 f
4
, f
3
g, f
2
g
2
, fg
3
, g
4
5 2863311530, 3435973836, 4042322160, 4278255360,
4294901760
6
2
f
5
, f
4
g, f
3
g
2
, f
2
g
3
, fg
4
, g
5
6
14756797279864794316, 14757395258967641292,
17361641481138401520, 18374966859414961920,
18446462603027742720, 18446744069414584320
2 3 f, g 2 15897, 19305
3 3 f
2
, fg, g
2
3 6159136430181, 7479532539765, 7625403764901
29
Onde fg = gf
2 4 f, g, h, i 4 3840206052, 4120966560, 4008592452, 4289352960
3
4
f
2
, fg, g
2
, fh, gh, h
2
, fi, gi, hi, i
2
Onde, além da comutatividade, vale:
gh = fi (basta efetuar as
composições conforme definidas em
(5)).
9
304252469246956743802546707821345694948,
326496608407547273709880145194317313440,
326937960348609920534832483808753787040,
317593414314454845085324736983695508548,
339837553475045374992658174356667127040,
317596875792875899220185137553843962948,
339837553475045374992658174356667127040,
340278905416108021817610512971103600640,
339841014953466429127518574926815581440,
340282366894529075952470913541252055040
Tabela 1. ACCRs obtidos de forma analítica e experimental, onde n é o comprimento da vizinhança considerada
(iniciando-se com n=2, onde as regras não são composições de nenhuma outra), q é a quantidade de estados,
Qtd. é a quantidade de ACCRs no espaço considerado, e W(.) é referente ao número da regra, segundo a notação
de Wolfram.
Adicionalmente, em particular, estabelece-se a enumeração dos ACCRs binários como a
seguir:
Conjectura 2.
Sendo S = {0, 1} e N = (0, 1), a tripla (S, N, ζ) define um ACCR se, e somente se,
ζ = f
x
g
y
onde x
,
y∈
+
: x+y = n-1 e f:S
2
→S, g:S
2
→S funções locais de transição tais que W(f) = 10 e
W(g) = 12. Note-se a relação com o binômio de Newton, uma vez que f
g = gf.
Finalmente, com base na representação q-ária dos ACCRs apresentados na Tabela 1, apresenta-
se ainda a seguinte conjectura:
Conjectura 3. Sejam S = {0, 1} e N = (0, 1). Então um AC é conservativo e reversível se, e somente
se, a representação binária de seu número de regra é da forma [1
x
0
x
]
y
, onde x, y∈
+
: xy = 2
n-1
.
ACs reversíveis da forma [1
x
0
x
]
y
e [0
x
1
x
]
y
, onde x, y∈
+
: xy = 2
n-1
foram identificadas em
[Kronemberger, 2008] como ´regras reversíveis primitivas´. Evidentemente, ACs da forma [0
x
1
x
]
y
não
satisfazem as condições de Boccara-Fukś, pois f(0,...,0) = 1, e conseqüentemente, não pertencem à
classe dos ACCRs.
30
A título de exemplo, considere S = {0, 1}, q=2 e n=4 ⇒ [1]
x
[0]
x
]
y
: xy = 2
4-1
. As soluções da
equação são {{1, 8}, {2, 4}, {4, 2}, {8, 1}}, o que implica nas seguintes representações binárias:
1010101010101010
2
, 1100110011001100
2
, 1111000011110000
2
e 1111111100000000
2
, que são,
respectivamente, as regras de números 43690, 52428, 61680 e 65280, conforme encontram-se na
Tabela 1. Uma demonstração para a Conjectura 3 permitiria estabelecer com segurança e eficiência um
ACCR binário com qualquer comprimento de vizinhança. Por exemplo, um ACCR binário de
vizinhança 9 tem seu número representado por:
1111111111111111111111111111111100000000000000000000000000000000111111111111111111
1111111111111100000000000000000000000000000000111111111111111111111111111111110000
0000000000000000000000000000111111111111111111111111111111110000000000000000000000
0000000000111111111111111111111111111111110000000000000000000000000000000011111111
1111111111111111111111110000000000000000000000000000000011111111111111111111111111
1111110000000000000000000000000000000011111111111111111111111111111111000000000000
00000000000000000000
2
31
Capítulo 5: Algumas Relações entre Autômatos Celulares Lineares
e Autômatos Celulares Conservativos e Reversíveis
Um AC é linear se sua função local de transição de estados é uma função linear [Kari, 2005].
Tal propriedade facilita significativamente a análise rigorosa de ACs, em particular em provas que
certos problemas indecidíveis para ACs em geral (tais como sobrejetividade e injetividade) não o são
para ACs lineares (ACLs) [Kari, 2005].
Um ACL pode ser definido como se segue. Sendo S = {0, 1, ... , q-1}, q∈
+
um conjunto finito
de estados, e f:S
n
→S uma função linear, então ∀(x
1
, x
2
, ... , x
n
)∈S
n
, tem-se que
∑
=
=
n
i
iin
xaxxxf
1
21
),...,,(
,
(11)
onde a
1
, a
2
, … , a
n
∈ S. Em particular pode-se considerar S =
m
onde
m
é o conjunto dos números
inteiros módulo m, m∈
+
. Por exemplo, as regras 10 = 1010
2
e 12 = 1100
2
com S = {0, 1} e n=2 são
lineares, pois vale:
f(0,0) = 0 = 0.0 + 1.0; f(0,1) = 1 = 0.0 + 1.1
f(1,0) = 0 = 0.1 + 1.0; f(1,1) = 1 = 0.1 + 1.1
f(0,0) = 0 = 1.0 + 0.0; f(0,1) = 0 = 1.0 + 0.1
f(1,0) = 1 = 1.1 + 0.0; f(1,1) = 1 = 1.1 + 0.1
(
12)
Portanto, para a regra 10, a
1
=0 e a
2
=1 e para a regra 12, a
1
=1 e a
2
=0. Vale notar que uma propriedade
dos ACLs que é particularmente útil no desenvolvimento deste trabalho é o fato de que a composição
de regras lineares também é uma regra linear [Kari, 2005].
Dado o contexto do presente trabalho, surge naturalmente a seguinte questão: existiria alguma
relação entre ACLs e ACCRs? Observe-se, por exemplo, que, para S = {0, 1, 2, 3} e n=2, existem
quatro ACCRs, mas somente dois deles são também ACLs. De fato, as regras de número
3840206052 = 3210321032103210
4
(Identidade),
4289352960 = 3333222211110000
4
(Deslocamento para a direita),
4120966560 = 3311220033112200
4
e
4008592452 = 3232323210101010
4
32
são ACCRs, mas somente a primeira e a segunda também são ACLs. Assim, aplicando (11) a estas,
obtém-se a
1
=0, a
2
=1 e a
1
=1, a
2
=1 respectivamente; por outro lado, para as duas regras restantes, não
há soluções que satisfazem (11) e, portanto, elas são não-lineares.
Figura 12. Interseção das classes dos ACCs, ACRs e ACLs.
Na Figura 12 observa-se que a classe dos ACCRs pode ser particionada em duas outras
subclasses: ACCRs não-lineares e ACCRs lineares. A Tabela 2 apresenta as regras com número
mínimo, para cada uma das classes de ACs da Figura 12.
Classe Número da regra n q
ACR 3 2 2
ACC 184 3 2
ACL 0 2 2
ACR linear 43690 4 2
ACC linear 6924717700245 3 3
ACCR linear 10 2 2
ACCR não-linear 4008592452 2 4
Tabela 2. Regras de números mínimo de cada uma das classes de ACs apresentadas na Figura 12.
33
Experimentos numéricos sugerem que ACCRs lineares preservam a densidade de estados
durante as iterações, isto é, a número de vezes que cada estado ocorre na configuração inicial.
Consequentemente, a soma dos estados também preservada. Assim, considerando um ACCR linear e
uma configuração inicial qualquer, após a k-ésima iteração, a configuração obtida será uma
permutação da configuração inicial. Um exemplo desta propriedade pode ser observado a seguir,
considerando o ACCR linear 3840206052, onde q=4, N = (0, 1) e configuração inicial 303212103 (o
símbolo
Æ indica a próxima iteração):
303212103
Æ 032121033 Æ 321210330 Æ 212103303 Æ 121033032
(14)
Entretanto, ao se considerar ACCRs não-lineares, a densidade dos estados não é
necessariamente preservada. Nesse sentido, observe, por exemplo, a evolução temporal do ACCR não-
linear 326496608407547273709880145194317313440, para q=4 e N = (0, 1, 2), a partir da
configuração inicial 303212103:
303212103
Æ 230301231 Æ 121032132 Æ 012303303 Æ 321231210
(14)
Evidências computacionais sugerem uma dinâmica espaço-temporal distinta entre ACCRs
lineares e não-lineares, conforme pode ser observado na Figura 13.
Figura 13. Diagramas espaço-temporais, por 100 iterações, respectivamente, para o ACCR linear
3840206052
(N=(0, 1) e q=4) e para o ACCR não-linear
326496608407547273709880145194317313440 (N=(0, 1, 2) e
q=4), a partir de configuração inicial aleatória de comprimento 100.
34
ACCRs não-lineares apresentam fluxos que se interceptam, o que não ocorre para ACCRs
lineares. De fato, experimentos numéricos sugerem que o número de fluxos que se interceptam é
diretamente proporcional ao número de estados. Para ACCRs não-lineares, variando-se n e q, é
possível observar diferentes composições de Identidades e Deslocamentos (esquerda e direita), com
diferentes ângulos de interceptação, num mesmo diagrama espaço-temporal. Uma propriedade
interessante observada na dinâmica local dos ACCRs não-lineares é o fato de que existem transições
de estado que levam a um estado não presente na vizinhança considerada. Por exemplo, considerando-
se as regras apresentadas na Figura 13, o ACCR não-linear apresenta a transição de estado f(3,2,1) = 0.
Tal situação não foi observada para ACCRs lineares analisados e foi observada para todos os ACCRs
não-lineares analisados e, de fato, é demonstrada no Teorema 5 que segue:
Teorema 5. Seja (S, N, f) um ACCR unidimensional, onde S = {0, 1, …, q-1}, N∈Z
n
, e f:S
n
→S. Seja
f(q
1
, q
2
, …, q
n
) = q
n+1
, onde q
n+1
∉{q
1
, q
2
, …, q
n
} e q
i
∈S, uma transição local de estados. Então, (S, N,
f) é um ACCR não-linear.
Demonstração. Assuma-se, por contradição, que (S, N, f) é um ACCR unidimensional linear. Então,
por definição, as soluções para (4) são dadas por: {(0, 0, ... , 1), (0, 0, ... , 1, 0), ... , (1, 0, 0, ... , 0)}.
Aplicando cada uma destas soluções à transição local f(q
1
, q
2
, …, q
n
) = q
n+1
, resulta que:
q
n
= q
n+1
, q
n-1
= q
n+1
, …, q
1
= q
n+1
. Contradição! Portanto, (S, N, f) é um ACCR unidimensional não-
linear.
Corolário. Se (S, N, f) é um ACCR unidimensional linear, então, toda transição local de estados
satisfaz: f(q
1
, q
2
, …, q
n
) = q
n+1
, onde q
n+1
∈{q
1
, q
2
, …, q
n
} e q
i
∈S.
Dessa forma, considerando-se qualquer ACCR unidimensional, basta verificar se suas
transições locais satisfazem ou não o Teorema 5, o que torna possível classificar sua natureza como
linear ou não-linear. Foi observado também que a representação q-ária das regras de ACCRs lineares
pode ser escrita através da repetição de um único bloco, por exemplo, o ACCR linear de número
6159136430181, com q=3 e n=3, pode ser escrito como 21021021021021021021021
3
, ou seja, [210]
8
(assumindo-se que o expoente indica o número de repetições do bloco). Entretanto, com relação a
ACCRs não-lineares, são necessários pelo menos dois blocos distintos em sua representação q-ária.
Por exemplo, a representação q-ária do ACCR não-linear de número
317596875792875899220185137553843962948, com q=3 e n=3, é
3232323232323232323232323232323210101010101010101010101010101010
4
, ou, de forma
reduzida: [32]
16
[10]
16
. De fato, a representação q-ária de ACCRs lineares pode ser generalizada
facilmente; contudo, com relação a ACCRs não-lineares, a quantidade de blocos distintos a serem
35
considerados aumenta conforme o número de estados aumenta. Além disso, a posição dos blocos
também se torna importante. Análises teóricas indicam que é possível associar o problema da
representação q-ária dos ACCRs a um grupo algébrico de permutações, o que permitiria, além da
obtenção de uma fórmula geral para a representação q-ária, uma análise de simetrias entre seus
elementos. De qualquer forma, faz-se necessária uma fomalização completa da dinâmica espaço-
temporal de ACCRs lineares e não-lineares, incluindo propriedades tais como a preservação de
densidade de estados para ACCRs lineares. Acredita-se, assim como no caso anterior, que a introdução
de técnicas matemáticas mais gerais possam efetivamente solucionar tais questões.
36
Capítulo 6: Dinâmica dos Autômatos Celulares Conservativos e
Reversíveis
ACCRs são regidos por leis de conservação de quantidades e reversibilidade, o que implica em
severas restrições na dinâmica de evolução espaço-temporal. De fato, qualquer que seja o ACCR, seu
campo de bacias de atração conterá apenas órbitas periódicas impostas pela reversibilidade (i.e.,
bijeção da função global de transição) e, além disso, cada órbita periódica conterá apenas
configurações que preservam a soma total de estados (i.e., definição de conservabilidade) ou que
preservam também a densidade de estados (considerando-se ACCRs lineares). A Figura 14 ilustra um
caso particular do espaço de estados de um ACCR linear.
Figura 14. Campo de bacias de atração do ACCR 7625403764901, para q=3 e n=3.
Nota-se claramente na Figura 14 que a topologia do espaço de estados é induzida pelas leis de
conservação e reversibilidade, uma vez que apresenta somente órbitas periódicas conservativas. Uma
transformação que substitua a configuração pela soma de seus estados reduz o espaço de estados a um
conjunto de pontos fixos, como ilustra a Figura 15.
37
Figura 15. Campo de bacias de atração do ACCR 7625403764901, para q=3 e n = 3, reduzido a um conjunto de
pontos fixos.
De fato, considerando a Conjectura 1, intuitivamente espera-se uma dinâmica espaço-temporal
trivial dos ACCRs, pois qualquer ACCR é uma composição de ACCRs triviais, os quais representam a
identidade ou deslocamentos no espaço onde n=2, fixado q. Contudo, nenhuma conclusão pode ser
estabelecida ainda e mais estudos tornam-se necessários nesse sentido.
Experimentos numéricos considerando as regras da Tabela 1 sugerem que todo ACCR
apresenta dinâmica trivial, isto é, composta apenas de funções identidade e deslocamentos. Fixando-se
q, a variação de n pode implicar em maior velocidade no deslocamento das partículas, conforme
evidencia a Figura 16.
38
Figura 16. Diagramas espaço-temporais, em 100 iterações, para as regras de número 170 (n=3 e q=2) e
2863311530 (n=5 e q=2), para uma configuração inicial aleatória de comprimento 100.
Na Figura 16, apresentam-se, respectivamente, os diagramas espaço-temporais das regras de
número 170, com n=3
e q=2, e 2863311530, com n=5 e q=2. Ambas as dinâmicas são qualitativamente
equivalentes, embora o segundo caso apresente maior velocidade de deslocamento das partículas,
justamente devido à maior vizinhança de sua função local de transição de estados.
Uma análise dos diagramas espaço-temporais das classes de ACs estudadas neste trabalho
sugere uma classificação dinâmica qualitativa, distinta das quatro classes listadas anteriormente,
sugerindo uma certa ordem de complexidade, conforme a seguir: ACCRs lineares, ACCRs não-
lineares, ACRs, ACCs, e ACs de forma geral. As Figuras de 17 a 21 apresentam diagramas espaço-
temporais, bem como campos de bacias de atração para ACs de cada uma dessas classes, de forma a
evidenciar a classificação.
39
Figura 17. Diagrama espaço-temporal para o ACCR linear 6159136430181 (n=3 e q=3)
para uma configuração inicial aleatória de comprimento 100 e 100 iterações (à esquerda), e campo de bacias de
atração incompleto (à direita).
Figura 18. Diagrama espaço-temporal para o ACCR não-linear
317596875792875899220185137553843962948 (n=3 e q=4) para uma configuração inicial aleatória de
comprimento 100 e 100 iterações (à esquerda), e campo de bacias de atração incompleto (à direita).
40
Figura 19. Diagrama espaço-temporal para o ACR 1079 (n=2 e q=3) para uma configuração inicial aleatória de
comprimento 100 e 100 iterações (à esquerda), e campo de bacias de atração incompleto (à direita).
Figura 20. Diagrama espaço-temporal para o ACC 7206774392253 (n=3 e q=3) para uma configuração inicial
aleatória de comprimento 100 e 100 iterações (à esquerda), e campo de bacias de atração incompleto (à direita).
41
Figura 21. Diagrama espaço-temporal para o AC 110 elementar (n=3 e q=2) para uma configuração inicial
aleatória de comprimento 100 e 100 iterações (à esquerda), e campo de bacias de atração incompleto (à direita).
Analisando-se as figuras anteriores, as seguintes observações podem ser feitas:
•
Figura 17 (ACCR linear): para qualquer configuração, tanto a densidade dos estados,
quanto sua soma são preservadas durante a evolução do sistema e também que o diagrama
espaço-temporal é composto de deslocamentos à esquerda; portanto, apresenta dinâmica
trivial. Outra característica importante é a ausência de configurações Garden-of-Eden,
devido à reversibilidade.
•
Figura 18 (ACCR não-linear): a soma dos estados é preservada durante as iterações do
sistema, contudo, a densidade não o é. Além disso, o diagrama espaço-temporal apresenta
fluxos que se interceptam. Outra característica importante é a ausência de configurações
Garden-of-Eden, devido à reversibilidade.
•
Figura 19 (ACR): nem a soma dos estados, nem sua densidade são preservadas durante a
iteração do sistema; contudo, é claro que, considerando qualquer AC reversível, as únicas
estruturas encontradas em seus campos de bacias de atração são ciclos (e, em particular,
pontos fixos) a partir de qualquer configuração global. Intuitivamente, o diagrama espaço-
temporal também apresenta maior complexidade que os anteriormente apresentados. Outra
característica importante é a ausência de configurações Garden-of-Eden, devido à
reversibilidade.
•
Figura 20 (ACC): a soma dos estados é preservada durante as iterações (por definição),
entretanto, a densidade de estados não é preservada. Nota-se também que o campo de
42
bacias de atração é constituído por ciclos com transientes (que podem até ser
arbitrariamente longos, apesar de não ser este o caso exemplificado), e também
configurações com mais de uma pré-imagem (devido à não-reversibilidade), logo,
apresenta configurações Garden-of-Eden [Moore, 1962] e [Myhill, 1963].
•
Figura 21 (AC genérico): nem a soma dos estados, nem a densidade dos mesmos é
preservada durante as iterações. Além disso, a estrutura do campo de bacias de atração não
sofre restrições (a menos das existentes na própria definição formal dos ACs [Hedlund,
1969]) e o diagrama espaço-temporal pode apresentar estruturas localizadas complexas e
longos transientes [Wolfram, 2002]. Vale notar que o AC mostrado pertence à Classe-IV de
Wolfram e é computacionalmente universal [Wolfram, 2002], além disso, apresenta
configurações Garden-of-Eden.
A Tabela 3 sintetiza as observações acima apresentadas:
Classe Propriedade
Conserva a soma
dos estados
Apresenta configurações
Garden-of-Eden
Conserva a densidade dos
estados
ACCR linear SIM NÃO SIM
ACCR não-linear SIM NÃO NÃO
ACR NÃO NÃO NÃO
ACC SIM SIM NÃO
AC genérico NÃO SIM NÃO
Tabela 3. Propriedades por classe de ACs.
Sabe-se que tanto ACRs [Morita, 2007] quanto ACCs [Moreira, 2003] e ACs [Wolfram, 2002]
podem apresentar computabilidade universal. ACCRs lineares são de fato demasiado simples e
provavelmente não apresentam tal propriedade. Dessa forma, surgem naturalmente as seguintes
questões: existiriam ACCRs não-lineares computacionalmente universais? E que linguagem são
capazes de reconhecer? De fato, análise dos diagramas espaço-temporais de ACCRs não-lineares, para
uma quantidade relativamente pequena de estados, sugere a não existência de um ACCR não-linear
que apresente tal propriedade, uma vez que as dinâmicas apresentadas são demasiado simples para
permitirem a modelagem de mecanismos que emulem a Máquina de Turing. Contudo, nada ainda
pode-se afirmar com relação à dinâmica espaço-temporal de ACCRs não-lineares considerando-se um
maior número de estados. Assim, tal qual outros pontos aqui discutidos, essa questão ainda demanda
investigações adicionais.
43
Capítulo 7: Considerações Finais
O presente trabalho expôs brevemente conceitos relacionados a ACs: conservabilidade,
reversibilidade, linearidade e, em particular, a classe dos ACCRs lineares e não-lineares. Com relação
à reversibilidade de ACs unidimensionais, propôs-se um parâmetro de caracterização dinâmica,
denominado parâmetro α, o qual relaciona a distribuição das pré-imagens dos blocos básicos à
reversibilidade, de tal forma que, para um AC unidimensional reversível, o número de pré-imagens
dos blocos básicos está igualmente distribuído e, conseqüentemente, α assume valor mínimo para o
espaço correspondente. Com isso, estabeleceu-se uma condição necessária, porém não suficiente, à
reversibilidade de ACs unidimensionais, e levantou-se a seguinte questão fundamental: é possível
decidir sobre a reversibilidade de um AC unidimensional considerando-se apenas análises relativas às
pré-imagens de seus blocos básicos? Caso afirmativo, quais seriam as condições necessárias e
suficientes nesse contexto? Uma outra questão está relacionada à existência e formulação generalizada
para o parâmetro α, no sentido de relacionar a distribuição das pré-imagens dos blocos fundamentais
para outros espaços de regras de maior dimensão. Ainda com relação ao parâmetro α, observou-se sua
distribuição nos espaços de regras, a qual lembra a distribuição normal, e com granularidade
consideravelmente maior que outros parâmetros de caracterização dinâmica considerados. Além do
parâmetro α estar evidentemente relacionado a uma condição necessária à reversibilidade de ACs
unidimensionais e, de forma geral, estar relacionado à condição necessária para regras que apresentam
uma distribuição particular das pré-imagens dos blocos básicos, conjecturou-se sobre sua possível
utilização para a definição de uma medida que caracterize o grau de reversibilidade de uma regra;
contudo, nenhuma evidência empírica satisfatória foi encontrada nesse sentido.
Apresentou-se também um estudo das propriedades dos ACCRs. Através de resultados
numéricos e argumentos teóricos, conjecturou-se que todo ACCR é uma composição dos ACCRs no
espaço de vizinhança de comprimento n=2. Ressalte-se que uma demonstração para tal conjectura
permitiria estabelecer uma enumeração entre os comprimentos das vizinhanças e a quantidade de
ACCRs no espaço correspondente, os quais seriam identificados através do cálculo das composições
das funções de transição de estados onde n=2, para um dado q. Com base nessa conjectura calcularam-
se diversos ACCRs, os quais também foram identificados através de buscas exaustivas. Ainda com
base nos ACCRs identificados, estabeleceu-se uma fórmula empírica para enumeração dos ACCRs
binários, de tal maneira que, dado n, pode-se facilmente enumerar todos os ACCRs binários daquele
espaço.
Por fim, fez-se breve análise da dinâmica espaço-temporal dos ACs, bem como da topologia de
suas bacias de atração, claramente induzidas pelas leis de conservação e reversibilidade. Finalmente.
conjecturou-se, com base em experimentos numéricos e observações teóricas, que todo ACCR linear
apresenta dinâmica espaço-temporal trivial e, conseqüentemente, não podem apresentar
44
computabilidade universal, característica encontrada tanto em ACs conservativos quanto em ACs
reversíveis. Contudo, com relação a ACCRs não-lineares, desconhece-se sua dinâmica espaço-
temporal considerando-se uma grande quantidade de estados e, portanto, mais estudos fazem-se
necessários com relação às suas capacidades computacionais.
A presente pesquisa levou a diversos questionamentos, alguns deles ainda sem respostas
satisfatórias, necessitando-se assim, de continuidade. As Conjecturas 1, 2 e 3 permanecem em aberto,
bem como uma fomalização da dinâmica espaço-temporal de ACCRs lineares e não-lineares,
incluindo propriedades tais como a preservação de densidade de estados para ACCRs lineares. Estudos
recentes sugerem soluções via aplicação de técnicas de dinâmica simbólica e topológica, que
consideram ACs definidos sobre espaços topológicos contínuos. De qualquer forma, um estudo
aprofundado tanto de dinâmica simbólica, quanto das áreas sob a qual a mesma é fundamentada, torna-
se necessário ao avanço deste trabalho.
45
Referências Bibliográficas
[Amoroso e Patt, 1972] S. Amoroso e Y. N. Patt. “Decision Procedures for Surjectivity and Injectivity
of Parallel Maps for Tesselation Structures”, J. Comp. and Sys. Sc., 6:448-464, 1972.
[Binder, 1993] P. Binder. “A Phase Diagram for Elementary Cellular Automata”, Complex Systems,
7:241–247, 1993.
[Boccara, 2005] N. Boccara. “Eventually Number-Conserving Cellular Automaton Rules”,
arXiv:cond-mat/0410563v2, (2005).
[Boccara e Fukś, 2002] N. Boccara e H. Fukś. “Number conserving cellular automaton rules”, Fund.
Inform, 52:1–13, 2002.
[Boykett, 2004] T. Boykett. “Efficient exhaustive listings of reversible one dimensional cellular
automata”, Theoretical Computer Science, 325:215–247, 2004.
[Burks, 1970] A. W. Burks. “Essays on Cellular Automata”, Technical Report, Univ. of Illinois,
Urbana, 1970.
[Culik II et al, 1990] K. Culik II, L. Hurd e S. Yu. “Computation Theoretic Aspects of Cellular
Automata”, Physica D, 45:357–378, 1990.
[Hattori e Takesue, 1991] T. Hattori e S. Takesue. “Additive conserved quantities in discrete-time
lattice dynamical systems”, Physica D, 49:295–322, 1991.
[Hedlund, 1969] G. Hedlund. “Endomorphisms and automorphisms of shift dynamical systems”,
Math. Systems Theory 3:320–375, 1969.
[Kari, 1994] J. Kari. “Reversibility and Surjectivity Problems of Cellular Automata”. Journal of
Comput. Syst. Sci, 48(1):149–182, 1994.
46
[Kari, 1996] J. Kari. “Representation of reversible cellular automata with block permutations”. Math.
Systems Theory 29:47–61, 1996.
[Kari, 2005] J. Kari. “Theory of cellular automata: A survey”, Theoretical Computer Science, 334:3–
33, 2005.
[Kronemberger, 2008] G. Kronemberger. “Em busca de um algoritmo construtivo para autômatos
celulares reversíveis: A abordagem das regras primitivas e derivadas”, Dissertação de
Mestrado em Engenharia Elétrica, Universidade Presbiteriana Mackenzie, São Paulo, SP,
2008.
[Langton, 1990] C. Langton. “Computation at the Edge of Chaos”, Physica D, 42:12–37, 1990.
[Li, 1991] W. Li. “Parameterizations of Cellular Automata Rule Space”, Santa Fe Institute Tech
Report: Preprints, Santa Fe, NM, USA, 1991.
[Margolus, 1984] N. Margolus. “Physics-like models of computation”, Physica D, 10:81–95,
1984.
[Moore, 1962] E.F. Moore, “Machine models of self-reproduction”, Proc. Symp. in Applied
Mathematics, 14:17–33, 1962.
[Moreira, 2003] A. Moreira. “Universality and decidability of number-conserving cellular automata”,
Theor. Comput. Sci. 292:711–721, 2003.
[Morita, 2007] K. Morita. “Simple Universal One-Dimensional Reversible Cellular Automata”,
Journal of Cellular Automata, 2(2):159-166, 2007.
[Myhill, 1963] J. Myhill, “The converse to Moore’s Garden-of-Eden theorem”, Proc. Amer. Math.
Soc., 14: 685–686, 1963.
47
[Nagel e Schreckenberg, 1992] K. Nagel e M. Schreckenberg. “A cellular automaton model for
freeway traffic”, J. Physique I2, 2221, 1992.
[Nishio, 2006] H. Nishio. “How does the Neighborhood Affect the Global Behavior of Cellular
Automata?”, Lecture Notes in Computer Science 4173:122-130 (Eds. S. El Yacoubi, B.
Chopard and S. Bandini. In: Proceedings of ACRI2006), 2006.
[Oliveira et al, 2001] G. Oliveira, P. de Oliveira e N. Omar. “Definition and applications of a five-
parameter characterization of one-dimensional cellular automata rule space”, Artificial Life
Journal, 7(3), MIT Press, p. 277–301, 2001.
[Richardson, 1972] D. Richardson. “Tessellation with local transformations”, J. Comput. System Sci.
6:373–388, 1972.
[Schranko et al, 2008] A. Schranko, P.E. Florencio, R.M. Ywassa e P.P.B. de Oliveira. “A definition
of conservation degree for one-dimensional cellular automata rules”, Automata 2008
Proceedings: Theory and Applications of Cellular Automata – A. Adamatzky; R. Alonso-Sanz;
A. Lawniczak; G.J. Martinez; K. Morita; T. Worsch. (Editors). Luniver Press, p. 156-170,
2008.
[Schranko e de Oliveira, 2009] A. Schranko e P.P.B. de Oliveira. “Towards the definition of
conservation degree for one-dimensional cellular automata rules”, Journal of Cellular
Automata, 2009. A ser publicado.
[Toffoli, 1977] T. Toffoli. “Computation and construction universality of reversible cellular
automata”, J. Comput. System Sci. 15:213–231, 1997.
[Toffoli e Margolus, 1987] T. Toffoli and N. Margolus. “Cellular Automata Machines: A New
Environment for Modeling”, MIT Press, Cambridge, Mass, 1987.
[Toffoli e Margolus, 1990] T. Toffoli and N. Margolus. “Invertible Cellular Automata: A Review”,
Physica D, 45:229–253, 1990.
48
[Voorhees, 1995] B. Voorhees. “Computational Analysis of One-Dimensional Cellular Automata”,
World Scientific, 1995.
[Wolfram, 1994] S. Wolfram. “Cellular Automata and Complexity”, World Scientific, 1994.
[Wolfram, 2002] S. Wolfram. “A New Kind of Science”, Wolfram Media, 2002.
[Wuensche e Lesser, 1992] A. Wuensche e M. Lesser. “The Global Dynamics of Cellular Automata”,
Addison-Wesley, 1992.
[Wuensche, 1992] A. Wuensche. “Classifying Cellular Automata Automatically”, Complexity,
4(3):47-66, 1992.
[Zwick e Shu, 1995] M. Zwick e H. Shu. “Set-Theoretic Reconstructability of Elementary Cellular
Automata”, Advances in Systems Science and Apllications. Special Issue I:31-36, 1995.
49
50
Apêndice I
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
