3 ms·
2D cellular automata can also be used to recognize formal languages: Every character of a word forms an (initial) state. Finitely many additional non-character
by Gehinnn 5y ago
2D cellular automata can also be used to recognize formal languages: Every character of a word forms an (initial) state. Finitely many additional non-character states are allowed.
A word w is accepted iff the first cell indicates "yes" after |w|-1 iterations.
It is an open problem if there is a language that can be recognized after 2|w|-1 iterations, but not after |w|-1 iterations. Afaik, it is even unknown if there is any language in NP that cannot be recognized after |w|-1 steps (obviously P!=NP would imply this).
I'm surprised how far math has come, but how little we know about computational complexity.
- jnakayama 5y agoCompletely agree! I had the same thought when looking into elementary cellular automata, they seem so inoccuous, but there are still so many open questions. There is even a prize for solving three particular ones: https://www.rule30prize.org/ https://www.rule30prize.org/
- Gehinnn 5y agoI'm quite happy that I have absolutely no idea what kind of argument could possibly be employed to solve any of those problems. No danger of wasting an endless amount of time here.