We know there is an elementary cellular automata (ECA) with 2 states (Rule 110) that is universal, i.e. Turing-complete. One-way cellular automata (OCA's) are a subcategory of ECA's where the next state only depends on the state of the current cell and one neighbor. I believe that one can make a universal OCA with 4 states pretty easily by simulating two cells of Rule 110 with each cell of the OCA. Does anyone know if it can be done with only three states? Thanks!
Hi, Chris! I'm not familiar with ZWA's. Can you point me at a paper? Thanks!
Thanks, I'll give that some thought! I think it's not quite the same paradigm as what I was originally wondering about but it might be interesting.
You might find this very interesting! I think it might be close to what you have been asking for. http://www.wolframscience.com/prizes/tm23/solved.html
You can find the proof here: http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf
That is very close! Not quite the same because it's a Turing Machine and not a CA. Also, I think it's not one-way --- but I'm going to have to take a close look at the proof. It might still be useful.
- Badges
- Science topic
- Similar topics
- Entomology
- Resistance