## Advertising

-------- Original Message -------- FYI -- http://www.newscientist.com/article/dn22222-turing-machine-gives-order-to-chaotic-penrose-universe.html New Scientist Physics & Math Turing machine gives order to chaotic Penrose universe 15:23 29 August 2012 by Jacob Aron

`A theoretical computer built in a mixed-up mathematical universe might not sound like the`

`most practical invention. But the discovery shows that computation can turn up in the most`

`unlikely places, which in turn might spur more realistic models of physical and chemical`

`processes.`

`The computer is what's known as a universal Turing machine, a theoretical construct`

`invented by mathematician Alan Turing that's capable of simulating any computer algorithm.`

`The computers we use today are approximations of Turing's idealised machine.`

`Katsunobu Imai at Hiroshima University in Japan and colleagues have found a way to bring`

`Turing's computational order to an irregular universe based on Penrose tiles – a feat that`

`was considered highly improbable until now.`

`Named after mathematician Roger Penrose, the tiling is an arrangement of two four-sided`

`shapes called a kite and a dart, which covers a two-dimensional plane, without repeating,`

`to create a constantly shifting pattern.`

`The team used this mathematical playing field to make a cellular automaton, a`

`two-dimensional universe in which patterns of cells evolve to create complex structures.`

`The most famous cellular automaton is the Game of Life, a grid of identical square cells`

`that can either be "alive" or "dead".`

`Players have created universal Turing machines in the Game of Life's orderly, two-state`

`universe. But making one work in a more chaotic Penrose universe presented a greater`

`challenge to Imai's team.`

Wired tiles

`The scientists constructed logic gates for their universal Turing machine by assigning one`

`of eight different states to each Penrose tile, with the states changing over time`

`according to a few simple rules.`

`Tiles in the first state act as wires that transmit signals between the logic gates, with`

`the signal itself consisting of either a "front" or "back" state. Four other states manage`

`the redirecting of the signal within the logic gates, while the final state is simply an`

`unused background to keep the various states separate.`

`At first it wasn't clear whether Imai's team would be able to keep their logic gates wired`

`together, as the gates can only appear in certain places where the tiles come together in`

`the right way.`

`However, the team found that a long enough wire would always make the connection, proving`

`that a universal Turing machine is possible in the Penrose universe.`

`Imai will present the work next month at the Automata conference in La Marana on the`

`French island of Corsica.`

More natural modelling

`Earlier this month, researchers also made the unexpected discovery of a highly repetitive`

`object called a glider in the Penrose universeMovie Camera.`

http://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html

`Gliders actually form the basis for a universal Turing machine in the Game of Life,`

`shuttling information around in place of wires. Imai didn't know about the Penrose glider`

`at the time, so he was forced to take an alternative approach.`

`Susan Stepney, a computer scientist at the University of York, UK, says Imai's creation is`

`not very practical as it requires a theoretically infinite number of cells to function.`

`Still, Imai says he was inspired to try and make a universal Turing machine because he`

`wanted to probe the limits of complexity in a Penrose universe. Just showing that it's`

`possible could open the door to other, more useful applications, he says.`

`"Cellular automata are widely used for modelling physical and chemical phenomena, but`

`sometimes the resulting patterns are quite artificial," he explains. While grid-based`

`patterns don't really reflect the natural world, the irregular patterns in Penrose tiling`

`could provide a better model.`

Journal reference: arxiv.org/abs/1208.2771v1 http://arxiv.org/abs/1208.2771v1 _______________________________________________ math-fun mailing list math-...@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.