Reachability analysis of a vertex in a graph, using Cellular Automata

Testing reachability of a node in a graph (directed), can be done using cellualr Automata? Actually what's in mind, is to implement an algorithm that checks reachability of a开发者_开发百科 nod from a specified vertex, using CA. Is it even possible? Is CA capable of doing that?

Any idea?

---

The answer to your first question is yes, since Conway's Game of Life is turing complete. That roughly means that cellular automata (particularly the Game of Life) can compute any function your PC can.

I am not familiar with the details of the proof but I would assume that it is based on some way of transforming a Turing machine into an instance of the Game of Life. If you can construct a Turing machine to solve the problem you can probably transform it into a cellular automaton using that technique.

I would recommend using a depth first search as the underlying algorithm since it is much simpler than Dijkstra's Algorithm and a cellular automaton is probably not an efficient way of solving the problem anyway.

---

I know of no general cellular automaton for reachability in arbitrary graphs, but in the mid 1990s there was some research into maze-solving in rectangular grid mazes using cellular automata. One accessible description of the technique can be found here. If you have ACM access, you can read the original paper here. It should not be particularly difficult to adapt the algorithm for pathfinding to reachability, assuming that your graph is a 2D grid.

I will keep looking and see if I can find a more general algorithm.

---

I cannot say for sure that CA will do what you want. But Dijkstra can be used to determine the shortest path (also if a path exists) from one node to another. The Complexity of Dijkstra is high though.