FYI -- http://www.newscientist.com/article/dn22222-turing-machine-gives-order-to-ch... 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-everchang... 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