Construtor universal de Von Neumann
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Julho de 2012) |
A tradução deste artigo está abaixo da qualidade média aceitável. (Julho de 2012) |
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
editarO 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
editarArthur 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
editar| 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
editarCusto computacional
editarTodas 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
editarUm 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
editar-
Exemplo de um braço de leitura de 29 estados.
Veja tambem
editarReferencias
editar- ↑ 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ênciapela 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
- ↑ 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
editar- 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.