Re:Cellular Automata (1983) [pdf]
by Gehinnn on Wednesday April 21, 2021 @07:36PM
(#26896756)
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.
Re:Cellular Automata (1983) [pdf]
by jnakayama on Thursday April 22, 2021 @03:56AM
(#26900039)
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/
Re:Cellular Automata (1983) [pdf]
by Gehinnn on Thursday April 22, 2021 @05:33PM
(#26908463)
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.
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.