Concurso/Encontro Nacional de Programação Lógica
CeNPL'2003

Universidade de Évora

9--11 de Maio de 2003


Autómatos Celulares

Introdução

Um Autómato Celular (AC) é um sistema dinâmico determinístico que consiste num array A de células idênticas que repetidamente mudam o seu estado ou cor de acordo com uma determinada regra de actualização ra. Esta regra é aplicada simultaneamente a todas as células de A em unidades de tempo discretas. Quando ra é aplicada a uma célula particular x Î A, a nova cor para x é determinada pelo valor corrente das células numa vizinhança Vx de x. Embora existam muitas escolhas interessantes para A, vamos restringir a nossa atenção a arrays uni-dimensionais de inteiros. A vizinhança de raio r (r é um inteiro positivo) de uma célula x é então o intervalo Vx = {y Î Z : |x-y| £ r}. De um modo geral, as células de um AC tomam uma cor de um conjunto de k cores diferentes (k ³ 2). No nosso problema tomamos r = 1 e k = 2. As duas cores possíveis são representadas por 0 e 1.

Para os ACs uni-dimensionais com r = 1 e k = 2, a regra de actualização ra de uma célula x depende das cores correntes das três células na vizinhança de x, pelo que podemos representar a nova cor de x por ra(p,q,r), onde p, q, r denotam as cores correntes respectivamente das células x-1, x e x+1. Por exemplo, a regra ra(p,q,r) = r desloca a sequência de cores (a sequência de zeros e uns) de uma unidade para a esquerda em cada actualização.

Tarefa

A sua tarefa consiste em escrever um programa Prolog que dada a configuração inicial das células; a regra de actualização; e o número N de actualizações a realizar; mostra na primeira linha do ecrã a configuração inicial e nas N linhas seguintes as N configurações que lhe sucedem.

Os Dados

O array uni-dimensional A é representado por uma lista de zeros e uns. A regra ra(p,q,r) é representada da maneira óbvia. Por exemplo, a regra
p + (1-2p) (q+r-qr)
é codificada como
         p + (1-2*p)*(q+r-q*r)
À esquerda da primeira célula (à esquerda do primeiro elemento na lista) e à direita da última célula (à direita do último elemento na lista) supomos um zero para efeitos de aplicação da regra (supomos, respectivamente, que p = 0 e r = 0).

Os Resultados

O programa deve ser invocado através do predicado:
         ca(+ConfiguracaoInicial,+RegraActualizacao,+NumActualizacoes)
Seguem-se dois exemplos ilustrativos:
         ?- ca([0,0,0,0,1],r,6).
            0 0 0 0 1
            0 0 0 1 0
            0 0 1 0 0
            0 1 0 0 0
            1 0 0 0 0
            0 0 0 0 0
            0 0 0 0 0

         ?- ca([0,0,0,1,0,0,0],p+(1-2*p)*(q+r-q*r),13).
            0 0 0 1 0 0 0
            0 0 1 1 1 0 0
            0 1 1 0 0 1 0
            1 1 0 1 1 1 1
            1 0 0 1 0 0 0
            1 1 1 1 1 0 0
            1 0 0 0 0 1 0
            1 1 0 0 1 1 1
            1 0 1 1 1 0 0
            1 0 1 0 0 1 0
            1 0 1 1 1 1 1
            1 0 1 0 0 0 0
            1 0 1 1 0 0 0
            1 0 1 0 1 0 0