[Solved]: Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines

Problem Detail: 

I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an infinite list of cells, which begins with the input string, the rest being blank. It has a transition function $\delta: Q \times Q \times Q \to Q$. The automaton computes by updating the value of the middle cell, $a$, using $\delta(x,a,y)$. The automaton accepts if any cell is in the accept state. From what I understand, this automaton is very similar to a 1-dimensional cellular automaton, with the addition of the accept state.

I'm trying to prove that a language is recognizable by a Turing machine if and only if it can be recognized by the automaton described.

I've been trying to do a proof by construction, but I'm really lost. I did some research on cellular automata, but the material I've been finding is way over my level. I know somehow I'm going to have to construct a TM from CA, and vica versa, but I'm not even sure how to get started. I would really appreciate any help.

Asked By : Kevin G

Answered By : Yuval Filmus

Here are some hints. The easy direction is simulating cellular automata with Turing machines. Turing machines can simulate C programs, and you can simulate cellular automata in C. (Replace C with your favorite programming language.)

Given a Turing machine, we want to construct a cellular automaton simulating it. We need to upgrade the alphabet by allowing, besides regular symbols $\sigma$, also symbols $\langle q,\sigma \rangle$ which signify that the head is currently at that point, the state is $q$, and the tape symbol is $\sigma$. The initial tape would contain $\langle q_0,\sigma_0 \rangle$ as the first symbol, where $q_0$ is the initial state and $\sigma_0$ is the first symbol on the input tape of the Turing machine.

It remains to show how to simulate the Turing machine by an appropriate choice of the propagation rules $\delta$. The basic idea is to maintain the invariant that the contents of the cells constitute of the tape of Turing machine, with the exception of the location of the head, which is of the form $\langle q,\sigma \rangle$. I'll let you work out the details.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16321