Dave Ackley is using cellular automata for new computational architectures.
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.
Very interesting! Added to my list for algorithms to use in generative art seeds. Was already looking for computer architecture geometries to visualise and play around with.
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.
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/
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.
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
It does and with acknowledgement that Conway's life was then the best known example of 2D cellular automata. However, Conway's life CA was not the focus of the article hence limited references to it. There was an increasing of interest at the time of the article on self similarity, emergence, self organization and mapping of CAs with dynamical systems theory and different classes of CAs (focus of article) beyond the game of life. A number of researchers at the time were interested in using CAs as a means of simulating certain dynamical systems e.g. fluids and weather. However generally the early work of CA pioneers including Stanislaw Ulam, Kondrad Zuse, Art Burks et all was not as widely known as it is now and certainly John Conway's life along with the works of Edward Frenkin, Norman Magulis et al and articles such as these by Stephen Wolfram helped generated renewed interest in the field. Without articles like this one I am not sure we would have seen sufficient interest to publish discoveries such as Christopher Langton's wonderful Loops and Ant only a few years later. If you are interested in CAs its a good article and worth reading.
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.
I saw that book it is pretty hardcore with over 1000 pages I'm just trying to grasp the basics of Cellular Automata. I'm thinking about reading this book:
Speaking of self-awareness, we need some as the community—specifically, enough self-awareness to avoid endless reflexive repetition in response to the same provocative stimulus over how many—has it been 20 now?—years. The internet obsession with Wolfram is just a mirror image of the Wolfram-obsession it's complaining about.
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.
https://direct.mit.edu/isal/proceedings/isal2020/32/13/98482