Construtor universal de Von Neumann

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Text document with red question mark.svg
Este artigo ou secção contém uma ou mais fontes no fim do texto, mas nenhuma é citada no corpo do artigo, o que compromete a confiabilidade das informações. (desde julho de 2012)
Por favor, melhore este artigo introduzindo notas de rodapé citando as fontes, inserindo-as no corpo do texto quando necessário.
Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo (desde julho de 2012).
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Nuvola apps important.svg
A tradução deste artigo ou se(c)ção está abaixo da qualidade média aceitável.
É possível que tenha sido feita por um tradutor automático ou por alguém que não conhece bem o português ou a língua original do texto. Caso queira colaborar com a Wikipédia, tente encontrar a página original e melhore este artigo conforme o guia de tradução.
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 Constructor Universal de John von Neumann é uma Máquina autorreplicadora em um ambiente Autómato celular (AC). 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, concluido 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-fonte]

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. Comumente, 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-fonte]

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. [1]

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 publicado com Golly uma terceira configuração para von Neumann 29 estado de autômatos celulares, que pode executar qualquer holística auto-replicação, 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 von Neumann 29-estado autómatos celulares.[2]

C. L. Nehaniv em 2002, e também Y. Takada et al. em 2004, propôs um construtor universal diretamente implementado em cima de um autômato celular assíncrona, em vez de em cima de um síncrono autômato celular. 9 10

Comparação das implementações[editar | editar código-fonte]

implementação fonte regras area retangular número de células comprimento da fita taxa passo de tempo para replicação compressão do codigo da fita comprimento do codigo da fita mecanismo de replicação tipo de replicação taxa de crescimento
Nobili-Pesavento, 1995 1 [3] Nobili 32-state 97 × 170 6,329 145,315 22.96 6.34?×?1010 none 5 bits holistic constructor non-repeatable linear
Nobili, 2007 SR_CCN_AP.EVN [4][5] Nobili 32-state 97 × 100 5,313 56,325 10.60 9.59?×?109 run-length limited encoding 5 bits holistic constructor repeatable super-linear
Buckley, 2009 codon3.rle Nobili 32-state 116 × 95 4,855 23,577 4.86 1.63 x 109 auto-retraction/bit generation/code overlay 3 bits holistic constructor repeatable super-linear
Buckley, 2008 codon4.rle [6] Nobili 32-state 109 × 59 3,574 37,780 10.57 4.31 x 109 auto-retraction/bit generation 4 bits holistic constructor repeatable linear
Buckley, 2008 codon5.rle [7] Nobili 32-state 112 × 50 3,343 44,155 13.21 5.87 x 109 auto-retraction 5 bits holistic constructor repeatable linear
Buckley, 20087 replicator.mc [8] von Neumann 29-state 312 × 132 18,589 294,844 15.86 2.61?×?1011 auto-retraction 5 bits holistic constructor repeatable linear
Buckley, 2009 PartialReplicator.mc [9] von Neumann 29-state NA NA NA - ~1.12 x 1014 none 4 bits partial constructor repeatable linear

It should be noted that none of the configurations discussed in this article is a universal constructor; none could, for instance, construct the real-time crossing organ devised by Gorman.7 To date, no configuration capable of universal construction has been demonstrated for the 29-state model of von Neumann.

praticidade[editar | editar código-fonte]

custo computacional[editar | editar código-fonte]

Todas as implementações da máquina de von Neumann auto-reproduz exigem recursos consideráveis ??para ser executado no computador. Por exemplo, no Nobili-Pesavento 32-estado implementação mostrada acima, enquanto o corpo da máquina é apenas 6,329 não vazios células (dentro de um rectângulo de tamanho 97x170), requer uma fita que é 145,315 células longas, e leva 63 passos_de_tempo bilhões 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 publicado, os autores não tinha visto sua réplica própria máquina. No entanto, em 2008, o hashlife algoritmo foi estendido para suportar os conjuntos de regras estaduais e 29-32-Estado em Golly. Em um PC moderno, a replicação agora leva apenas alguns minutos, embora uma quantidade significativa de memória é necessária.

Evoluabilidade[editar | editar código-fonte]

Problema indicado Von Neumann era a evolução [10]: como é o crescimento e complexidade dos organismos biológicos evolvability possível? 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 [11] 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

Galeria[editar | editar código-fonte]

Veja tambem[editar | editar código-fonte]

Referencias[editar | editar código-fonte]

  1. a b c Pesavento, Umberto (1995), "An implementation of von Neumann's self-reproducing machine" (PDF), Artificial Life (MIT Press) 2 (4): 337–354, doi:10.1162/artl.1995.2.337, PMID 8942052, http://web.archive.org/web/20070418081628/http://dragonfly.tam.cornell.edu/~pesavent/pesavento_self_reproducing_machine.pdf 
  2. von Neumann, John; Burks, Arthur W. (1966) (Scanned book online), Theory of Self-Reproducing Automata., www.walenz.org, arquivado do original em 2008-01-05, http://web.archive.org/web/20080105213853/www.walenz.org/vonNeumann/index.html, visitado em 2008-02-29 
  3. a b c McMullin, B. (2000), "John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...", Artificial Life 6 (4): 347–361, doi:10.1162/106454600300103674, PMID 11348586, http://www.eeng.dcu.ie/~alife/bmcm-alj-2000/ 
  4. http://www.walenz.org/vonNeumann/page0110.html
  5. ==Referências em contribuições recentes==
    Commons-emblem-question book orange.svg

    Olá, Construtor universal de Von Neumann. Algumas contribuições que realizou não possuem referências necessárias para cumprir a política de verificabilidade da Wikipédia, pelo que o texto foi removido, modificado ou marcado com a predefinição {{Sem-fontes}}.

    Para referenciar, é necessário colocar <ref>referência</ref> após sua edição, substituindo referência pela bibliografia ou ligação de onde obteve a informação, de acordo com o livro de estilo.

    Antes de retirar a predefinição, por favor, consulte o usuário que a colocou, ou com alguém que goze da confiança da comunidade (ex. um administrador).

    Por favor, leia as ligações observando o que dizem, 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 da Wikipédia. Se desta vez não o fez, 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. a b Nobili, Renato; Pesavento, Umberto (1996), "Generalised von Neumann's Automata", in Besussi, E.; Cecchini, A. (PDF), Proc. Artificial Worlds and Urban Studies, Conference 1, Venice: DAEST, http://www.pd.infn.it/%7Ernobili/pdf_files/jvnconstr.pdf 
  7. a b c d e Buckley, William R. (2008), "Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata", in Andrew Adamatzky, Ramon Alonso-Sanz, Anna Lawniczak, Genaro Juarez Martinez, Kenichi Morita, Thomas Worsch, Proc. Automata 2008, Luniver Press 
  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), "Self-Reproduction in Asynchronous Cellular Automata", 2002 NASA/DoD Conference on Evolvable Hardware (15-18 July 2002, Alexandria, Virginia, USA), IEEE Computer Society Press, pp. 201–209 
  10. Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki (2004), "Universal Construction on Self-Timed Cellular Automata", in Sloot, P.M.A., ACRI 2004, LNCS 3305, pp. 21–30 

Links externos[editar | editar código-fonte]