A primeira implementação da auto replicadora de von Neumann, construtor universal.[1] Três gerações de máquina são mostrados: o segundo está quase terminando de construir o terceiro. As linhas de circulação para a direita são as fitas de instruções genéticas, que são copiados juntamente com o corpo das máquinas. A máquina mostrada é executado em uma versão 32-estado do ambiente de von Neumann autômatos celulares, não a sua especificação 29 estado original.
O construtor universal de John von Neumann é uma máquina autorreplicadora em um ambiente autómato celular (AC). 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.[2]
Na especificação de von Neumann, definido como a máquina usando 29 estados, estes estados que constituem os meios de transporte de sinal e operação lógica, e agindo sobre os sinais representados na forma de fluxos de bits. Uma 'fita' de células codifica a sequência de ações a ser executada pela máquina. Usando a cabeça da escrita (denominado um braço de construção) a máquina pode imprimir (construir) um novo padrão de células, permitindo que ele faça uma cópia completa de si mesmo, e a fita.
Propósito
O projeto de von Neumann tem sido tradicionalmente entendida como uma demonstração dos requisitos lógicos para máquina de auto-replicação.[3] No entanto, é evidente que as máquinas, até as mais simples, podem alcançar a auto-replicação. Exemplos triviais incluem crescimento de cristais, Replicação do DNA e Loops Langton. Mas von Neumann estava interessado em algo mais profundo: a universalidade de construção e evolução.[4]
Esse construtor universal pode ser visto como uma simulação abstrata de um montador universal fisico.
Note que as mais simples estruturas CA auto-replicadoras(especialmente, Byl's loop e o Chou-Reggia loop) não pode existir numa grande variedade de formas e, assim, têm evolvability muito limitada. Outras estruturas CA, tais como o Evoloop são um tanto evolutivo, mas ainda não suportam evolução ilimitada. Comummente, replicadores simples não contêm totalmente a máquina de construção, não havendo um grau em que o replicador de informação é copiado por seu ambiente circundante. Embora o desenho de Von Neumann é uma construção lógico, é, em princípio, uma concepção que possam ser instanciado como uma máquina física. A questão da contribuição ambiental para a replicação é um pouco aberta, uma vez que existem diferentes concepções de matéria-prima e sua disponibilidade.
O conceito de construtor universal não é trivial devido à existência de padrões do jardim do Éden. Mas uma definição mais simples é que um construtor universal é capaz de construir qualquer padrão finito de células não-excitadas (quiescente).
A percepção crucial de Von Neumann é que parte do replicador tem um uso duplo, sendo tanto um componente ativo do mecanismo de construção, e sendo o alvo de um processo de cópia passiva. Esta parte é tocada pela fita de instruções em combinação Von Neumann do construtor universal, mais fita de instrução.
A combinação de um construtor universal e uma fita de instruções que i) permitir a auto-replicação, e também ii) garantia de que o crescimento complexidade aberta observada em organismos biológicos era possível.[3] A imagem abaixo ilustra essa possibilidade.
Esta visão é ainda mais notável porque precedeu a descoberta da estrutura da molécula de DNA por Watson and Crick, que seguiu o experimento Avery-MacLeod-McCarty que identificou o DNA como transportador molecular de informação genética em organismos vivos.[5] A molécula de DNA é processado por mecanismos separados que realizam as suas instruções e copia o DNA para inserção na célula de novas construções. A capacidade de atingir aberta evolução reside no facto de que, assim como na natureza, os erros (mutações) na cópia da fita genética pode levar a variantes viáveis do autómato, que pode então evoluir via seleção natural.
A demonstração da capacidade da máquina de von Neumann para apoiar mutações hereditárias. (1) A uma iteração anterior, uma mutação foi adicionada manualmente para a fita da máquina de segunda geração do. (2) gerações posteriores tanto exibir a tela [fenótipo [
da mutação (um desenho de uma flor) e passar a mutação aos seus filhos, já que a fita é copiada de cada vez. Este exemplo ilustra como o design de von Neumann permite o crescimento complexidade (em teoria) uma vez que a fita pode especificar uma máquina que é mais complexa do que a uma tornando-.]]
Implementação
Arthur Burks e outros estendeu o trabalho de von Neumann, dando uma visão mais clara e mais completo conjunto de detalhes sobre o projeto e operação de von Neumann auto-replicador. O trabalho de JW Thatcher é particularmente notável, pois ele simplificou o design. Ainda assim, o seu trabalho não deu uma completa design da célula, por célula, de uma configuração capaz de demonstrar auto-replicação.
Renato Nobili e Umberto Pesavento publicou o primeiro, totalmente implementado, auto-reproduz autômato celular em 1995, quase 50 anos após o trabalho de von Neumann.[1][6] They used a 32-state cellular automaton instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing and a more compact design. They also published an implementation of a general constructor within the original 29-state CA but not one capable of complete replication - the configuration cannot duplicate its tape, nor can it trigger its offspring; the configuration can only construct.[6][7]
Em 2007, publicou uma implementação Nobili 32-estado que usa codificação run-length para reduzir significativamente o tamanho da fita.
Em 2008, William R. Buckley publicado duas configurações que são auto-replicadores dentro do original 29-CA estado de von Neumann.[7] Buckley afirma que a passagem de sinal dentro do von Neumann autómatos celulares de 29-estado não é necessário para a construção de auto-replicantes.[7] Buckley também aponta que, para efeitos 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 do que uma cópia. Conforme publicado, o projeto 1995 de Nobili-Pesavento não cumprir este requisito, mas o projeto 2007, de Nobili faz, o mesmo é verdade para configurações Buckley.
Em 2004, D. Mange et al. relatou uma implementação de um auto-replicador que é consistente com os projetos de von Neumann.[8]
Em 2009, Buckley publicou com o Golly uma terceira configuração para o autómato celular de von Neumann de 29 estados, que pode executar qualquer auto-replicação holística, ou auto-replicação pela construção parcial. Esta configuração também demonstra que o cruzamento de sinal não é necessário para a construção de auto-replicantes dentro do autómato celular de von Neumann de 29 estados.
C. L. Nehaniv em 2002,[9] e também Y. Takada et al. em 2004,[10] propuseram um construtor universal implementado diretamente num autómato celular assíncrona, em vez de em cima de um autómato celular síncrono.
Deve-se notar que nenhuma das configurações referidas neste artigo é um construtor universal; nenhuma pode, por exemplo, construir o órgão de cruzamento em tempo-real criado por Gorman.[7] Até à data, nenhuma configuração capaz de construção universal foi demonstrada para o modelo de 29 estados de von Neumann.
Praticidade
Custo computacional
Todas as implementações da máquina de von Neumann auto-reproduz exigem recursos consideráveis[carecede fontes?] para ser executado no computador. Por exemplo, no Nobili-Pesavento 32-estado implementação mostrada acima, enquanto o corpo da máquina é apenas 6329 não vazios células (dentro de um rectângulo de tamanho 97x170), requer uma fita que é 145315 células longas, e leva 63 mil milhões (63 bilhões) de passos de tempo para replicar. Um simulador a executar 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 a réplica da sua própria máquina. No entanto, em 2008, o algoritmo hashlife foi estendido para suportar os conjuntos de regras estaduais e 29-32-Estado em Golly. Num PC moderno, a replicação agora leva apenas alguns minutos, embora seja necessária uma quantidade significativa de memória.
Evoluabilidade
Um dos problemas indicados por Von Neumann era a evolução : como é o crescimento e complexidade dos organismos biológicos possível? A sua máquina mostra como é logicamente possível, usando um construtor universal, mas não mostra como é possível na prática. Em seu trabalho inacabado, ele analisa brevemente o conflito e as interações entre replicadores mas na prática o seu modelo não é susceptível de se tornar uma unidade útil da evolução porque é muito frágil.[3]
↑von Neumann, John; Burks, Arthur W. (1966), Theory of Self-Reproducing Automata., www.walenz.org, consultado em 6 de julho de 2012, arquivado do original(Scanned book online) em 9 de março de 2009
Olá, Construtor universal de Von Neumann. Boas-vindas à Wikipédia! Alerto que algumas contribuições que realizou não possuemfontes confiáveis e independentes, conforme orienta a política de verificabilidade da Wikipédia, por isso seu texto foi removido, modificado ou marcado com o uso de predefinições (como {{sem-fontes}} e {{carece de fontes}}). Para adicionar referências é necessário colocar <ref>referência</ref> após sua edição, substituindo o termo referência pela bibliografia ou ligação de onde obteve a informação que adicionou, de acordo com as orientações de formatação do livro de estilo. Encontre fontes:Google (N•L•A•I•WP refs) •ABW•CAPES.
Por favor, leia com atenção as políticas e regulamentos apresentados acima, assim seu esforço aqui terá um bom resultado. Se, ao ler a política, lhe surgir alguma dúvida, por favor deixe-me uma mensagem em minha página de discussão e quando eu puder lhe responderei, ou então, pode consultar algum membro do programa de tutoria ou um administrador da Wikipédia. Também pode utilizar o assistente para a criação de artigos, que o guiará passo a passo no processo de criação. Saudações e boa sorte em suas edições.
12345Buckley, William R. (2008), Andrew Adamatzky, Ramon Alonso-Sanz, Anna Lawniczak, Genaro Juarez Martinez, Kenichi Morita, Thomas Worsch, ed., «Proc. Automata 2008», Luniver Press, Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata !CS1 manut: Nomes múltiplos: lista de editores (link)
↑Mange, Daniel; Stauffer, A.; Peparaolo, L.; Tempesti, G. (2004), «A Macroscopic View of Self-replication», Proceedings of the IEEE, 92 (12): 1929–1945, doi:10.1109/JPROC.2004.837631
↑Nehaniv, Chrystopher L. (2002), «2002 NASA/DoD Conference on Evolvable Hardware (15-18 July 2002, Alexandria, Virginia, USA)», IEEE Computer Society Press, Self-Reproduction in Asynchronous Cellular Automata, pp.201–209
