Ir para o conteúdo

Construtor universal de Von Neumann

Origem: Wikipédia, a enciclopédia livre.
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

[editar | editar código]

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

[editar | editar código]

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.

Comparação das implementações

[editar | editar código]
implementaçãofonteregrasarea retangularnúmero de célulascomprimento da fitataxapasso de tempo para replicaçãocompressão do codigo da fitacomprimento do codigo da fitamecanismo de replicaçãotipo de replicaçãotaxa de crescimento
Nobili-Pesavento, 1995[1] Nobili (32 estados)97 × 170632914531522,966,34 × 1010nenhuma5 bitsconstrutor holísticonão repetívellinear
Nobili, 2007 SR_CCN_AP.EVN Nobili (32 estados)97 × 10053135632510,609,9 × 109codificação por comprimento da série limitado5 bitsconstrutor holísticorepetívelsuper-linear
Buckley, 2009 codon3.rleNobili (32 estados)116 × 954855235774,861,63 × 109recuo automático/geração de bits/sobreposição de códigos3 bitsconstrutor holísticorepetívelsuper-linear
Buckley, 2008 codon4.rle Nobili (32 estados)109 × 5935743778010,574,31 x 109recuo automático/geração de bits4 bitsconstrutor holísticorepetívellinear
Buckley, 2008 codon5.rle Nobili (32 estados)112 × 5033434415513,215.87 x 109recuo automático5 bitsconstrutor holísticorepetívellinear
Buckley, 2008[7] replicator.mc von Neumann (29 estados)312 × 13218,589294,84415.862.61?×?1011recuo automático5 bitsconstrutor holísticorepetívellinear
Buckley, 2009 PartialReplicator.mc von Neumann (29 estados)NANANA-~1,12 x 1014nenhum4 bitsconstrutor parcialrepetívellinear

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

[editar | editar código]

Custo computacional

[editar | editar código]

Todas as implementações da máquina de von Neumann auto-reproduz exigem recursos consideráveis[carece de 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

[editar | editar código]

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]

Ver também

[editar | editar código]

Referencias

[editar | editar código]
  1. 1 2 3 Pesavento, Umberto (1995), «An implementation of von Neumann's self-reproducing machine» (PDF), MIT Press, Artificial Life, 2 (4): 337–354, PMID 8942052, doi:10.1162/artl.1995.2.337
  2. ↑ 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
  3. 1 2 3 McMullin, B. (2000), «John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...», Artificial Life, 6 (4): 347–361, PMID 11348586, doi:10.1162/106454600300103674
  4. ↑ «Cópia arquivada». Consultado em 6 de julho de 2012. Arquivado do original em 13 de junho de 2008
  5. ↑

    Referências em contribuições recentes

    Olá, Construtor universal de Von Neumann. Boas-vindas à Wikipédia! Alerto que algumas contribuições que realizou não possuem fontes 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.
  6. 1 2 Nobili, Renato; Pesavento, Umberto (1996), Besussi, E.; Cecchini, A., eds., «Proc. Artificial Worlds and Urban Studies, Conference 1» (PDF), Venice: DAEST, Generalised von Neumann's Automata
  7. 1 2 3 4 5 Buckley, 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
  8. ↑ 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
  9. ↑ 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
  10. ↑ Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki (2004), Sloot, P.M.A., ed., «ACRI 2004, LNCS 3305», Universal Construction on Self-Timed Cellular Automata, pp. 21–30

Ligações externas

[editar | editar código]