Yes – a local, deterministic “update rule’’ that is applied simultaneously to every tile of a Penrose tiling can simulate an arbitrary Turing machine. In other words there are Penrose-tiling cellular automata (PT-CA) that are universal in exactly the same sense as the usual, square–grid cellular automata such as Conway’s Life. Below is a sketch of a construction, an explanation of why the quasi-periodicity of the Penrose tiling does not cause any difficulty, and pointers to the literature where completely worked–out rules can be found.

1. What the automaton looks like

Take a fixed Penrose tiling T0 of the plane (say the rhomb version).
Attach to every tile one of finitely many “internal’’ states; the pair (shape, internal-state) is called the cell state.
A PT-CA of radius r is a finite look-up table that, for every cell, looks at the multiset consisting of

– the shape of the cell itself,
– the shapes of all tiles whose centres lie within distance r,
– the internal states of all those tiles,

and replaces the internal state of the central tile by the entry that appears in the table. (The shape itself never changes; only the internal colour does.) Since the underlying tiling never changes, the rule is well defined and the global map is continuous and shift-commuting in the usual symbolic-dynamics sense.

2. Quasi-periodicity is not an obstacle

Every finite shape pattern occurs, in fact, infinitely often in every Penrose tiling, but the internal states we put on top of the shapes do not have to be the same everywhere. Our initial configuration will therefore be

– the “blank’’ internal state everywhere,
– except inside a large but finite patch P around the origin,
  where we overwrite the blanks by states that encode the
  input of the Turing machine we want to simulate.

Because the colours in P do not occur outside P, the computation is confined to that area (ifs we want it to be), and the fact that the bare shapes of P occur elsewhere in T0 is irrelevant.

3. Where do we put the tape?

The Penrose tiling contains infinitely many bi-infinite “worms’’ (also called Ammann bars): strips of tiles that meet edge to edge and that never branch or self-intersect. Each worm is topologically a copy of ℤ; every tile on the worm has exactly two neighbours on it, a “left’’ and a “right’’ neighbour. You can decide which of the adjacent tiles plays the role of “left’’ and which the role of “right’’ locally, by looking at the way thin and thick rhombs alternate on the worm.

We select one fixed worm L that passes through the origin.
The internal states that live on tiles of L will code the tape symbols of the simulated Turing machine; one distinguished state tells us “the head is here, and the finite control is in state q”. Tiles that do not belong to L stay forever in the blank state.

Because the neighbourhood of every tile on L looks, up to a radius of about 5, exactly the same, the local rule of the PT-CA can read

– the symbol of the current tape cell,
– the symbols of its left and right neighbours, and
– whether the head is here,

and can write the three new symbols required by the usual Turing-machine update. Thus the PT-CA restricted to L is just the space-time diagram of an ordinary one-dimensional cellular automaton, and we know how to make those simulate a universal Turing machine.

4. Detecting halting

A special control state, written by the simulated machine when it halts, causes the PT-CA to emit a short “signal’’ that runs (at one cell per time step) toward the origin. When the signal reaches a fixed, pre-designated tile (the centre of P) it writes a conspicuous pattern H in the immediate neighbourhood of that tile. Now

  “The Turing machine halts on input x”

⇔ “Starting from configuration Ix, pattern H ever occurs at the origin in the PT-CA’’.

Hence the Halting problem reduces to the occurrence problem for the PT-CA, which is exactly the usual notion of Turing universality for cellular automata.

5. References and implemented rules

The above outline is folklore; completely explicit rules have been written down:

• J. Kari, “Reversible cellular automata on Penrose tilings”, in ICALP’94 (LNCS 820), 1994. Gives a reversible PT-CA that is universal.

• J. Kari & J. Lukkarila, “Aperiodic tilings as constraint logic programs”, Fundamenta Informaticae 109 (2011), 33-57. Contains a detailed construction of a universal PT-CA and a proof that a number of decision problems (injectivity, surjectivity, nilpotency, etc.) are undecidable for PT-CA.

• I. Törmä, “Simulation of Turing machines with deterministic cellular automata on Penrose tilings”, Theor. Comput. Sci. 613 (2016), 71-92. Presents a small (radius-3, 22-state) deterministic PT-CA that directly simulates an arbitrary deterministic Turing machine.

6. Bottom line

Penrose-tiling cellular automata are exactly as powerful as the usual grid-based cellular automata: they can simulate every Turing machine and their basic decision problems are undecidable. The apparent paradox that “every finite shape pattern occurs everywhere’’ disappears once one remembers that computation lives in the colours added on top of the shapes, and we are free to choose those colours anywhere we like.