Turing machine gives order to chaotic Penrose universe: 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 didn't know about the Penrose glider at the time, so he was forced to take an alternative approach.
No comments:
Post a Comment