15
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Nov 11 '10 at 15:53
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Shor Nov 11 '10 at 16:22
  • $\begingroup$ 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? $\endgroup$ – Aaron Sterling Nov 11 '10 at 17:24
  • 2
    $\begingroup$ 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. $\endgroup$ – Colin McQuillan Nov 11 '10 at 21:01
  • 2
    $\begingroup$ @Colin, Actually, I was wrong about this. Forget the question. Maybe I should delete it. $\endgroup$ – Peter Shor Nov 11 '10 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.