Is the halting problem decidable for 3 symbol one dimensional cellular automata?

Question

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata.

Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. More formally $f:A^*\times \mathbb{N} \to A^*$, where $A$ is the alphabet.

Definition. A cellular automaton has halted in configuration $f(w,i)$, if $\forall k\in \mathbb{N}$ we have that $f(w,i)=f(w,i+k)$.

The halting problem for a given cellular automaton is as follows:

Input: a finite word $w$
Question: will the automaton halt in some state $s$?

Elementary cellular automata (with 2 symbols) are defined here. I am focused on the same sort of celullar automata, except that I'm interested in the case of CA's with 3 symbols instead of just 2 symbols.

From now on, I will denote my rules in the form of $***\to*$, meaning that 3 neighboring symbols produce another one beneath them.

The halting problem is decidable for elementary, 2-symbol cellular automata

I will use $0$ to denote a white cell and $1$ to denote a black one.

If we have rules $000 \to 1$, $001 \to 1$, $100 \to 1$ we know the automaton won't halt. Because with the first rule, since our grid is infinite, we will always have 3 white cells that will generate a black cell. With the second and 3rd rules the word will be expanding to the sides and the automaton will never halt.

In the rest of the cases we can let it evolve for $2^n$ steps and see if it halts. If it does halt, then ok, it halts, if it doesn't then it is repeating some combinations and is stuck in a loop, so we can also conclude that it won't halt.

What I have figured out for the 3 symbol case

It is obvious that it won't halt if we have rules $000 \to 1$ or $000 \to 2$. But the side rules of the form $00x \to y$ and $x00 \to y$ are harder to analyze, because what if we have rules $002 \to 1$ and $001 \to 0$?

Here's what I came up with:

let's consider all combinations of such rules:

1. $001 \to 0$ and $002 \to 0$
2. $001 \to 0$ and $002 \to 1$
3. $001 \to 0$ and $002 \to 2$
4. $001 \to 1$ and $002 \to 0$
5. $001 \to 1$ and $002 \to 1$
6. $001 \to 1$ and $002 \to 2$
7. $001 \to 2$ and $002 \to 0$
8. $001 \to 2$ and $002 \to 1$
9. $001 \to 2$ and $002 \to 2$

I didn't write the cases for the rules of the form $x00 \to y$, because those are symmetrical.

So, in the first case it's obvious that the input word won't be expanding to the sides, because those side symbol rules produce zeros.

In cases 5, 6, 8, 9 it's obvious that the automaton will never halt, because the input word will be expanding.

Cases 2,3,4,7 are more interesting. First, let's note, that case 2 is similar to case 7 and case 3 is similar to case 4. So, let's just consider cases 2 and 3 for conciseness.

I'm gonna consider case 3 first, because it's easier.

We have $001 \to 0$ and $002 \to 2$. It is obvious that if the first or last symbol of our input word is $2$, then we can conclude that the automaton won't halt. But if they are '1', then we have to look at more stuff, in particular, let's look at rules that can turn the last or first symbols into $2$, because if we have those, then after they do produce that $2$, we can conclude that the automaton won't halt. (the word will be expanding to the side(s)).

Here are all combinations that we need to consider:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
........... etc

An explanation of what happens if we have the first triple from the above table

We have a word $w$, written on the grid. The first and last symbols are $1$. Let's say we have rules $010 \to 0$, $011 \to 0$, $012 \to 0$ (the first triple) from above. Then we know that with each next step our input word will be getting smaller by 2 symbols, because these rules erase the first and last symbols, but if at some point we get a $2$, then the rule $002 \to 2$ will make the word grow to one side or the other (or both) and the automaton will never halt. So, all in all, in this case we can let the automaton do $|w|/2$ steps, and if the word becomes empty, then the automaton halts, if not, then it doesn't.

Generalized case 3

I generalized it and noticed that we can simply let the automaton do $3^n$ steps and if at any one of those steps we have a $2$ as first or last symbol, then the automaton won't halt. If that doesn't happen and the automaton still didn't halt, then it's repeating some configuration, so it's stuck in a loop and won't halt. If it halts, then it halts.

Where I get stuck

Now let's consider case 2.

We have rules $001 \to 0$ and $002 \to 1$.

And here is where I got stuck and don't know what to do.

I also wrote out a table of rules that start with $1$. I wrote those out, because they seemed to be the first thing I should analyze, because even if we have the input word with first or last (or both) symbol as $2$, at the next step those $2's$ will turn into a $1$. And we will have to deal with rules of the form $01x \to y$.

Here's the table:

010 011 012
 0   0   0
 0   0   1
 0   0   2
 0   1   0
 0   1   1
 0   1   2
 0   2   0
 0   2   1
 0   2   2
 1   0   0
 1   0   1
 1   0   2
 1   1   0
 1   1   1
 1   1   2
 1   2   0
 1   2   1
 1   2   2
 2   0   0
 2   0   1
 2   0   2
 2   1   0
 2   1   1
 2   1   2
 2   2   0
 2   2   1
 2   2   2

It is also obvious, that if among our 27 rules, we have a triple from this table in which no rule derives a $2$, then we have nothing to worry about and can simply let the automaton evolve for $3^n$ steps, because it won't really expand, since the side rules will not produce a $2$.

But looking at the triples that do have a $2$, it's actually very hard to analyze, and whether the word will expand or not also seems to depend on the input word.

Can you guys tell me how to solve this? I can't seem to wrap my head around this.

Or, if this 3 symbol cellular automaton looks like something for which the halting problem has been proven to be undecidable, how can I reduce that something to 3 symbol cellular automata?

Answer 1

I have found this article: http://www.dna.caltech.edu/~woods/download/NearyWoodsMCU07.pdf and will show how to prove that the halting problem is undecidable for 15-symbol cellular automata.

Let's look at typical instructions of a Turing machine, we have:

1) $q,x\to p,y,L$

2) $q,x\to p,y,R$

The first one says that if the automaton sees symbol $x$ in state $q$, then we replace $x$ by $y$, switch to state $p$ and move left, the second one says the same thing, but it moves right.

Let's assume that the TM alphabet is $A$, the set of rules is $R$ and the set of states is $Q$. Now, let's create a new alphabet for our cellular automaton, it will be the following: $\Sigma=A\bigcup Q\bigcup \{q'|\forall q \exists r\in R, r=p,x\to q,y,L\}$. In other words, in the new alphabet we will include the alphabet of the TM, the state alphabet of the TM and for every state $q$, such that there's a rule $p,x\to q,y,L$ we will include $q'$.

The automaton will model the TM, in the following way: at each step of CA's operation we will have one symbol from the TM's state alphabet on CA's tape, and that symbol will point to the symbol that TM's head would be pointing to, in the following way: a symbol that is to the right of the state symbol is the symbol that the TM's head points to. As an example consider the string $s=...xabqzyk...$, let's say, that $q\in Q$, then the TM is in state $q$, and the head points at symbol $z$.

Let's see how we can simulate the operations of the TM. Let's consider the second one first:

2) $q,z\to p,y,R$

So, basically, if we have a string $s=...xabqzyk...$, it should be converted into $...xabypyk...$. Which can be very easily achieved by adding the following rules to the automaton:

$qz\alpha\to p, \forall \alpha \in \Sigma$

$\alpha qz\to y, \forall \alpha \in \Sigma$

The first case is a little more complicated, we have:

1) $q,z\to p,y,L$

So the string $s=...xabqzyk...$ should be converted into $...xapbyyk...$, but there's not a way to do $abq\to p$ because we perform a TM operation by looking at state and symbol, but $abq$ doesn't tell us about the symbol, only state, so we will perform this left move in 2 steps:

first step:

$qz\alpha\to y, \forall \alpha \in \Sigma$

$\alpha qz\to p', \forall \alpha \in \Sigma$

second step:

$\alpha \beta p'\to p, \forall \alpha, \beta \in \Sigma$

$\alpha p' \beta\to \beta, \forall \alpha, \beta \in \Sigma$

As for all the other CA rules, for which there's isn't a rule in TM, we will write the following:

$\alpha \beta \gamma \to \beta, \forall \alpha,\beta,\gamma \in \Sigma$

Now that I explained the way to model the work of TM on a CA, let's see why we need 15 symbols. In the paper, the link to which I gave above we have a universal TM $U_{6,4}$ with 6 states and 4 symbols:

So, we need all the alphabet symbols, which is 4, plus all the state symbols which is 6 and all the state symbols $q'$ such that there's a rule $p,x\to q,y,L$, which are $u_1, u_3, u_4, u_5, u_6$, so, we need 15 symbols in total.

So, now there's a gap between 2 and 15 symbols (exclusive), that we don't know about.