Construtor universal de Von Neumann
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.
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. [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 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
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] | [2] | Nobili (32 estados) | 97 × 170 | 6329 | 145315 | 22,96 | 6,34 × 1010 | nenhuma | 5 bits | construtor holístico | não repetível | linear |
Nobili, 2007 | SR_CCN_AP.EVN [3][4] | Nobili (32 estados) | 97 × 100 | 5313 | 56325 | 10,60 | 9,9 × 109 | codificação por comprimento da série limitado | 5 bits | construtor holístico | repetível | super-linear |
Buckley, 2009 | codon3.rle | Nobili (32 estados) | 116 × 95 | 4855 | 23577 | 4,86 | 1,63 × 109 | recuo automático/geração de bits/sobreposição de códigos | 3 bits | construtor holístico | repetível | super-linear |
Buckley, 2008 | codon4.rle [5] | Nobili (32 estados) | 109 × 59 | 3574 | 37780 | 10,57 | 4,31 x 109 | recuo automático/geração de bits | 4 bits | construtor holístico | repetível | linear |
Buckley, 2008 | codon5.rle [6] | Nobili (32 estados) | 112 × 50 | 3343 | 44155 | 13,21 | 5.87 x 109 | recuo automático | 5 bits | construtor holístico | repetível | linear |
Buckley, 2008[7] | replicator.mc [7] | von Neumann (29 estados) | 312 × 132 | 18,589 | 294,844 | 15.86 | 2.61?×?1011 | recuo automático | 5 bits | construtor holístico | repetível | linear |
Buckley, 2009 | PartialReplicator.mc [8] | von Neumann (29 estados) | NA | NA | NA | - | ~1,12 x 1014 | nenhum | 4 bits | construtor parcial | repetível | linear |
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[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
Um dos problemas indicados por Von Neumann era a evolução [9]: 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 [10] 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
- Exemplo de um braço de leitura de 29 estados.Exemplo de um braço de leitura de 29 estados.
Veja tambem
- Quine (computação)
- Wireworld
Referencias
- ↑ a b c 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
- ↑ 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
- ↑ 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, PMID 11348586, doi:10.1162/106454600300103674
- ↑ «Cópia arquivada». Consultado em 6 de julho de 2012. Arquivado do original em 13 de junho de 2008
- ↑ == 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 termoreferê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: ABW • CAPES • Google (N • L • A).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.
- ↑ a b 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
- ↑ a b c d e 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 !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
- ↑ 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
- Golly - the Cellular Automata Simulation Accelerator Very fast implementation of state transition and support for JvN, GoL, Wolfram, and other systems.
- von Neumann's Self-Reproducing Universal Constructor The original Nobili-Pesavento source code, animations and Golly files of the replicators.
- John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don Hopkins
- A Catalogue of Self-Replicating Cellular Automata. This catalogue complements the Proc. Automata 2008 volume.