Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.