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. 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?
