Do que se trata o autômato celular? Que tipo de problema isso pode resolver? É algo equivalente às máquinas de Turing?
1 Resposta
Do que se trata o autômato celular?
A primeira definição de Automato Celular Surgiu com Von Neumman nos anos 40 com a intenção de fornecer informações sobre os requisitos lógicos de uma Máquina autorreplicadora, e foi usado no construtor universal de Von Neumann.
Em uma definição geral, Autômato Celular, matematicamente falando , é um arranjo de maquinas de estados que há alterações entre si baseando-se em condições pré-estabelecidas.
O AC é composto por um conjunto de células com determinados valores, que interagem entre si em função de uma coleção finita de condições pré-definidas. Os estados(valores) das células são alterados conforme um conjunto de regras de transição, que depende da vizinhança (às vezes da própria célula também), ou seja, das células em torno da célula que será atualizada.
Vale Ressalva sobre o trecho coleção finita de condições pré-definidas.
Evolução de um autómato celular numa rede de dimensão 1 e numa rede de dimensão 2 com simetria hexagonal. A regra de interacção é a mesma para os dois autómatos: o estado de cada nó no tempo 1 só depende dos estados nos nós vizinhos no tempo 0
Vamos pegar como referência os autômatos unidimensionais, Temos exatamente 256 regras definidas:
Cada célula pode assumir um dos possíveis estados (valores) k do conjunto Q, sendo que os estados variam de 0 até k − 1.
Por ser unidimensional, terá apenas dois caminhos(comumente chamado vizinhos), um para direita e um para a esquerda(desconsiderando o próprio ponto k)
A quantidade possível de combinações com os dois vizinhos e a própria célula e dois estados é 2³ = 8 combinações, sendo que as células terão apenas um dos dois estados existentes, ou seja, o número 2 corresponde a quantidade de estados possíveis que a célula pode assumir, por exemplo 0 ou 1, e o número 3 corresponde a quantidade de vizinhos, isto é, o vizinho da esquerda, a própria célula e o vizinho da direita, o que implica em uma faixa de vizinhança igual a r = 1. Com estas 8 possíveis combinações pode-se formar um total de 2⁸ = 256 regras locais, ou seja, para cada combinação a célula que será atualizada pode receber 0 ou 1.
Em suma os ACs representam determinados conjuntos que irá sofrer alteração por regras estabelecidas e isso implica na resposta da segunda pergunta:
** Que tipo de problema pode resolver?**
Por demonstrar os resultados a partir de regras os ACs são utilizados para simular fenômenos, é possível simular a propagação de um incêndio caso estejamos numa seca forte e o vento estiver a 10 nós para oeste, por exemplo, logicamente a parte ao leste do inicio estaria muito menos, ou não haveria nenhum foco de fogo e a parte queimando quando acabasse com as arvores e/ou encontrasse alguma região de muita rocha se findaria o incêndio.
É algo equivalente às máquinas de Turing?
Semelhante, mas não equivalente. Enquanto os Acs trabalhariam com valores pré definidos de conjuntos Finitos, se assemelhando a Fita da máquina, porém para Turing havia um potencial ilimitado de fitas.
é uma máquina capaz de calcular todos os processos ou funções que sejamos capazes de imaginar
Esta pergunta define bem o significado da Máquina de Turing O que é Máquina de Turing?
Outras referências : Autômatos Celulares, máquina de Turing ou a natureza Como máquina de Cálculo