Regras de Tansição de Autômatos Celulares (tabela de transição ou ainda função de transição)

Para implementação de um sistema autômato celular, a mais importante especificação do sistema é a tabela de transição. Pois é como for especificada a tabela de transição que fará com que o sistema evolua de um modo ou de outro. Por exemplo, para o jogo da vida que é mostrado como exemplo, uma das regras de transição diz que se uma célula está viva, ela só continuará nesse estado se exatamente dois ou três de seus oito vizinhos estiverem vivos.

De acordo com a finalidade, as regras de transição devem estar o mais próximo possível da realidade.

Existem algumas formas de se especificar a função de transição, a saber:

1. Especificação Direta


Uma especificação direta da tabela de transição consiste na listagem de todos os possíveis estados das células vizinhas, da própria célula, e do próximo estado. Por exemplo, para o autômato de uma dimensão considerado no exemplo da propagação do pulso na corda, temos as seguintes quádruplas do formato:

(estado vizinho 1, estado do vizinho 2, estado da célula, próximo estado)

0  para não exitada
1  para exitada

(0,0,0,0)     (0,0,1,0)
(1,0,0,1)     (0,1,1,0)
(0,1,0,1)     (1,0,1,0)
(1,1,0,1)     (1,1,1,0)

Como as variáveis da função de transição nesse caso são 2ⁿ (n=3), temos 8 possibilidades, mas em um sistema de grande porte teríamos um número bem elevado de possíveis entradas, o que torna esse tipo de especificação bastante tediosa.
 
 

2. Regras Totalísticas


Algumas vezes não importa exatamente qual o estado de cada vizinho de uma determinada célula, mas a quantidade total de células vizinhas que estão num determinado estado. Por exemplo, no applet do jogo da vida, como foi dito, para uma célula manter-se viva é necessário que a quantidade de células vivas ao redor seja dois ou três. Esse tipo de representação das regras é chamado de totalístico. No caso de ser considerado também ser considerado os estado atual da célula a ser modificada, essa representação é chamada de totalística exterior (curioso...).
 
 
 

3. Especificação Implícita e Multi-Passos


A especificação pode ser determinada por uma fórmula onde as variáveis representam os estados das células vizinhas ou o estado da própria célula. Por exemplo, os estado da célula r pode ser dado pela fórmula C(r) = {célula r-1 está ativa ou célula r+1 está inativa}.

Multi-passos consiste na forma como é avaliada a fórmula da função de transição. As variáveis da fórmulas podem ser avaliadas em passos diferentes, ou seja, por exemplo, pode-se avaliar na fórmula anterior primeiro quais as células inativas para todas as células do autômato e depois as células ativas, contanto que sejam seguidas as definições de autômatos celulares descritos na seção de definições.
 
 

4. Regras Probabilísticas


Em algumas situações pode-se associar a cada configuração da vizinhança diferentes saídas da função de transição atribuindo probabilidades a essas diferentes saídas. Ou seja, para uma dada configuração dos vizinhos, uma célula pode partir para um ou outro estado com probabilidade definida. É preciso lembrar que a soma das probabilidades de cada possível saída deve ser 1. Podemos tomar novamente o exemplo da propagação do pulso na corda, no qual um célula se estiver excitada no tempo t₀, não estará no tempo t₁. Poderíamos então definir as seguintes regras:
 

• Se uma célula está exitada no tempo t, ela estará não-excitada no tempo t+1 com probabilidade p e estará ainda excitada com probabilidade (1-p).
• Se uma célula não está exitada no tempo t, ela ficará no tempo t+1 se pelo menos um vizinho seu está exitado no tempo t.


Dessa maneira temos que uma dada célula pode estar não-deterministicamente em algum estado relativo a uma dada configuração da vizinhança.