[Gehinnn]

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]

Completely 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/

[Gehinnn]

I'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.