arduino, eletrônica, robotica...

Gliders e a Máquina Universal de Turing (hacker needed)

Ok, ok... eu sei que esse tópico beira os limites da nerdice, mas domingo é um dia perigoso, e a patroa me deixou horas demais sozinho lendo a wikipedia no tablet.
Algum hacker de plantão poderia me ajudar a entender essa lógica abaixo?

"Gliders can also be collided with other patterns with interesting results. For example, if two gliders are shot at a block in just the right way, the block will move closer to the source of the gliders. If three gliders are shot in just the right way, the block will move farther away. This "sliding block memory" can be used to simulate a counter, which would be modified by firing gliders at it. It is possible to construct logic gates such as AND, OR and NOT using gliders. One may also build a pattern that acts like a finite state machine connected to two counters. This has the same computational power as a universal Turing machine, so, using the glider, the Game of Life is theoretically as powerful as any computer with unlimited memory and no time constraints: it is Turing complete.[3][4]"
http://en.wikipedia.org/wiki/Glider_(Conway%27s_Life)

Eu entendi que usando os gliders daria para simular portas lógicas e a partir daí construir uma máquina de estados finitos, mas não entendi porque ela teria teoricamente memória infinita, simulando a máquina universal de Turing.

Amanha eu volto para a bancada e paro de ficar viajando...

Curtir

0 membros curtem isto

Exibições: 688

▶ Responder esta

Respostas a este tópico

Permalink Responder até Alexander Hugo Tartari em 7 novembro 2011 at 9:44

Marcelo vai me fazer relembrar as aulas de Teoria da Computação hahahaha

Até onde lembro, a máquina de Turing tem memória infinita pois é um computador teórico.

É mais ou menos o que acontece com o "condutor ideal" na eletrônica, com resistência zero. Só existe na teoria.

Então acho que o que o artigo está querendo dizer é que isso é possível, mas na teoria.

Essas coisas muito teóricas são complicadas demais :/

Mas também é possível que este artigo esteja equivocado, afinal, é Wikipedia...

▶ Responder

Permalink Responder até Marcelo Rodrigues em 7 novembro 2011 at 13:19

Alexander,

Pois é... eu entendi isso. O que não entendi é como ficaria a "montagem" dos contadores e dos gliders para resultar na máquina universal.

O Fernando Gil achou a tal da montagem. Embora seja só uma imagem, talvez traga mais luz.

Fernando, por favor, posta aqui aquela imagem que você mostrou no lab.

Abraços!!

▶ Responder

Permalink Responder até Marcelo Rodrigues em 8 novembro 2011 at 15:11

Achei.

http://en.wikipedia.org/wiki/Conway_Game_of_Life

▶ Responder

Permalink Responder até Fernando Gil em 10 agosto 2012 at 11:45

Da Slashdot:

"Conway's Game of Life is now forty two years old, but it continues to inspire as well as being the basis of an actively researched field, with computer scientists now announcing they have found a new form of the famous 'glider' pattern (once suggested by Eric S Raymond as the insignia of computer hackers) that runs over a so-called Penrose universe."