<p>This question was based on an incorrect premise ... see Colin's comment below. Forget it.</p>

<p>This was inspired by the discussion on <a href="https://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45382">this Math Overflow question</a>. First, I need to define our terms.</p>

<p>In a Penrose tiling, there are generally several different legal patterns of tiles which will cover a given region. A Penrose tile cellular automaton should be some rule that deterministically takes a Penrose tiling $T$ to a Penrose tiling $T'$, where each tile in $T'$ is deterministically given by looking at the tiles in a radius $r$ around the corresponding spot in $T$. You should be able to implement these by having a set of rules of the form: when a region of shape $S$ is covered by a pattern $X$ of tiles, replace it with a pattern $Y$ of tiles. In order to do this deterministically, you either have to make sure no two of your replaceable regions can overlap or have some priority ranking on these replacement rules. But certainly you can ensure this, and define lots of different Penrose tiling cellular automata.</p>

<p>What does it mean for a Penrose tiling celluar automaton to be Turing-complete. Here's what I think it should mean (although I won't insist on it in the answers): the halting problem should be reducible to the behavior of such an automaton. Let's take some canonical Penrose tiling $T_0$ that provides constraints on our starting position. We  start with an input $G$ to a universal Turing machine, and we'd like to decide whether the machine halts on input $G$. I would like some computable map from $G$ to a starting Penrose tiling $S$ such that $S$ differs from $T_0$ on only a finite set of tiles. We then run the Penrose tiling cellular automaton, starting with $S$, and wait for some finite canonical configuration $C$ at position $0$ in the Penrose tiling. I want configuration $C$ to appear at position $0$ if and only if the universal Turing machine halts on input $G$.</p>

<p>The strange thing about Penrose tiling cellular automata is that every finite legal configuration of tiles appears infinitely often in every Penrose tiling of the plane. Thus, our universal Penrose tiling is not only computing the behavior of our universal Turing machine on input $G$, it's also simultaneously carrying out the first steps of every other possible computation. This makes me doubt whether Penrose tiling cellular automata could be Turing complete. On the other hand, if they're not Turing complete, what is the class of computations that Penrose tiling cellular automata can perform?</p>

CC BY-SA 4.0
2024-10-09T09:03:52.213Z
Yes, it's 14 years later, but I can't help noticing that something is wrong on the internet (like the [xkcd cartoon](https://images.app.goo.gl/Y2r21GjjunGpabYb9)). It is not correct that every finite pattern occurs in a Penrose tiling.
Matt
CC BY-SA 4.0
2024-10-09T09:04:36.473Z
If every finite pattern would occur, you would not be able to "get stuck" when attempting to tile the plane (because your finite pattern, whatever it is so far, would be guaranteed to be part of a valid tiling of the plane).  But in fact, you do need to know what you are doing in order to not get stuck, regardless of which Penrose tile set you are talking about.  Only very occasionally do you really have a choice of what tile to place (in the sense that either tile would be ok for creating a full tiling of the plane), approximately once per inflation scale level.
Matt
CC BY-SA 4.0
2024-10-09T09:42:06.550Z
@Matt: What I should have said is that every finite pattern that appears once in an infinite Penrose tiling appears infinitely often in every Penrose tiling.
Peter Shor 
CC BY-SA 4.0
2024-10-09T10:17:51.317Z
Yes, that is true for tilings formed via the deflation process. But an arbitrary planar tiling might have a "rift" along a line in the plane, along which the higher level tiles do not match up (like a tiling of the plane by squares in which the upper half plane is shifted right by a fraction of a unit). This is certainly possible with Robinson tiles and Ammann tiles, and I would expect it also for the various Penrose tiles although I haven't checked. If rifts can occur, local patches along the rift will appear infinitely often in the same tiling but needn't appear in another tiling.
Matt
CC BY-SA 2.5
2010-11-11T15:53:02.347Z
I am confused by your definition, sorry.  Is a Penrose CA just like a normal (2D) CA, except that the replacement rules are connected templates of finite size, instead of a local transition function that is applied cell by cell?  So there's an initial configuration at time step 0 that specifies the input, and the connected templates specify the program? One way small models of computation specify "halting" is to repeat a special state infinitely often. So maybe if the simulated TM halts the Penrose CA keeps recreating a certain pattern, and if the TM runs forever, anything goes.
Aaron Sterling
CC BY-SA 2.5
2010-11-11T16:22:12.827Z
The replacement rules are indeed connected templates of finite size. The problem with your periodic "halting" state is that it can't happen. You always can find any specific finite pattern in a Penrose tiling, so if any Penrose tiling CA has a starting state that is eventually periodic, then any starting state for that Penrose tiling CA is periodic with that period.
Peter Shor 
CC BY-SA 2.5
2010-11-11T17:24:46.510Z
Okay, second round.  There are Generalized Cellular Automata, where each cell $x$ transitions based on a "stencil" $\delta_x$, which is a neighborhood of tiles around $x$, and the size and shape of these neighborhoods may vary from cell $x$ to cell $y$. Is a Penrose CA a generalization of GCA's, where now each $x$ has a stencil set $S$ (perhaps common to all cells) and some $\delta \subseteq S$ can be applied to $x$ and its surrounding cells? This then leads to multiple possible tilings of the plane for a single start state. Does every ("nice"?) start state converge to a stable tiling?
Aaron Sterling
CC BY-SA 2.5
2010-11-11T17:53:49.433Z
typo: I meant "$\delta \in S$"
Aaron Sterling
CC BY-SA 2.5
2010-11-11T18:26:44.203Z
I hope it's clearer now. I want the rules to be deterministic and local, but exactly how they're formulated is less imporant.
Peter Shor 
CC BY-SA 2.5
2010-11-11T19:49:36.883Z
I don't think the existence of every finite pattern is any evidence against Turing completeness - in the game of life it seems plausible that there is a (finite) initial state that runs every turing machine G and puts a "halt" marker at some position f(G) if and only if G halts.
Colin McQuillan
CC BY-SA 2.5
2010-11-11T19:58:59.993Z
If someone reduced the Turing Machine Immortality Problem to a Penrose CA, would that be progress?  (TMIP = given a TM with an input tape with infinitely many nonblank symbols on it, does it halt?)  That problem is undecidable for TMs.
Aaron Sterling
CC BY-SA 2.5
2010-11-11T21:01:26.743Z
Can you give an example of a region which may be legally covered by different patterns of tiles? I'm not familiar with the subject, but there is a unique way to break up a triangle into smaller triangles in "up-down" generation - see for example Prop 6.1 of Quasicrystals and geometry.
Colin McQuillan
CC BY-SA 2.5
2010-11-11T22:17:29.310Z
@Colin, Actually, I was wrong about this. Forget the question. Maybe I should delete it.
Peter Shor 
CC BY-SA 2.5
2010-11-11T22:42:58.933Z
@Peter: This question intrigued me because it seems related to one of the main open problems in tile self-assembly, which is "the power of multiple nucleation." If the Penrose tiling rule were somehow limited to radiate out one tile at a stage from the origin, instead of everywhere being tileable at once, I think the model would be very close to self-assembly models. The open questions there are complexity-related, not computability, e.g.: is there a finite shape such a restricted Penrose tiling could achieve that a GCA could not achieve with only polynomial complexity increase?
Aaron Sterling
<computability><machine-models><cellular-automata>
Can a Penrose tile cellular automaton be Turing-complete?
Peter Shor 
# Can a Penrose tile cellular automaton be Turing-complete?

(Asked by: username_0 on 2010-11-11)

This question was based on an incorrect premise ... see Colin's comment below. Forget it.

This was inspired by the discussion on [this Math Overflow question](https://mathoverflow.net/questions/45378/undecidability-in-conways-game-of-life/45382). First, I need to define our terms.

In a Penrose tiling, there are generally several different legal patterns of tiles which will cover a given region. A Penrose tile cellular automaton should be some rule that deterministically takes a Penrose tiling $T$ to a Penrose tiling $T'$, where each tile in $T'$ is deterministically given by looking at the tiles in a radius $r$ around the corresponding spot in $T$. You should be able to implement these by having a set of rules of the form: when a region of shape $S$ is covered by a pattern $X$ of tiles, replace it with a pattern $Y$ of tiles. In order to do this deterministically, you either have to make sure no two of your replaceable regions can overlap or have some priority ranking on these replacement rules. But certainly you can ensure this, and define lots of different Penrose tiling cellular automata.

What does it mean for a Penrose tiling celluar automaton to be Turing-complete. Here's what I think it should mean (although I won't insist on it in the answers): the halting problem should be reducible to the behavior of such an automaton. Let's take some canonical Penrose tiling $T\_0$ that provides constraints on our starting position. We start with an input $G$ to a universal Turing machine, and we'd like to decide whether the machine halts on input $G$. I would like some computable map from $G$ to a starting Penrose tiling $S$ such that $S$ differs from $T\_0$ on only a finite set of tiles. We then run the Penrose tiling cellular automaton, starting with $S$, and wait for some finite canonical configuration $C$ at position $0$ in the Penrose tiling. I want configuration $C$ to appear at position $0$ if and only if the universal Turing machine halts on input $G$.

The strange thing about Penrose tiling cellular automata is that every finite legal configuration of tiles appears infinitely often in every Penrose tiling of the plane. Thus, our universal Penrose tiling is not only computing the behavior of our universal Turing machine on input $G$, it's also simultaneously carrying out the first steps of every other possible computation. This makes me doubt whether Penrose tiling cellular automata could be Turing complete. On the other hand, if they're not Turing complete, what is the class of computations that Penrose tiling cellular automata can perform?

**Tags:** computability, machine-models, cellular-automata

> **Comments:**
> **username_2**: I am confused by your definition, sorry.  Is a Penrose CA just like a normal (2D) CA, except that the replacement rules are connected templates of finite size, instead of a local transition function that is applied cell by cell?  So there's an initial configuration at time step 0 that specifies the input, and the connected templates specify the program? One way small models of computation specify "halting" is to repeat a special state infinitely often. So maybe if the simulated TM halts the Penrose CA keeps recreating a certain pattern, and if the TM runs forever, anything goes.  
> **username_0**: The replacement rules are indeed connected templates of finite size. The problem with your periodic "halting" state is that it can't happen. You always can find any specific finite pattern in a Penrose tiling, so if any Penrose tiling CA has a starting state that is eventually periodic, then any starting state for that Penrose tiling CA is periodic with that period.  
> **username_2**: Okay, second round.  There are Generalized Cellular Automata, where each cell $x$ transitions based on a "stencil" $\delta_x$, which is a neighborhood of tiles around $x$, and the size and shape of these neighborhoods may vary from cell $x$ to cell $y$. Is a Penrose CA a generalization of GCA's, where now each $x$ has a stencil set $S$ (perhaps common to all cells) and some $\delta \subseteq S$ can be applied to $x$ and its surrounding cells? This then leads to multiple possible tilings of the plane for a single start state. Does every ("nice"?) start state converge to a stable tiling?  
> **username_2**: typo: I meant "$\delta \in S$"  
> **username_0**: I hope it's clearer now. I want the rules to be deterministic and local, but exactly how they're formulated is less imporant.  
> **username_3**: I don't think the existence of every finite pattern is any evidence against Turing completeness - in the game of life it seems plausible that there is a (finite) initial state that runs every turing machine G and puts a "halt" marker at some position f(G) if and only if G halts.  
> **username_2**: If someone reduced the Turing Machine Immortality Problem to a Penrose CA, would that be progress?  (TMIP = given a TM with an input tape with infinitely many nonblank symbols on it, does it halt?)  That problem is undecidable for TMs.  
> **username_3**: Can you give an example of a region which may be legally covered by different patterns of tiles? I'm not familiar with the subject, but there is a unique way to break up a triangle into smaller triangles in "up-down" generation - see for example Prop 6.1 of Quasicrystals and geometry.  
> **username_0**: @Colin, Actually, I was wrong about this. Forget the question. Maybe I should delete it.  
> **username_2**: @Peter: This question intrigued me because it seems related to one of the main open problems in tile self-assembly, which is "the power of multiple nucleation." If the Penrose tiling rule were somehow limited to radiate out one tile at a stage from the origin, instead of everywhere being tileable at once, I think the model would be very close to self-assembly models. The open questions there are complexity-related, not computability, e.g.: is there a finite shape such a restricted Penrose tiling could achieve that a GCA could not achieve with only polynomial complexity increase?  
> **username_1**: Yes, it's 14 years later, but I can't help noticing that something is wrong on the internet (like the [xkcd cartoon](https://images.app.goo.gl/Y2r21GjjunGpabYb9)). It is not correct that every finite pattern occurs in a Penrose tiling.  
> **username_1**: If every finite pattern would occur, you would not be able to "get stuck" when attempting to tile the plane (because your finite pattern, whatever it is so far, would be guaranteed to be part of a valid tiling of the plane).  But in fact, you do need to know what you are doing in order to not get stuck, regardless of which Penrose tile set you are talking about.  Only very occasionally do you really have a choice of what tile to place (in the sense that either tile would be ok for creating a full tiling of the plane), approximately once per inflation scale level.  
> **username_0**: @username_1: What I should have said is that every finite pattern that appears once in an infinite Penrose tiling appears infinitely often in every Penrose tiling.  
> **username_1**: Yes, that is true for tilings formed via the deflation process. But an arbitrary planar tiling might have a "rift" along a line in the plane, along which the higher level tiles do not match up (like a tiling of the plane by squares in which the upper half plane is shifted right by a fraction of a unit). This is certainly possible with Robinson tiles and Ammann tiles, and I would expect it also for the various Penrose tiles although I haven't checked. If rifts can occur, local patches along the rift will appear infinitely often in the same tiling but needn't appear in another tiling.  

---

## 0 answers

