Can SAT instances be solved using cellular automata?

Question

I'm a high school student, and I have to write a 4000-word research paper on mathematics (as part of the IB Diploma Programme). Among my potential topics were cellular automata and the Boolean satisfiability problem, but then I thought that maybe there was a connection between the two. Variables in Boolean expressions can be True or False; cells in cellular automata can be "On" or "Off". Also, the state of some variables in Boolean expressions can depend on that of other variables (e.g. the output of a Boolean function), while the state of cells in cellular automata depend on that of its neighbors.

Would it be possible to use cellular automata to solve a satisfiablity instance? If so, how, and where can I find helpful/relevant information?

Thanks in advance!

Answer 1

If you could find an efficient way to solve SAT, you'd become very rich and famous. That's not likely to happen when you're still in high school. What you might be able to do, though, is get your cellular automaton to go through all possible values of the variables, and check the value of the Boolean expression for each one.

Answer 2

The simple answer is Yes. Can you do it in a simple way? probably not. Cook showed in 2004 that you can indeed compute anything that a turing-machine could on elemetry celular automata using Rule 110 and careful selection of start conditions. There is probably no simple rule or start conditions to do this though.

see: http://blog.barvinograd.com/2012/11/cyclic-tag-system-1-line-of-turing-complete-code/ for more details.