Dave Ackley is using cellular automata for new computational architectures.<p>Its really cool stuff and you'll no doubt love it if you're keen on that stuff. He's also got a youtube channel under his name that is really worth checking out.<p><a href="https://direct.mit.edu/isal/proceedings/isal2020/32/13/98482" rel="nofollow">https://direct.mit.edu/isal/proceedings/isal2020/32/13/98482</a>
Only a few pages in. Had to try:
<a href="https://gist.github.com/peheje/8076f619f6fbc1202954bc70720ef986" rel="nofollow">https://gist.github.com/peheje/8076f619f6fbc1202954bc70720ef...</a>
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.<p>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.
Hey, this article got me interested in 1-d cellular automata at the time. Before that it was Von Neumann’s self replicating cellular automata and then Conway’s Life in the 70’s
Funny enough I started researching biology and computation 1 month ago and so far it has been a wild ride into topics such as biocomputation, emergent computation, evolutionary biology, evolutionary computation and artificial life.
Some nice demonstrations of 2d cellular automata <a href="https://oeis.org/A139250/a139250.anim.html" rel="nofollow">https://oeis.org/A139250/a139250.anim.html</a>
"I wonder which will become self-aware first -- Wolfram Alpha, or Stephen Wolfram."<p><a href="https://news.ycombinator.com/item?id=9798333" rel="nofollow">https://news.ycombinator.com/item?id=9798333</a>