Slashdot Mirror
Universal Turing Machine In Penrose Tile Cellular Automata
New submitter submeta writes "Katsunobu Imai at Hiroshima University has figured out a way to construct a universal Turing machine using cellular automata in a Penrose tile universe. '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.' He was not aware of the recent development of the Penrose glider, so he developed this alternative approach."
Somehow Greg Egan's book "Permutation City" came to my mind when reading this. With his Autoverse representation on cellular automats.
No, you can't make a sphere with Penrose tiling. As has already been mentioned, a flat tile can't be used to cover a sphere. But more importantly, there isn't a generalization that will work either. The thing that makes Penrose tiling interesting is that it is aperiodic. No aperiodic pattern can work on a sphere since you necessarily are periodic when you make one complete revolution around any greater circle on a sphere.
There is a reason there are 50 different definitions of computable function - they are not hard to come by. As a professional mathematician/theoretical computer scientist I find it totally unsurprising to find one in the Penrose tiles. If it is useful for something, that's different. But you build almost any sufficiently rich mathematical structure and you can interpret a subset of them as Turing machines.