Get best of the week

Gerando números pseudo-aleatórios usando um autômato celular: Regra 30

Os geradores de números pseudo-aleatórios fornecem números deterministicamente, mas geralmente esses números parecem não periódicos (aleatórios). Pelo menos na maioria dos casos, o uso de tais números geralmente acontece. O gerador pega um valor inicial (idealmente um número aleatório verdadeiro) e gera uma sequência de números, funcionando como uma função do valor inicial e / ou do número anterior na sequência. Esses números são pseudo-aleatórios (e não aleatórios), devido ao fato de que, se o valor inicial transmitido ao gerador for conhecido, esses números poderão ser gerados novamente algoritmicamente. Números aleatórios verdadeiros são gerados usando hardware especial ou certos fenômenos físicos - flutuações de pulso no volume sanguíneo, pressão atmosférica, ruído térmico, processos quânticos e assim por diante.



Existem muitas maneiras de gerar números pseudo-aleatórios. Por exemplo, o algoritmo Blum - Blum - Shub , o método do quadrado médio , o método de Fibonacci com atrasos . Hoje falaremos sobre a geração de números aleatórios usando a Regra 30 , que usa uma abordagem ambígua envolvendo o uso de um modelo de autômato celular . Esse método passou em muitos testes padrão de número aleatório e foi usado no Mathematica para gerar números inteiros aleatórios.

Autômato celular


Antes de chegarmos ao assunto da Regra 30, vamos dedicar algum tempo nos autômatos celulares. Um autômato celular é um modelo discreto que consiste em uma grade regular de células de qualquer dimensão. Cada uma das células da rede pode estar em um conjunto finito de estados. Além disso, para cada célula, é definido um conceito como "vizinhança". Nas proximidades de uma determinada célula, por exemplo, todas as células localizadas a uma distância não superior a 2 dela podem entrar. Existem regras que determinam como as células interagem umas com as outras e passam para a próxima geração (estado). Essas regras são representadas principalmente por funções matemáticas (programáveis), que dependem do estado atual das células e do estado de seus vizinhos.


Descrição do autômato celular A

descrição do autômato celular da figura anterior permite descobrir que cada célula pode estar em um dos dois estados finais -0(mostrado em vermelho) e1(mostrado em preto). Cada célula passa para a próxima geração, assumindo um novo estado resultante da aplicação da operaçãoXORaos seus oito vizinhos. A primeira geração (estado inicial) da rede é definida aleatoriamente. A operação deste autômato celular é mostrada abaixo.




Autômato celular baseado em XOR em ação A idéia de um autômato celular surgiu na década de 1940, graças a Stanislav Ulam e John von Neumann . Autômatos celulares encontraram aplicação em ciência da computação, matemática, física, na teoria de sistemas complexos, em biologia teórica e em problemas de modelagem da microestrutura de mídia e materiais. Na década de 1980, Stephen Wolfram conduziu um estudo sistemático de um autômato celular unidimensional (também chamado de autômato celular elementar), no qual a Regra 30 se baseia.

Regra 30


A regra 30 é um autômato celular elementar (unidimensional) no qual cada célula pode residir em um dos dois estados finais: 0(células vermelhas na figura abaixo) e 1(células pretas). A vizinhança da célula é representada por seus dois vizinhos mais próximos, localizados à esquerda e à direita dela. O próximo estado (geração) de uma célula depende do seu estado atual e do estado de seus vizinhos. As regras para a transição de células para o próximo estado são mostradas na figura a seguir.


Regra 30

Estas regras de transição para um novo estado de células podem ser simplificadas, escritas comoleft XOR (central OR right).

Nós produzimos as células do autômato na forma de uma rede bidimensional, cada linha representando uma geração (estado). Quando a próxima geração (estado) de células é calculada, ela é exibida abaixo do último estado conhecido. Cada linha contém um número finito de células que, no final, fazem um loop.


Regra 30 em ação

O padrão acima surge do estado inicial (linha 0) quando uma célula tem um estado1(preto) e todas as células ao seu redor têm um estado0(vermelho). O estado das células na próxima geração (linha 1) é calculado de acordo com a regra acima. A grade vertical representa o tempo e as interseções de linhas e colunas representam o estado de uma célula específica em um estágio específico do desenvolvimento do sistema.


Geração te geração t + 1

À medida que o padrão se desenvolve, triângulos vermelhos de tamanhos diferentes geralmente aparecem nele, mas, em geral, um padrão distinguível não pode ser reconhecido na estrutura resultante. O fragmento acima da rede é feito em um momento arbitrariamente escolhido. Aqui você pode ver o caos e a aperiodicidade. Esta propriedade é a Regra 30 e é usada para gerar números pseudo-aleatórios.

Geração de números pseudo-aleatórios


Como já mencionado, a regra 30 demonstra um comportamento aperiódico e caótico. Como resultado, sua aplicação leva à criação de padrões complexos e, ao que parece, aleatórios, de acordo com regras simples e bem definidas. Para gerar números aleatórios usando a Regra 30, é usada a coluna de treliça central, a partir da qual uma sequência de nbits aleatórios é selecionada , a partir da qual o nnúmero aleatório de bits desejado é gerado . O próximo número aleatório é gerado usando os seguintes nbits da coluna.


Gerando números aleatórios usando a Regra 30

Se você sempre começar a selecionar células da primeira linha, a sequência de números gerada sempre será previsível. E não é disso que precisamos. Para criar números pseudo-aleatórios, usaremos um valor inicial aleatório (por exemplo, o horário atual), pularemos o número correspondente de linhas e, depois disso, selecionaremos seqüências denlinhas e criaremos números aleatórios com base nelas.

Os números pseudo-aleatórios gerados usando a Regra 30 não são criptograficamente seguros, mas são adequados para simulações - até que utilizemos valores iniciais inadequados como0.

Uma das principais vantagens do uso da Regra 30 para gerar números pseudo-aleatórios é que você pode criar muitos números aleatórios no modo paralelo selecionando aleatoriamente muitas colunas de comprimento n bits. Aqui é um exemplo de uma sequência pseudo-aleatória de números de 8 bits gerado por este método, utilizando o valor inicial 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

Além disso, o valor inicial pode ser usado para definir o estado inicial do modelo (linha nº 0). Como resultado, números pseudo-aleatórios podem ser obtidos simplesmente escolhendonbit da coluna central, começando na linha zero. Essa abordagem é mais eficaz, mas é altamente dependente da qualidade do valor inicial. Um valor inicial selecionado incorretamente pode levar ao aparecimento de números bem previstos. Uma demonstração dessa abordagem pode ser encontrada aqui .

Regra 30 no mundo real


A regra 30 pode ser vista na natureza, na forma de um padrão na concha da espécie gastrópode Conus . A estação de trem de Cambridge North é emoldurada por painéis que representam os resultados evolutivos de um modelo construído usando a Regra 30.

Sumário


Se você achar a Regra 30 interessante, recomendo escrever sua própria simulação usando a biblioteca p5 . Esse algoritmo pode ser implementado de uma forma bastante geral, o que permitirá que o mesmo programa gere padrões para regras diferentes - 90, 110, 117 e assim por diante. Padrões gerados usando várias regras são muito interessantes. Se você quiser, você pode ir para o próximo nível. Você pode expandir o modelo para três dimensões e explorar a evolução dos padrões. Eu acho que a programação pode trazer muito prazer se tiver um componente visual.

É incrível quando dois campos da ciência aparentemente não relacionados, autômatos celulares e criptografia, se combinam para criar algo surpreendente. Embora o algoritmo descrito aqui não seja mais amplamente utilizado devido ao surgimento de algoritmos mais eficientes, ele nos encoraja a usar criativamente autômatos celulares.

Queridos leitores! Quais geradores de números pseudo-aleatórios você usa?

More articles:


All Articles