-------- 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
[email protected]
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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
