测试图（有向）中节点的可达性，可以使用cellualr自动机完成吗？实际上，需要考虑的是，使用ca实现一个算法，该算法使用ca检查节点从指定顶点的可达性。这甚至是可能的吗？CA有能力这么做吗？
知道吗？
最佳答案
第一个问题的答案是肯定的，因为Conway's Game of Life就是turing complete这大致意味着细胞自动机（尤其是生命游戏）可以计算出你的电脑可以实现的任何功能。
我不熟悉这个证明的细节，但我认为它是基于某种方式将图灵机器转化为生命游戏的一个实例。如果你能构造一个图灵机器来解决这个问题，你就可以用这个技术把它转换成一个细胞自动机。
我建议使用深度优先搜索作为底层算法，因为它比dijkstra的算法简单得多，而且元胞自动机可能不是解决问题的有效方法。
关于algorithm - 使用元胞自动机对图形中的顶点进行可达性分析，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7122095/