A cellular automaton in a Penrose-tiling universe
I like cellular automata, and I recall taking a course about them in graduate school. And I find Penrose tiling quite intriguing. But the idea that you can build a Game of Life universal Turing machine in a Penrose-tiling universe is surprising. Be sure to click the video link to see a Penrose tiling glider in action. Jacob Aron’s article is in New Scientist:
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. . .
Continue reading. The glider is discussed later in the article, with a link to the video.