Artigos

12: Autômatos celulares II - Análise - Matemática


  • 12.1: Tamanhos do Espaço de Regra e Espaço de Fase
    Um dos recursos exclusivos dos modelos CA típicos é que o tempo, o espaço e os estados das células são todos discretos. Por causa dessa discrição, o número de todas as funções de transição de estado possíveis é finito, ou seja, há apenas um número finito de "universos" possíveis em uma determinada configuração de CA. Além disso, se o espaço for finito, todas as configurações possíveis de todo o sistema também são enumeráveis. Isso significa que, para configurações de CA razoavelmente pequenas, pode-se realizar uma pesquisa exaustiva de todo o espaço de regras para
  • 12.2: Visualização do Espaço de Fase
    Se o espaço de fase de um modelo de CA não for muito grande, você pode visualizá-lo usando a técnica que discutimos na Seção 5.4. Essas visualizações são úteis para entender a dinâmica geral do sistema, especialmente medindo o número de bacias de atração separadas, seus tamanhos e as propriedades dos atratores.
  • 12.3: Aproximação de campo médio
    Os comportamentos dos modelos CA são complexos e altamente não lineares, por isso não é fácil analisar sua dinâmica de uma forma matematicamente elegante. Mesmo assim, existem alguns métodos analíticos disponíveis. A aproximação do campo médio é um desses métodos analíticos. É um método analítico poderoso para fazer uma previsão aproximada do comportamento macroscópico de um sistema complexo.
  • 12.4: Análise de Grupo de Renormalização para Prever Limites de Percolação
    O próximo método analítico é para estudar os limites críticos para que a percolação ocorra em processos de contato espacial, como aqueles no modelo de CA de epidemia / incêndio florestal discutido na Seção 11.5. O limite de percolação pode ser estimado analiticamente por um método chamado análise de grupo de renormalização.

Autômatos celulares

4.9 Autômatos celulares em rede - um desenvolvimento para o futuro?

Autômatos celulares de rede (NCA) são um desenvolvimento relativamente recente de autômatos celulares [Wol02]. Aqui está uma tentativa de definição:

As células são definidas como nós em uma rede de conexões. Diferente dos autômatos celulares convencionais é que as células não constituem necessariamente uma partição de volume do espaço, elas são abstraídas para um nível superior. Na verdade, uma rede geralmente pode ser mapeada em qualquer número de dimensões. Na Figura 4-30, as células são desenhadas em uma grade periódica 2D, mas deve-se notar que esta especificação de grade é não parte da definição da rede, é apenas uma forma de desenhar a rede de maneira ordenada.

FIGURA 4-30. Autômatos celulares em rede.

Uma definição de vizinhança da célula & # x27s é determinada pela configuração local da rede. Um exemplo de definição poderia ser: a própria célula mais todas as células diretamente conectadas a ela e todas as conexões entre essas células, conforme ilustrado para a célula cinza no recorte da Figura 4-30.

O estado de uma célula da rede é a configuração das conexões em sua vizinhança.

Uma regra de mudança de estado opera na configuração da rede na vizinhança. As conexões podem ser adicionadas, excluídas e modificadas. A única restrição é que nenhuma conexão deve ser adicionada às células fora da vizinhança. Para isso, seriam necessárias informações sobre a localização na rede de células fora da vizinhança, o que é o mesmo que considerar uma vizinhança maior, por exemplo, incluindo nnível, células indiretamente conectadas.

4.9.1 Autômatos Celulares de Rede Combinada

Os autômatos celulares de rede combinada (CNCA) são uma extensão lógica do NCA. O conceito é simples: o estado de uma célula é uma combinação da configuração de rede na vizinhança e um estado separado, opcionalmente com atributos, atribuídos à própria célula. Conforme ilustrado na Figura 4-31, a principal diferença com o NCA padrão é que uma regra de mudança de estado agora também opera nesses estados de célula separados e seus atributos. Esta figura também indica a enorme quantidade de possibilidades que posso ser usado para definir a função de transformação de estado f, já que a combinação de configuração de rede e estados de célula separados tem um grande número de combinações possíveis. É de se esperar que, ao utilizar CNCA, se limite as combinações possíveis, mas a abertura da definição permite selecionar as necessárias. Tomando a Figura 4-31 como exemplo:

FIGURA 4-31. Autômatos celulares de rede combinada.

f toma como entrada os estados das células na vizinhança e / ou a configuração local das conexões entre a célula central e suas vizinhas.

f precisa ser definido para todas as configurações de rede de estado combinadas possíveis, por exemplo, a configuração inicial à esquerda no recorte na Figura 4-31 leva à situação modificada na parte direita da figura: -

O estado da célula é alterado de UMA para B.

Algumas conexões de rede são excluídas enquanto outras são criadas, alterando assim o layout da rede local, mas também redefinindo a vizinhança para a etapa CNCA subsequente.

É importante observar que, dependendo do tipo de reconfiguração da rede, em alguns casos a transformação de estado não pode ser realizada em todas as células em paralelo, pois podem surgir conflitos quando a rede local é trocada simultaneamente para células vizinhas. Este tópico precisa de mais pesquisas no nível do método matemático, mas uma abordagem prática é construir uma função de transformação de estado que garanta que tais conflitos não ocorram ou não realizar transformações de estado em todas as células em paralelo.

A questão crucial agora é: tais CNCA podem ser úteis para modelar a evolução da microestrutura, ou são úteis apenas na busca por uma grande teoria unificada [Wol02]?

4.9.2 CNCA para Modelagem de Evolução de Microestrutura

Diferentes estruturas semelhantes a redes podem ser observadas em microestruturas:

Microestruturas são grãos conectado por limites de grãos.

Uma microestrutura 2D é uma coleção de junções triplas conectadas por contornos de grão.

Possivelmente, uma microestrutura 3D é representável como uma coleção de junções quádruplas e triplas conectadas por contornos de grão.

Algumas microestruturas de materiais compostos ou multifásicos mostram claramente redes em sua estrutura.

Tomando o primeiro exemplo da lista, aqui está uma maneira plausível de modelar o crescimento de grãos usando CNCA:

Dê a todos os grãos da microestrutura um número de identificação único.

O estado de uma célula pode ser qualquer um desses números de identificação e representa um grão inteiro na microestrutura.

O atributo para um estado de célula & # x27s é sua orientação cristalográfica. Atributos adicionais podem ser o volume do grão, sua composição química média, temperatura, densidade de deslocamento, fase, etc.

A configuração da rede é tal que cada célula de grão é conectada às células de grão com as quais está em contato através de uma superfície de contorno de grão (pode-se adicionar junções triplas).

Um exemplo de tal modelo é dado na Figura 4-32.

FIGURA 4-32. Autômatos celulares em rede combinada aplicados a uma microestrutura simples de óxido de alumínio. A inserção mostra uma microestrutura mais complexa de um aço duplex laminado, onde a determinação da rede também é muito mais complexa.

É indiscutível que a utilidade do CNCA para a análise e modelagem de microestruturas em evolução ainda precisa ser investigada. Mas, como último ato neste capítulo sobre autômatos celulares, gostaria de apresentar a visão de que:

É possível analisar a evolução de microestruturas 3D complexas usando CNCA, e muito mais detalhes podem ser encontrados sobre a dependência da evolução da microestrutura na vizinhança local dos grãos, que são, afinal, os blocos de construção das microestruturas.

Além disso, usando os resultados de tal análise, pelo menos em alguns casos simplificados, é possível prever a evolução de tais microestruturas.

Lista de Símbolos

ƒ função de transformação de estado

k Constante de Boltzmann (= 1,38065812 e -23 J / K)

eu ca comprimento unidimensional de uma célula

m mobilidade limite de grão

m0 prefator independente da temperatura da mobilidade do contorno do grão

puma pressão motriz adicional

rη raio da vizinhança

rc raio equivalente de uma célula

ϒ função de estado global de um autômato celular

υ velocidade do limite do grão


Cellular Automata do Natal de 1983

Há uma certa complexidade em muitas das formas características usadas nas imagens de Natal: flocos de neve, árvores de Natal, padrões de geada, etc.

E como em tantos outros casos, é bastante fácil capturar a essência dessas formas usando regras de autômato celular muito simples.

Isso significa que é fácil usar as regras do autômato celular para fazer imagens de Natal.

Bem, examinando alguns dos meus arquivos recentemente, lembrei-me de que fiz isso há quase exatamente vinte anos & # 8212 para o Natal de 1983. (A data real do arquivo é 22 de novembro de 1983.)

Imprimi quatro tipos de cartões para o Natal de 1983:

Em anexo estão os scans dos cards originais de 1983, junto com versões modernas feitas com as mesmas regras (embora com escolhas ligeiramente diferentes de condições iniciais aleatórias).

É claro que é inevitável, mas sempre acho agradável que, em qualquer ano que se faça uma imagem de autômato celular, ela sempre tenha a mesma aparência nova. De alguma forma, isso me lembra os poliedros da antiguidade & # 8212; que, claro, parecem exatamente os poliedros de hoje.

Desde 1983, muitas imagens de autômatos celulares têm sido usadas para cartões de Natal & # 8212 por mim e outros. E certamente seria ótimo ver alguns deles postados no Fórum. Mas achei que os membros do Fórum poderiam se divertir ao ver meus esforços originais de 1983.

Observe a ausência nesses esforços da regra 30 ou qualquer coisa parecida. Só em 1984 é que percebi totalmente que condições iniciais simples ainda podiam produzir um comportamento altamente complexo. (Veja o livro NKS, página 881)


Assis, F., Pedreira, C .: Uma arquitetura para o cálculo dos logaritmos de Zech em GF (2m). IEEE Trans. Comput. 49(5), 519–524 (2000)

Bao, F .: Crytanalysis of a cell autômata cryptosystem. 8ª Conferência da Australásia sobre Segurança da Informação e Privacidade - ACISP 2003. Lecture Notes in Computer Science, vol. 2727, pp. 416-427. Springer, Berlin Heidelberg New York (2003)

Blackburn, S., Merphy, S., Paterson, K .: Comentários sobre ‘Teoria e aplicações de autômatos celulares em criptografia’. IEEE Trans. Comput. 46, 637–638 (1997)

Cattell, K., Muzio, J .: Análise de autômatos celulares híbridos lineares unidimensionais sobre GF (q). IEEE Trans. Comput. 45(7), 782–792 (1996)

Cattell, K., Muzio, J .: Synthesis of un-dimensional linear hybrid hybrid automata. IEEE Trans. Des. Comput.-Aided. Integr. Circuits Syst. 15(3), 325–335 (1996)

Cattell, K., Shujian, Z .: Autômatos celulares híbridos lineares de custo mínimo de grau a 500. J. Electron. Teste: Teoria Appl. 6, 255–258 (1995)

Cattell, K., Muzio, J .: Um algoritmo de autômato celular linear: Teoria. Departamento de Ciência da Computação. Universidade de Victoria, Canadá, Tech. Rep. DCS-161-IR, 1991

Coppersmith, D., Krawczyk H., Mansour, Y .: The shrinking generator. Advances in Cryptology –CRYPTO'93. Lecture Notes in Computer Science, vol. 773, pp. 22-39. Springer, Berlin Heidelberg New York (1994)

Cho, S., Un-Sook, C., Yoon-Hee, H .: Computing phase shifts of maximum-length 90/150 Cellular automata sequences. Proc. of ACRI 2004. Lecture Notes on Computer Science, vol. 3305, pp. 31–39. Springer, Berlin Heidelberg New York (2004)

Das, A.K., Ganguly, A., Dasgupta, A., Bhawmik, S., Chaudhuri, P.P .: Efficient caracterization of cell automata. IEE Proc., Parte E. 1, 81–87 (1990)

Golomb, S .: Shift-Register Sequences (edição revisada). Aegean Park, Laguna Hills, Califórnia (1982)

Gong, G .: Teoria e aplicações de sequências intercaladas q-ário. IEEE Trans. Informar. Teoria 41, 400–411 (1995)

Golic, J., O'Connors, L .: A cryptanalysis of clock-driven shift registers with multiple steps. Criptografia: Política e Algoritmos 41, 174–185 (1995)

Johansson, T .: Ataques de correlação de complexidade em dois Geradores controlados por relógio. Proc. de Asiacrypt'98. Lecture Notes in Computer Science, vol. 1426, pp. 342-356. Springer, Berlin Heidelberg New York (1998)

Kanso, A .: Gerador de encolhimento controlado por relógio de registradores de deslocamento de feedback. 8ª Conferência da Australásia sobre Segurança da Informação e Privacidade - ACISP 2003. Lecture Notes in Computer Science, vol. 2727, pp. 443–451. Springer, Berlin Heidelberg New York (2003)

Lidl, R., Niederreiter, H .: Introdução aos Campos Finitos e Suas Aplicações. Cambridge University Press, Cambridge, Reino Unido (1986)

Martin, O., Odlyzko, A.M., Wolfram, S .: Algebraic properties of celular automata. Com. Matemática. Phys. 93, 219–258 (1984)

Menezes, A.J., van Oorschot, P., Vanstone, S.A .: Handbook of Applied Cryptography. CRC, Nova York (1997)

Nandi, S., Kar, B.K., Chaudhuri, P.P .: Teoria e aplicações de autômatos celulares em criptografia. IEEE Trans. Comput. 43, 1346–1357 (1994)

Rueppel, R.A .: Stream ciphers. In: Simmons G.J. (ed.) Contemporary Cryptology, The Science of Information, pp. 65-134. IEEE, Piscataway, New Jersey (1992)

Serra, M., Slater, T., Muzio, J., Miller, D.M .: A análise de autômatos celulares lineares unidimensionais e suas propriedades de aliasing. IEEE Trans. Des. Comput.-Aided. Integr. Circuits Syst. 9(7), 767–778 (1990)

Simpson, L. et al. Clock - um ataque de correlação probabilística no gerador de encolhimento. Proc. da Conferência Australasian sobre Segurança da Informação e Privacidade - ACISP 1998. Lecture Notes in Computer Science, vol. 1438, pp. 147-158. Springer, Berlin Heidelberg New York (1998)

Wolfram, S .: Geração de sequência aleatória por autômatos celulares. Adv. Appl. Matemática. 7(123), (1986)

Wolfram, S .: Cryptography with cell automata. Avanços em Criptologia - CRYPTO'85. Lecture Notes in Computer Science, vol. 218, pp. 22-39. Springer, Berlin Heidelberg New York (1994)

Zhang, S .: Análise quantitativa para CA híbrido linear e LFSR como geradores BIST para falhas sequenciais. J. Electron. Teste. 7(3), 209–221 (1995)


Wolfram, S. Rev. Mod. Phys. 55, 601–644 (1983).

Wolfram, S. Physica 10 D, 1–35 (1984).

Wolfram, S. Comum. Matemática. Phys. (na imprensa).

Wolfram, S. Autômatos celulares (Los Alamos Science, outono, 1983).

Mandelbrot, B. A geometria fractal da natureza (Freeman, San Francisco, 1982).

Packard, N., Preprint Modelos de autômato celular para crescimento dendrítico (Institute for Advanced Study, 1984).

Madore, B. & amp Freedman, W. Ciência 222, 615–616 (1983).

Greenberg, J. M., Hassard, B. D. & amp Hastings, S. P. Touro. Amer. Matemática. Soc. 84, 1296–1327 (1978).

Vichniac, G. Physica 10 D, 96–116 (1984).

Domany, E. & amp Kinzel, W. Phys. Rev. Lett. 53, 311–314 (1984).

Waddington, C. H. & amp Cowe, R. J. J. teore. Biol. 25, 219–225 (1969).

Lindsay, D. T. Veliger 24, 297–299 (1977).

Young, D. A. Um modelo local ativador-inibidor de padrões de pele de vertebrados (Lawrence Livermore National Laboratory Rep., 1983).

Guckenheimer, J. & amp Holmes, P. Oscilações não lineares, sistemas dinâmicos e bifurcações de campos de vetores (Springer, Berlin, 1983).

Hopcroft, J. E. & amp Ullman, J. D. Introdução à teoria, linguagens e computação dos autômatos (Addison-Wesley, New York, 1979).

Packard, N. Preprint, Complexidade de padrões de crescimento em autômatos celulares (Institute for Advanced Study, 1983).

Martin, O, Odlyzko, A. & amp Wolfram, S. Comum. Matemática. Phys. 93, 219–258 (1984).

Grassberger, P. Physica 10 D, 52–58 (1984).

Lind, D. Physica 10 D, 36–44 (1984).

Margolus, N. Physica 10 D, 81–95 (1984).

Smith, A. R. Journal of the Association for Computing Machinery 18, 339–353 (1971).

Berlekamp, ​​E. R., Conway, J. H. & amp Guy, R. K. Maneiras de vencer para seus jogos matemáticos Vol. 2, CH. 25 (Academic, New York, 1982).

Gardner, M. Rodas, vida e outras diversões matemáticas (Freeman, San Francisco, 1983).

Wolfram, S. Manual de Referência SMP (Computer Mathematics Group, Inference Corporation, Los Angeles, 1983).


Instantâneos


O programa simulador é escrito em JavaScript e HTML5, portanto, um navegador decente, o suporte a essas tecnologias é um requisito absoluto. Testei o simulador na última versão do Firefox, Chrome e Opera para desktop e funciona bem. Não funciona no IE9, mas o IE 10 deve suportá-lo (embora nunca tenha sido testado). Também funcionará em alguns navegadores móveis, particularmente no Android e Chrome, mas a interface é mais adequada para mouse, não para telas sensíveis ao toque.

Uso básico

Espero que você considere a interface do Simulador autoexplicativa. Como na maioria dos simuladores convencionais de CA, você pode editar padrões de células com o mouse e executar a simulação, passo a passo ou continuamente. Se você viu Golly, então você sabe tudo. O principal recurso que você não encontrará no Golly é o botão & ldquoReverse Play & rdquo, que permite avaliar o universo celular no passado. Na verdade, isso só é possível para os autômatos celulares reversíveis.

  • Editando células usando o mouse ou a interface de toque (o último não é conveniente, mas é compatível).
  • Executando o autômato na direção para frente e para trás.
  • Alterando regra de automação celular. Selecione uma das regras predefinidas ou insira a sua própria na notação de transposição (consulte & ldquoRulse na vizinhança de Margolus & rdquo acima).
  • Seleção:
    • Limpar área selecionada ou não selecionada
    • Preencher com células aleatórias
    • Analise o padrão selecionado (veja os recursos avançados)
    • Copie o padrão selecionado para o buffer interno e cole-o no campo

    Características avançadas

    • Analisador de padrões
    • Apanhador de nave espacial
    • Analisador de regra
    • Salvar o estado no URL

    Analisador de padrões

    • Tipo de Padrão: oscilador, nave espacial (diagonal, ortogonal ou inclinada) ou nenhum.
    • Período padrão, se for um oscilador ou nave espacial.
    • Velocidade de movimento do padrão, no caso de ser uma nave espacial.
    Uma nave diagonal com período 10896 e velocidade c / 5448. A regra é & # 8220Rotations II & # 8221. Experimente ao vivo (nova janela).

    Esses grandes períodos complicam enormemente a análise manual dos padrões. Dados 2 padrões visualmente diferentes, como você decide: são fases diferentes do mesmo padrão ou apenas 2 padrões diferentes? A forma canônica oferece uma solução para este problema. O Analyzer avalia um determinado padrão durante seu período e escolhe uma configuração que minimiza alguns critérios. (Precisamente falando, ele procura a configuração mais compacta, mas não é realmente importante). O importante é que essa forma canônica seja determinada exclusivamente (na maioria dos casos). Além disso, se o padrão foi identificado como uma nave espacial e a regra permite rotações, a forma canônica é girada de forma que a direção do movimento seja para a direita (ortogonal) ou para a direita inferior (diagonal). Usando a forma canônica, determinar a equivalência de dois padrões é trivial: padrões equivalentes têm as mesmas formas canônicas.

    Apanhador de nave espacial

    Este recurso facilita a busca por espaçonaves nascidas naturalmente, inicializando o campo com um padrão inicial aleatório no centro e coletando espaçonaves em fuga. Quando o receptor de nave espacial está ativado, todos os padrões que tocam a borda do campo são removidos dele, analisados ​​e as naves são adicionadas à biblioteca aberta no momento. A cada 30000 etapas (que é o valor padrão que pode ser alterado no painel & ldquoSettings & rdquo), o campo é reinicializado: a seleção atual é preenchida aleatoriamente.


    Risco de embaçamento: difusão de informações com base em autômatos celulares

    Os efeitos negativos do risco de neblina podem se espalhar facilmente de forma mais rápida e ampla, no entanto, os estudos existentes raramente investigam todo o período ou ciclo de eventos de difusão, o que leva ao conhecimento público reduzido, muitas vezes resultando em efeitos negativos exagerados. Neste artigo, o modelo de simulação de difusão baseado em autômatos celulares é usado para avaliar a difusão de informações de risco de neblina. Em primeiro lugar, de acordo com o ciclo de vida completo das emergências, o público afetado pelas informações de risco de neblina é classificado pela semelhança do modelo de doenças infecciosas SEIR. Em segundo lugar, uma regra de difusão de desconhecidos para indivíduos expostos é desenvolvida com base na teoria dos autômatos celulares. Então, de acordo com a transformação de estado individual em diferentes estágios, um modelo de ciclo de vida completo em relação à difusão de informações de risco de neblina e modelo de propagação é construído. Finalmente, os parâmetros apropriados são selecionados para calcular os resultados sem intervenção. Os resultados mostram que durante todo o processo de evolução, as incógnitas continuam diminuindo e os lurkers continuam aumentando. Devido à existência do período de imunização, os imunizados atingem seu número máximo antes que estejam prestes a perder imunidade, e o número de comunicadores atinge o mínimo. Posteriormente, o número de pessoas imunizadas reduziu a um nível estável e o número de comunicadores continua a aumentar em direção a um benefício de aglomeração. Portanto, a fim de alcançar o controle efetivo da disseminação das informações de risco de neblina, medidas de controle fortes e fracas são tomadas para cada tipo de indivíduo, e a imunidade de desconhecidos e lurkers é aumentada para o controle de tipo individual. Para todo o controle de difusão de informações, aumente a imunidade do comunicador e reduza a taxa de conversão de imunização. O estudo da disseminação de informações sobre o risco de neblina ajuda a aumentar o senso de responsabilidade do público, ajuda a melhorar a credibilidade do governo e contribui para o estabelecimento de uma sociedade harmoniosa.

    Esta é uma prévia do conteúdo da assinatura, acesso através de sua instituição.


    2. Algumas noções básicas e resultados

    2.1 Definições básicas

    Agora estamos dando uma olhada mais de perto na CA, com foco em modelos e resultados de interesse filosófico. Embora a variedade de sistemas que podem ser encontrados na literatura de CA seja vasta, pode-se gerar praticamente todos os CA ajustando os quatro parâmetros que definem sua estrutura:

    1. Rede discreta n-dimensional de células: Podemos ter unidimensional, bidimensional e, diabos, n-dimensional CA. Os componentes atômicos da rede podem ter formatos diferentes: por exemplo, uma rede 2D pode ser composta de triângulos, quadrados ou hexágonos. Geralmente homogeneidade é assumido: todas as células são qualitativamente idênticas.
    2. Estados discretos: A cada passo de tempo discreto, cada célula está em um e apenas um estado, ( sigma in Sigma, Sigma ) sendo um conjunto de cardinalidade finita (| Sigma | = k ).
    3. Interações locais: O comportamento de cada célula e rsquos depende apenas do que acontece em seu local vizinhança de células (que podem ou não incluir a própria célula). Lattices com a mesma topologia básica podem ter diferentes definições de vizinhança, como veremos a seguir. É crucial, entretanto, observar que & ldquoactions à distância & rdquo não são permitidos.
    4. Dinâmica discreta: Em cada etapa de tempo, cada célula atualiza seu estado atual de acordo com uma função de transição determinística ( phi: Sigma ^ n rightarrow Sigma ) mapeando as configurações de vizinhança (n-tuplos de estados de ( Sigma )) a ( Sigma ). Também é geralmente, embora não necessariamente, assumido que (i) a atualização é síncrono, e (ii) ( phi ) leva como entrada na etapa de tempo t os estados da vizinhança imediatamente anterior passo de tempo (t - 1 ).

    Pode-se descrever exaustivamente, por exemplo, o autômato do nosso exemplo de sala de aula:

    1. Estrutura unidimensional de células quadradas em uma linha.
    2. ( Sigma = <1, 0> ) (1 = preto ou chapéu colocado, 0 = branco ou chapéu retirado), então (| Sigma | = 2 ).
    3. Cada vizinhança de célula e rsquos é composta pelas duas células mais próximas. Se indexarmos as células por inteiros, de modo que (c_i ) é o número da célula eu, então a vizinhança de (c_i ) é (N (c_i) = langle c_, c_ rangle ).
    4. A regra de transição ( phi ) é simples: a cada passo de tempo t, um estado de célula é 1 se exatamente uma das células vizinhas era 1 em (t - 1, 0 ) caso contrário.

    Uma regra para um CA pode ser expressa como uma instrução condicional: & ldquoSe a vizinhança é isto e aquilo, então volte para o estado s& rdquo. Pode-se escrever a forma geral da regra para CA unidimensional:

    [marcação sigma_i (t + 1) = phi ( sigma_ (t), sigma_ (t), ldots, sigma_ (t), sigma_ (t)) ]

    Onde ( sigma_(t) in Sigma = <0, 1, ldots, k - 1 > ) é o estado do número da célula eu no passo do tempo t r especifica o alcance, ou seja, quantas células em qualquer lado contam como vizinhas para uma determinada célula e ( phi ) é definido explicitamente atribuindo valores em ( Sigma ) a cada um dos (k ^ <2r + 1> (2r + 1) ) - tuplas representando todas as configurações de vizinhança possíveis. Por exemplo, com (r = 1, Sigma = <1, 0 > ), uma possível regra de transição ( phi ) pode ser expressa como na Fig. 4 (com 1 sendo representado como Preto, 0 como Branco):

    Para uma determinada célula, cada triplo no topo representa uma configuração de vizinhança possível em t, sendo a célula em questão a do meio: para cada configuração, o quadrado na parte inferior especifica o estado da célula & rsquos em (t + 1 ). Este é o nosso exemplo de sala de aula: você terá uma cela preta para o caso de precisamente um dos vizinhos ser preto.

    2.2 O Esquema de Classificação Wolfram

    Essa representação simples também está no cerne do código Wolfram amplamente adotado (Wolfram 1983), atribuindo a cada regra um número: com Preto = 1 e Branco = 0, a linha inferior pode ser lida como um número binário (01011010) e a conversão em decimal fornece a regra e o nome do rsquos (neste caso, Regra 90) Como as regras para CA com (r = 1 ) e (k = 2 ) diferem apenas na linha inferior do diagrama, esse esquema de codificação identifica efetivamente cada regra possível na classe. CA unidimensional com (r = 1 ) e (k = 2 ) estão entre os CA mais simples que se pode definir, embora seu comportamento seja bastante interessante. Quando Stephen Wolfram começou a explorar esse campo nos anos 80, essa classe parecia uma combinação perfeita. Com (r = 1 ), existem 8 vizinhos possíveis (veja a Fig. 4 acima) a serem mapeados para (<1, 0> ), dando um total de (2 ^ 8 = 256 ) regras. Começando com condições iniciais aleatórias, Wolfram passou a observar o comportamento de cada regra em muitas simulações. Como resultado, ele foi capaz de classificar o comportamento qualitativo de cada regra em uma das quatro classes distintas. Repetindo o experimento original, simulamos a evolução de duas regras para cada classe do esquema de Wolfram & rsquos.

    2.3 As Classes das 256 Regras

    Aula1 regras que levam a estados homogêneos, todas as células terminando de forma estável com o mesmo valor:

    Aula2 regras que levam a estruturas estáveis ​​ou padrões periódicos simples:

    Aula3 regras que levam a um comportamento aparentemente caótico e não periódico:

    Aula4 regras que levam a padrões complexos e estruturas que se propagam localmente na rede:

    Aula1 compreende as regras que produzem rapidamente configurações uniformes. Regras da aula2 produzir um padrão final uniforme, ou um ciclo entre os padrões finais, dependendo das configurações iniciais. As configurações produzidas por membros da Classe3 parecem muito aleatórios, embora alguns padrões e estruturas regulares possam estar presentes.

    Aula4 merece atenção especial. Se observarmos o universo gerado por Regra 110 vemos padrões regulares (embora não tão regulares quanto em Regra 108), bem como algum comportamento caótico (embora não seja tão barulhento quanto em Regra 90) Agora, o recurso básico que uma CA precisa para realizar cálculos é a capacidade de sua regra de transição de produzir padrões de propagação persistentes & ldquopartículas & rdquo (Ilachinski 2001: 89), ou seja, configurações localizadas, estáveis, mas não periódicas de grupos de células, às vezes chamado solitons na literatura, que pode preservar sua forma. Essas configurações podem ser vistas como codificação pacotes de informações, preservando eles através do tempo, e em movimento de um lugar para outro: a informação pode se propagar no tempo e no espaço sem sofrer deterioração importante. A quantidade de imprevisibilidade no comportamento da Classe4 as regras também sugerem características computacionalmente interessantes: pelo Teorema da Halting (veja a seção no verbete sobre máquinas de Turing), é uma característica-chave da computação universal que não se pode, em princípio, prever se uma dada computação irá parar com uma determinada entrada. Esses insights levaram Wolfram a conjeturar que a classe4 CA eram (os únicos) capazes de computação universal. Intuitivamente, se interpretarmos a configuração inicial de uma classe4 CA como seus dados de entrada, uma classe universal4 O CA pode avaliar qualquer função efetivamente computável e emular uma máquina de Turing universal. Como mencionamos acima, Regra 110 foi de fato provado ser computacionalmente universal.

    (Veja o documento suplementar The 256 Rules.)

    2.4 The Edge of Chaos

    A natureza intermediária da classe4 regras estão conectadas à ideia de que interessante complexidade, como aquela exibida por entidades biológicas e suas dinâmicas, encontra-se em uma área intermediária entre os dois extremos de regularidades enfadonhas e caos ruidoso:

    Talvez a implicação mais emocionante [da representação CA de fenômenos biológicos] seja a possibilidade de que a vida teve sua origem nas proximidades de uma transição de fase e que a evolução reflete o processo pelo qual a vida ganhou controle local sobre um número sucessivamente maior de parâmetros ambientais que afetam sua capacidade de se manter em um ponto crítico de equilíbrio entre a ordem e o caos. (Langton 1990: 13)

    CA forneceu não apenas a intuição, mas uma estrutura formal para investigar a hipótese. No final dos anos 80, a imagem do & ldquoEdge of Chaos & rdquo recebeu considerável interesse dos praticantes da CA. Packard 1988 e Langton 1990 foram os primeiros estudos a dar ao Edge of Chaos uma interpretação agora bem conhecida no contexto da CA. Como Miller e Page colocaram, & ldquothese primeiros experimentos sugeriram que os sistemas posicionados à beira do caos tinham a capacidade de computação emergente & rdquo (Miller & amp, página 2007: 129). A ideia é bastante simples: o que acontece se seguirmos uma regra como Regra 110 e introduzir uma pequena perturbação? Se quisermos acreditar na hipótese do Limite do Caos, devemos esperar as regras obtidas por pequenas mudanças em Regra 110 para exibir um comportamento simples ou caótico. Vamos considerar uma única mudança de 1 para 0 ou 0 para 1 no mapeamento característico de Regra 110. Os resultados são as seguintes oito regras vizinhas, cada uma diferindo de Regra 110 por um único bit (a diagonal na matriz, com números em itálico):

    110 111 108 106 102 126 78 46 228
    000 0 1 0 0 0 0 0 0 0
    001 1 1 0 1 1 1 1 1 1
    010 1 1 1 0 1 1 1 1 1
    011 1 1 1 1 0 1 1 1 1
    100 0 0 0 0 0 1 0 0 0
    101 1 1 1 1 1 1 0 1 1
    110 1 1 1 1 1 1 1 0 1
    111 0 0 0 0 0 0 0 0 1
    Aula 4 2 2 3 3 3 1 2 1

    Em uma primeira aproximação, a hipótese do Limite do Caos é confirmada: três dos oito vizinhos são de Classe3, três são de classe2, dois são de classe1: Regra 110 é a única classe4 na mesa. Para generalizar essas descobertas para toda a classe de regras para CA unidimensional, Langton introduziu um parâmetro, ( lambda ), que se aplica a cada ( phi ): para (k = 2 ), ( r = 1 ) (estado binário, intervalo unário) CA, ( lambda ( phi) ) pode ser calculado como a fração de entradas da tabela de regras de transição que são mapeadas para uma saída diferente de zero (consulte Langton 1990: 14 para a definição geral). Em nosso caso, isso significa: ( lambda ( phi) ) será igual ao número de unidades na coluna de regra & mdashe.g., ( Lambda ( phi) = 5/8 ) para ( phi ) = Regra 110 e ( lambda ( phi) = 1/2 ) para ( phi ) = Regra 46. A principal descoberta de Langton & rsquos foi que uma medida simples como ( lambda ) se correlaciona com o comportamento do sistema: como ( lambda ) vai de 0 a 1, o comportamento médio dos sistemas vai de congelamento para padrões periódicos até o caos. Langton destacou 1/2 como o valor de ( lambda ) no qual o comportamento médio mostra pela primeira vez evidências de caos: regras ( phi ) com ( lambda ( phi) sim 1/2 ) foram destacados como estando no Edge (veja Miller & amp Página 2001: 133).

    ( lambda ) Todas as regras Regras Caóticas Regras Complexas
    0 1 0 0
    1/8 8 0 0
    1/4 28 2 0
    3/8 56 4 1
    1/2 70 20 4
    5/8 56 4 1
    3/4 28 3 0
    7/8 8 0 0
    1 1 0 0

    Tanto as regras caóticas quanto as complexas têm um valor médio de ( lambda ) em torno de 1/2, aparentemente apoiando a hipótese da Borda do Caos. É justo dizer, porém, que alguns lançaram dúvidas sobre o papel explicativo do parâmetro ( lambda ) e as inferências tiradas dele. Em particular, a região de transição do Edge of Chaos parece ser ela própria complexa. Miller e Page observam que & ldquothere são arestas múltiplas, não apenas uma única & rdquo (Miller & amp Página 2007: 133). Os resultados agregados não são válidos quando analisamos regras individuais, mesmo paradigmáticas:

    110 111 108 106 102 126 78 46 228
    ( lambda ) 5/8 3/4 1/2 1/2 1/2 3/4 1/2 1/2 3/4

    Como mostra a tabela, entre os Regra 110 vizinhos, algumas regras caóticas ( phi ) têm ( lambda ( phi) = 3/4 ), algumas cíclicas têm ( lambda ( phi) = 1/2 ) e, de fato,

    every one of the rules classified as complex in this space has at least one chaotic neighbor with a lower (lambda) value and one with higher value. (Miller & Page 2007: 135)

    Melanie Mitchell, Peter Hraber and James Crutchfield replicated Langton and Packard&rsquos experiments, reporting very different results (Mitchell, Hraber, & Crutchfield 1994). In particular, they report that serious computational phenomena take place much closer to a chaotic (lambda(phi) = 1/2) than it was previously thought. Apart from technical points, a conceptual flaw in the original findings is the use of aggregate statistics, which are difficult to interpret in a high variance context:

    if, instead, the hypotheses are concerned with generic, statistical properties of CA rule space&mdashthe &ldquoaverage&rdquo behavior of an &ldquoaverage CA&rdquo at a given (lambda)&mdashthen the notion of &ldquoaverage behavior&rdquo must be better defined. (Mitchell, Hraber, & Crutchfield 1994: 14).

    While it is fair to conclude that complex behavior does not lie at the Edge of Chaos taken in a simplistic sense (i.e., it is not straightforwardly correlated with the simple (lambda)), the interest in the connection between computational capabilities and phase transitions in the CA rule space has been growing since then. We will consider such developments below, specifically in the context of CA and the philosophy of computation.

    2.5 CA in More Dimensions: the Game of Life

    Notwithstanding the computational interest of one-dimensional CA, philosophical issues have been discussed more often in connection with two-dimensional CA. The first CA, von Neumann&rsquos self-reproducing automaton, inhabited a two-dimensional grid. Besides, two-dimensional CA are suitable for representing many physical, biological, and even human phenomena, ranging from the dynamics of perfect gases to the movements of birds in a storm and soldiers on a battlefield. The most common configurations have either square or hexagonal cells, given their translational and rotational symmetries. Moving to two dimensions, of course, also expands the possibly interesting combinations of rules and neighborhoods. As for the latter, the two most common options in a grid of squares are the von Neumann neighborhood, where each cell interacts only with its four horizontal and vertical adjacent mates, and the Moore neighborhood, comprising all the eight immediately adjacent cells.

    By way of example, we introduce the famous Game of Life (or, more briefly, Life) by John Conway (see Berkelamp, Conway, & Guy 1982). Life fits well with our usual schema:

    1. 2-dimensional lattice of square cells in an orthogonal grid.
    2. (Sigma = <1, 0>), so (|Sigma| = 2) (for reasons we are about to see, we can picture 1 as the state of being alive for a given cell, 0 as the state of being dead).
    3. Each cell&rsquos neighborhood is composed of all its eight neighboring cells (the Moore neighborhood).
    4. Life&rsquos transition rule goes as follows. At each time step t exactly one of three things can happen to a cell:
      1. Birth: If the cell state at (t - 1) was 0 (dead), the cell state becomes 1 (alive) if exactly three neighbors were 1 (alive) at (t - 1)
      2. Survival: If the cell state at (t - 1) was 1 (alive), the cell state is still 1 if either two or three neighbors were 1 (alive) at (t - 1)
      3. Death: If the cell state at (t - 1) was 1 (alive), the cell state becomes 0 (dead) if either fewer than two or more than three neighbors were 1 (alive) at (t - 1) (cells can die of &ldquoloneliness&rdquo or &ldquooverpopulation&rdquo).

      Life would definitely be considered a Class4 CA by Wolfram&rsquos taxonomy. In this simple setting, periodic structures, stable blocks and complex moving patterns come into existence, even starting from a very simple initial configuration. Conway remarked:

      It&rsquos probable, given a large enough Life space, initially in a random state, that after a long time, intelligent, self-reproducing animals will emerge and populate some parts of the space. (cited in Ilachinski 2001: 131)

      Life-fans explored the CA&rsquos possible patterns of evolution, and shared their findings in what has been called Life&rsquos zoology (Dennett 2003: 41). Here is a small gallery of samples together with snapshots of a typical simulation (for more pictures and animations, see Other Internet Resources at the end). Gliders are the most popular among the basic Life inhabitants: a simple 5-bit structure, a glider can travel the Life grid in a 4-time step cycle:

      Toads are period 2 blinking configurations: together with Blinkers e Beacons they are the simplest oscillators of the universe.

      Eaters have the feature of devouring other configurations, e.g., gliders, maintaining intact their own form (because of this, they play an important role for Life&rsquos computational abilities).

      An Eater devouring a Glider

      A typical evolution of Life starting from random initial conditions may contain all of the above notable figures and much more. Some initial configuration may end up, even after few time steps, into static or simple periodic structures. Other configurations, though, can produce non-periodic, increasingly complex environments whose development can be unpredictable (even in the computational sense we are about to explore). As Ilachinski has suggestively conjectured from this:

      Upon observing the seemingly unlimited complexity and variety of Life&rsquos evolving patterns, it becomes almost impossible to refrain from imagining, along with Conway, that, were the game really to be played on an infinite lattice, there must surely arise true living &ldquolife-forms&rdquo, perhaps themselves evolving into more complex, possibly sentient, &ldquoorganisms&rdquo. (Ilachinski 2001: 133)

      The mathematical literature on CA does not refrain from describing the Life configurations using the same imaginative vocabulary we used: items are born, live, mover around, eat other figures, die, etc. The universe these patterns inhabit may also be described, though, as a collection of individual cells, each of which does not directly depend on what is happening on the macro-scale. And the life on Life can also be described in the simple mathematical language of matrices and discrete sequences. But if one is only told the basic Life rule, one could hardly imagine the complexity it can generate&mdashuntil one sees it. Life&rsquos reputation among scientists and philosophers arguably comes from its challenging naive intuitions about complexity, pattern formation and reality, persistence, and continuity: as a toy universe we ourselves built, we feel we should know in advance what dynamics are allowed. This has been shown to be impossible, in a mathematically precise sense.

      2.6 Life as a Universal Turing Machine

      Like any other CA, Life can be considered a computational device: an initial configuration of the automaton can encode an input string. One can let the system run and, at some point, read the current configuration as the result of the computation performed so far, decoding it into an output string. But exactly what can Life compute? It turns out that Life can compute everything a universal Turing machine can and therefore, taking on board Turing&rsquos Thesis, function as a general purpose computer: a suitable selection of initial conditions can ensure that the system carry out arbitrary algorithmic procedures.

      The proof of the universal computational capacities of Life presented in Berkelamp, Conway, and Guy 1982 consists in showing that the basic building blocks or primitives of standard digital computation can be emulated by appropriate patterns generated by Life&mdashin particular: (a) data storage or memorization, (b) data transmission requiring wires and an internal clock, and (c) data processing requiring a universal set of logic gates, like negation, conjunction and disjunction&mdashan actual Turing machine was later explicitly implemented in Life by Paul Rendell (see Other Internet Resources).

      This finding is not of great engineering importance (no one would spend their time translating &ldquo(24 + 26 / 13)&rdquo into Life) However, it raises a conceptual issue about any universe sharing the capacity of producing and hosting universal computers: because of the aforementioned Halting Theorem, no general algorithm is to decide whether, given some initial configuration as input, Life will eventually die out or halt. It is in this sense that the evolution of the automaton is unpredictable. Given that the development of CA that are computationally universal cannot be predicted by direct mathematical analysis alone, it is no surprise that CA practitioners have adopted the language of philosophy and talked of phenomenological studies of CA (we will come back to this terminology in more detail in Section 3.4 below, discussing how CA model whatever they can model). Here the automaton is realized as a computer software, and the observable emergent properties of its evolution are empirically registered as the computer simulation advances. In Wolfram&rsquos turn of phrase, Life é algorithmically irreducible: no algorithmic shortcut is available to anticipate the outcome of the system given its initial input. &ldquoLife&mdashlike all computationally universal systems&mdashdefines the most efficient simulation of its own behavior&rdquo (Ilachinski 2001: 15). This raises the important philosophical question of the limits of the predictability of any universe capable, just as Life is, of producing and hosting universal computers.

      2.7 Further CA

      Notwithstanding the historical and conceptual centrality of the CA described in this section, many important developments in the field could not be presented in the space allowed for this entry. One can relax some of the assumptions in the general characterization of CA provided in Section 2.1 and get interesting results. The transition rule can be probabilistic and take into consideration more than just one time step (see Richards, Meyer, & Packard 1990: probabilistic automata are widely used to represent the stochastic dynamics of microphysical systems) the cell state updating can be asynchronous (see Ingerson & Buvel 1984) the lattice can be made of non-homogenous cells following different transition rules (see Kauffman 1984) even the discreteness constraint can be relaxed by having the set of states be the set of real numbers (see Wolfram 2002: 155&ndash157).

      CA are also being fruitfully used in connection to the issue of the thermodynamic limits of computation: is there a minimum amount of energy needed to perform a logical operation? Landauer (1961) argued that irreversible logical operations (i.e., operations that, not corresponding to bijections, cannot be run backwards as they entail some information loss) necessarily dissipate energy. The invention of the Fredkin reversible logical gate and of the Billiard Ball Model of reversible computation (Fredkin & Toffoli 1982) strengthened the importance of the link between universal reversible automata and the physical properties of computation (for an overview, see Ilachinski 2001: 309&ndash323 for a sample reversible CA, see Berto, Rossi, & Tagliabue 2016).

      Finally, it is worth mentioning that genetic algorithms have been used with CA to study how evolution creates computation (for a survey of important results, see Mitchell, Crutchfield, & Das 1996). While the aforementioned sources further explore these possibilities, the sample CA models discussed so far will be sufficient for the philosophical arguments we are going to address henceforth.


      Related Links

      Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

      • Radius-1/2 Cellular Automata
        Daniel de Souza Carvalho
      • Sorted Evolutions of Cellular Automata
        Michael Schreiber
      • General Additive Cellular Automata
        Stephen Wolfram
      • Classifying the Complexity and Information of Cellular Automata
        Daniel de Souza Carvalho
      • 3-Color Left/Right Mobile Automata
        Narine Manukyan
      • Totalistic Cellular Automaton with Rule 935912 r = 1, k = 4
        Daniel de Souza Carvalho
      • Five-Neighbor 2D Totalistic Cellular Automata
        Daniel de Souza Carvalho
      • Examples of 1D Three-Color Totalistic Cellular Automata
        Abigail Nussey
      • Circular View of the Means of Two-Color Totalistic 2D Cellular Automata
        Daniel de Souza Carvalho
      • Patterns from the Mean of Two-Color Totalistic 2D Cellular Automata
        Daniel de Souza Carvalho
      • Expected Returns of the Dow Industrials, Beta Model
        Jason Cawley
      • Comparing Data on Countries
        Jason Cawley
      • Rank Plots for Countries
        Jason Cawley
      • Country Groups
        Jason Cawley
      • Country Data and Benford&aposs Law
        Jason Cawley
      • Cellular Automata with Global Control
        Jason Cawley
      • Simulating the 2008 U.S. Presidential Election
        Jason Cawley
      • Exploring Social Choice Theory
        Jason Cawley
      • Fully Random, Five-Rule Interactive Cellular Automata (ICA)
        Jason Cawley
      • Algorithmic Architecture with Cellular Automata
        Jason Cawley
      • Modeling Return Distributions
        Jason Cawley
      • Expected Returns of the Dow Industrials, Fama-French Model
        Jason Cawley
      • Credit Risk
        Jason Cawley
      • Highlighting Patterns in Cellular Automata
        Jason Cawley
      • Markov Volatility Random Walks
        Jason Cawley
      • Asset Allocation
        Jason Cawley
      • Mean-Reverting Random Walks
        Jason Cawley
      • An Amoeba Problem
        Jason Cawley
      • Totalistic K3 R 1/2 Cellular Automata
        Jason Cawley
      • Cellular Automaton Model of Pine Savanna Dynamics in Response to Fire and Hurricanes
        Jason Cawley


      Assista o vídeo: Autômatos celulares (Novembro 2021).