Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top