Construtor universal Von Neumann - Von Neumann universal constructor

A primeira implementação do construtor universal de auto-reprodução de von Neumann. Três gerações de máquinas são mostradas: a segunda quase terminou de construir a terceira. As linhas à direita são as fitas de instruções genéticas, que são copiadas junto com o corpo das máquinas. A máquina mostrada funciona em uma versão de 32 estados do ambiente de autômato celular de von Neumann, não em sua especificação original de 29 estados.

O construtor universal de John von Neumann é uma máquina auto-replicante em um ambiente de autômato celular (CA). Ele foi projetado na década de 1940, sem o uso de um computador. Os detalhes fundamentais da máquina foram publicados no livro de von Neumann, Theory of Self-Reproducing Automata , concluído em 1966 por Arthur W. Burks após a morte de von Neumann. Embora normalmente não seja tão conhecido como o outro trabalho de von Neumann, é considerado fundamental para a teoria dos autômatos , sistemas complexos e vida artificial . De fato, o ganhador do Prêmio Nobel Sydney Brenner considerou o trabalho de Von Neumann sobre autômatos auto-reprodutores (junto com o trabalho de Turing sobre máquinas de computação) central também para a teoria biológica , permitindo-nos "disciplinar nossos pensamentos sobre máquinas, tanto naturais quanto artificiais".

O objetivo de Von Neumann, conforme especificado em suas palestras na Universidade de Illinois em 1949, era projetar uma máquina cuja complexidade pudesse crescer automaticamente semelhante a organismos biológicos sob seleção natural . Ele perguntou qual é o limite de complexidade que deve ser cruzado para que as máquinas possam evoluir. Sua resposta foi especificar uma máquina abstrata que, quando executada, se replicaria. Em seu projeto, a máquina autorreplicante consiste em três partes: uma "descrição" de ('planta' ou programa para) ela mesma, um mecanismo construtor universal que pode ler qualquer descrição e construir a máquina (sem descrição) codificada nessa descrição e uma copiadora universal que pode fazer cópias de qualquer descrição. Depois que o construtor universal foi usado para construir uma nova máquina codificada na descrição, a copiadora é usada para criar uma cópia dessa descrição, e esta cópia é passada para a nova máquina, resultando em uma replicação funcional da máquina original que pode continuar se reproduzindo. Algumas máquinas farão isso ao contrário, copiando a descrição e construindo uma máquina. Crucialmente, a máquina que se auto-reproduz pode evoluir acumulando mutações da descrição, não a própria máquina, ganhando assim a capacidade de crescer em complexidade.

Para definir sua máquina com mais detalhes, von Neumann inventou o conceito de um autômato celular . O que ele usou consiste em uma grade bidimensional de células, cada uma das quais pode estar em um dos 29 estados a qualquer momento. Em cada etapa de tempo, cada célula atualiza seu estado dependendo dos estados das células vizinhas na etapa de tempo anterior. As regras que regem essas atualizações são idênticas para todas as células.

O construtor universal é um certo padrão de estados celulares neste autômato celular. Ele contém uma linha de células que servem como descrição (semelhante à fita de Turing ), codificando uma sequência de instruções que servem como um "projeto" para a máquina. A máquina lê essas instruções uma por uma e executa as ações correspondentes. As instruções direcionam a máquina a usar seu 'braço de construção' (outro autômato que funciona como um sistema operacional ) para construir uma cópia da máquina, sem a fita descritiva, em algum outro local da grade de células. A descrição não pode conter instruções para construir uma fita de descrição igualmente longa, assim como um contêiner não pode conter um contêiner do mesmo tamanho. Portanto, a máquina inclui uma copiadora separada que lê a fita descritiva e passa uma cópia para a máquina recém-construída. O novo conjunto resultante de construtor universal e copiadoras mais a fita descritiva é idêntico ao antigo e começa a se replicar novamente.

Propósito

Sistema de autômatos de auto-replicação de Von Neumann com capacidade de evolução (Figura adaptada de Notas de aula de Luis Rocha na Universidade de Indiana). i) o sistema autorreplicante é composto de vários autômatos mais uma descrição separada (uma codificação formalizada como uma 'fita' de Turing ) de todos os autômatos: Construtor Universal (A), Copiadora Universal (B), Sistema Operacional (C), funções extras não envolvidas com replicação (D), e descrição separada Φ (A, B, C, D) codificando todos os autômatos. ii) (Topo) o Construtor Universal produz (decodifica) autômatos a partir de sua descrição ( modo ativo de descrição); (Parte inferior) Copiadora universal copia a descrição de autômatos ( modo passivo de descrição); Mutações Φ (D ') para descrição Φ (D) (sem mudanças no autômato D diretamente) se propagam para o conjunto de autômatos produzidos na próxima geração, permitindo que (autômato + descrição) o sistema continue se replicando e evoluindo (D → D'). O processo ativo de construção a partir de uma descrição é paralelo à tradução do DNA , o processo passivo de copiar a descrição é paralelo à replicação do DNA e a herança das descrições mutadas é paralela à herança vertical de mutações de DNA em Biologia, e foram propostas por Von Neumann antes da descoberta da estrutura de a molécula de DNA e como ela é traduzida e replicada separadamente na célula.

O projeto de Von Neumann tem sido tradicionalmente entendido como uma demonstração dos requisitos lógicos para a autorreplicação da máquina. No entanto, está claro que máquinas muito mais simples podem realizar a autorreplicação. Os exemplos incluem crescimento semelhante a um cristal trivial , replicação de modelo e loops de Langton . Mas von Neumann estava interessado em algo mais profundo: construção, universalidade e evolução.

Observe que as estruturas CA autorreplicantes mais simples (especialmente, o loop de Byl e o loop de Chou-Reggia ) não podem existir em uma ampla variedade de formas e, portanto, têm capacidade de evolução muito limitada . Outras estruturas de CA, como o Evoloop, são um pouco evolutivas, mas ainda não oferecem suporte à evolução aberta. Comumente, replicadores simples não contêm totalmente a maquinaria de construção, havendo um grau em que o replicador é uma informação copiada pelo ambiente circundante. Embora o projeto de Von Neumann seja uma construção lógica, é, em princípio, um projeto que poderia ser instanciado como uma máquina física. Na verdade, esse construtor universal pode ser visto como uma simulação abstrata de um montador universal físico . A questão da contribuição ambiental para a replicação é um tanto aberta, uma vez que existem diferentes concepções de matéria-prima e sua disponibilidade.

O insight crucial de Von Neumann é que a descrição da máquina, que é copiada e passada aos filhos separadamente por meio da copiadora universal, tem um uso duplo; sendo um componente ativo do mecanismo de construção na reprodução e sendo o alvo de um processo de cópia passiva . Este papel é desempenhado pela descrição (semelhante a Turing 's fita de instruções ) em combinação de construtor universal e copiadora universal de Von Neumann. A combinação de um construtor universal e copiadora, mais uma fita de instruções conceitua e formaliza i) autorreplicação e ii) evolução aberta, ou crescimento da complexidade observada em organismos biológicos.

Essa percepção é ainda mais notável porque precedeu a descoberta da estrutura da molécula de DNA por Watson e Crick e como ela é traduzida e replicada separadamente na célula - embora tenha seguido o experimento Avery-MacLeod-McCarty que identificou o DNA como o portador molecular de informação genética em organismos vivos. A molécula de DNA é processada por mecanismos separados que executam suas instruções ( tradução ) e copiam ( replicam ) o DNA para células recém-construídas. A capacidade de atingir uma evolução aberta reside no fato de que, assim como na natureza, erros ( mutações ) na cópia da fita genética podem levar a variantes viáveis ​​do autômato, que podem então evoluir por meio da seleção natural . Como disse Brenner:

Turing inventou o computador com programa armazenado e von Neumann mostrou que a descrição é separada do construtor universal. Isso não é trivial. O físico Erwin Schrödinger confundiu o programa e o construtor em seu livro de 1944 O que é a vida ?, no qual ele viu os cromossomos como ″ o plano do arquiteto e o trabalho do construtor em um ″. Isto está errado. O script de código contém apenas uma descrição da função executiva, não a função em si.

-  Sydney Brenner

Evolução da Complexidade

O objetivo de Von Neumann, conforme especificado em suas palestras na Universidade de Illinois em 1949, era projetar uma máquina cuja complexidade pudesse crescer automaticamente semelhante a organismos biológicos sob seleção natural . Ele perguntou qual é o limite de complexidade que deve ser cruzado para que as máquinas possam evoluir e crescer em complexidade. Seus designs de “prova de princípio” mostraram como isso é logicamente possível. Ao usar uma arquitetura que separa um construtor programável de uso geral ("universal") de uma copiadora de uso geral, ele mostrou como as descrições (fitas) de máquinas poderiam acumular mutações na autorreplicação e, assim, desenvolver máquinas mais complexas (a imagem abaixo ilustra esta possibilidade.). Este é um resultado muito importante, pois antes disso, pode-se conjeturar que existe uma barreira lógica fundamental para a existência de tais máquinas; nesse caso, os organismos biológicos, que evoluem e crescem em complexidade, não poderiam ser “máquinas”, como convencionalmente entendido. O insight de Von Neumann foi pensar na vida como uma Máquina de Turing, que, da mesma forma, é definida por uma "cabeça" de máquina determinada pelo estado separada de uma fita de memória.

Na prática, quando consideramos a implementação particular de autômatos que Von Neumann buscou, concluímos que ela não produz muita dinâmica evolutiva porque as máquinas são muito frágeis - a grande maioria das perturbações faz com que elas efetivamente se desintegrem. Assim, é o modelo conceitual delineado em suas palestras em Illinois que é de maior interesse hoje, porque mostra como uma máquina pode, em princípio, evoluir. Essa percepção é ainda mais notável porque o modelo precedeu a descoberta da estrutura da molécula de DNA, conforme discutido acima. É também digno de nota que o projeto de Von Neumann considera que as mutações em direção a uma maior complexidade precisam ocorrer nos (descrições dos) subsistemas não envolvidos na própria auto-reprodução, conforme conceitualizado pelo autômato adicional D que ele considerava desempenhar todas as funções não diretamente envolvidas na reprodução. (veja a Figura acima com o Sistema de Autômatos de Auto-replicação de Von Neumann com a capacidade de evoluir.) De fato, em organismos biológicos apenas variações muito menores do código genético foram observadas, o que corresponde ao raciocínio de Von Neumann de que o construtor universal ( A ) e Copier ( B ) que não evoluem, deixando toda a evolução (e crescimento de complexidade) para autômato D . Em seu trabalho inacabado, Von Neumann também considera brevemente o conflito e as interações entre suas máquinas de auto-reprodução, no sentido de compreender a evolução das interações ecológicas e sociais de sua teoria das máquinas de auto-reprodução.

Uma demonstração da capacidade da máquina de von Neumann de suportar mutações hereditárias. (1) Em um passo de tempo anterior, uma mutação foi adicionada manualmente à fita da máquina de segunda geração. (2) As gerações posteriores exibem o fenótipo da mutação (o desenho de uma flor) e passam a mutação para seus filhos, já que a fita é copiada a cada vez. Este exemplo ilustra como o design de von Neumann permite o aumento da complexidade (em teoria), uma vez que a fita pode especificar uma máquina que é mais complexa do que aquela que a está fabricando.

Implementações

Na teoria dos autômatos, o conceito de um construtor universal não é trivial devido à existência de padrões do Jardim do Éden . Mas uma definição simples é que um construtor universal é capaz de construir qualquer padrão finito de células não excitadas (quiescentes).

Arthur Burks e outros estenderam o trabalho de von Neumann, dando um conjunto de detalhes muito mais claro e completo sobre o projeto e operação do auto-replicador de von Neumann. O trabalho de JW Thatcher é particularmente notável, pois ele simplificou muito o design. Ainda assim, seu trabalho não produziu um projeto completo, célula por célula, de uma configuração capaz de demonstrar autorreplicação.

Renato Nobili e Umberto Pesavento publicaram o primeiro autômato celular auto-reprodutor totalmente implementado em 1995, quase cinquenta anos após o trabalho de von Neumann. Eles usaram um autômato celular de 32 estados em vez da especificação original de 29 estados de von Neumann , estendendo-o para permitir um cruzamento de sinais mais fácil, função de memória explícita e um design mais compacto. Eles também publicaram uma implementação de um construtor geral dentro da CA original de 29 estados, mas não capaz de replicação completa - a configuração não pode duplicar sua fita, nem pode disparar sua prole; a configuração pode apenas construir.

Em 2004, D. Mange et al. relataram uma implementação de um autorreplicador que é consistente com os projetos de von Neumann.

Em 2007, a Nobili publicou uma implementação de 32 estados que usa codificação run-length para reduzir significativamente o tamanho da fita.

Em 2008, William R. Buckley publicou duas configurações que são auto-replicadoras dentro do CA original de 29 estados de von Neumann. Buckley afirma que o cruzamento do sinal dentro dos autômatos celulares de 29 estados de von Neumann não é necessário para a construção de auto-replicadores. Buckley também aponta que, para fins de evolução, cada replicador deve retornar à sua configuração original após a replicação, a fim de ser capaz (em teoria) de fazer mais de uma cópia. Conforme publicado, o projeto de 1995 de Nobili-Pesavento não cumpre esse requisito, mas o projeto de 2007 de Nobili sim; o mesmo se aplica às configurações de Buckley.

Em 2009, Buckley publicou com Golly uma terceira configuração para autômatos celulares de 29 estados de von Neumann, que podem realizar auto-replicação holística ou auto-replicação por construção parcial. Esta configuração também demonstra que o cruzamento de sinal não é necessário para a construção de auto-replicadores dentro de autômatos celulares de 29 estados de von Neumann.

CL Nehaniv em 2002, e também Y. Takada et al. em 2004, propôs um construtor universal diretamente implementado sobre um autômato celular assíncrono, ao invés de um autômato celular síncrono.

Comparação de implementações

Implementação Fonte Conjunto de regras Área retangular Número de células Comprimento da fita Razão Período Compressão de código de fita Comprimento do código da fita Tipo de código de fita Mecanismo de replicação Tipo de replicação Taxa de crescimento
Nobili-Pesavento, 1995 Nobili 32-state 97 × 170 6.329 145.315 22,96 6,34  ×  10 10 Nenhum 5 bits binário construtor holístico não repetível linear
Nobili, 2007 SR_CCN_AP.EVN Nobili 32-state 97 × 100 5.313 56.325 10,60 9,59  ×  10 9 codificação limitada de comprimento de execução 5 bits binário construtor holístico Repetivel superlinear
Buckley, 2008 codon5.rle Nobili 32-state 112 × 50 3.343 44.155 13,21 5,87  ×  10 9 auto-retração 5 bits binário construtor holístico Repetivel linear
Buckley, 2008 replicator.mc von Neumann 29-state 312 × 132 18.589 294.844 15,86 2,61  ×  10 11 auto-retração 5 bits binário construtor holístico Repetivel linear
Buckley, 2008 codon4.rle Nobili 32-state 109 × 59 3.574 37.780 10,57 4,31  ×  10 9 auto-retração / geração de bits 4 bits binário construtor holístico Repetivel linear
Buckley, 2009 codon3.rle Nobili 32-state 116 × 95 4.855 23.577 4,86 1,63  ×  10 9 auto-retração / geração de bits / sobreposição de código 3 bits binário construtor holístico Repetivel superlinear
Buckley, 2009 PartialReplicator.mc von Neumann 29-state 2063 × 377 264.321 N / D - ≈ 1,12  ×  10 14 Nenhum 4 bits binário construtor parcial Repetivel linear
Goucher & Buckley, 2012 phi9.rle Nobili 32-state 122 × 60 3957 8920 2,25 - auto-retração / geração de bits / sobreposição de código / duração limitada 3+ bits ternário construtor holístico Repetivel superlinear

Conforme definido por von Neumann, a construção universal envolve a construção de configurações passivas, apenas. Como tal, o conceito de construção universal constituiu nada mais do que um artifício literário (ou, neste caso, matemático). Facilitou outra prova, como a de que uma máquina bem construída pode se envolver em autorreplicação, enquanto a própria construção universal foi simplesmente assumida em um caso mínimo. A construção universal sob este padrão é trivial. Conseqüentemente, embora todas as configurações dadas aqui possam construir qualquer configuração passiva, nenhuma pode construir o órgão de cruzamento em tempo real idealizado por Gorman.

Praticidade e custo computacional

Todas as implementações da máquina de auto-reprodução de von Neumann requerem recursos consideráveis ​​para funcionar no computador. Por exemplo, na implementação Nobili-Pesavento de 32 estados mostrada acima, embora o corpo da máquina tenha apenas 6.329 células não vazias (dentro de um retângulo de tamanho 97x170), ela requer uma fita com 145.315 células de comprimento e 63 bilhões de passos de tempo para replicar. Um simulador rodando a 1.000 passos de tempo por segundo levaria mais de 2 anos para fazer a primeira cópia. Em 1995, quando a primeira implementação foi publicada, os autores não tinham visto sua própria máquina replicar. No entanto, em 2008, o algoritmo hashlife foi estendido para oferecer suporte aos conjuntos de regras de 29 e 32 estados em Golly . Em um PC desktop moderno, a replicação agora leva apenas alguns minutos, embora uma quantidade significativa de memória seja necessária.

Galeria de animação

  • Exemplo de um braço de leitura de 29 estados.

Veja também

Referências

links externos