Good evening (Or whatever time of the day it is where you're at) to all my lovely fellow redditors, I have a question, but rather than a question I need some guidance.
Some context: I am currently taking a class on Dynamical Systems at my University. I've always been interested on cellular automatas but never had a chance to actually interact with the subject (What you guys do is incredible).
Today our teacher told us it would be a good idea to end the semester with a project related to the subject, so I decided it would be a great idea to try and mix both Complexity Theory and Cellular Automatas but I don't have many ideas, so I wanted to ask for some guidance on the matter.
Cellular automatas and complexity (Question)
-
cristomike2
- Posts: 1
- Joined: May 8th, 2020, 10:57 am
Re: Cellular automatas and complexity (Question)
The main connection I can think of between cellular automata and complexity are the proofs that various cellular automata are Turing complete.
There's also the complexity of various different search problems. For a example, given a pattern in a cellular automaton, is it NP-hard to determine whether or not it has a predecessor?
There's also the complexity of various different search problems. For a example, given a pattern in a cellular automaton, is it NP-hard to determine whether or not it has a predecessor?