我知道可以将某些算法表示为 FSM，但 FSM 可以描述所有可能的算法吗？
最佳答案
没有。直观地说，如果算法仅使用有限数量的状态，则它只能表示为 FSM。例如，您无法使用 FSM 对任意长度的列表进行排序。
现在，向 FSM 添加无限数量的状态——就像一个无限的一维值数组……并在 FSM 和数组之间添加一点“胶水”状态——一个“当前位置”在那个数组中......你有一个图灵机。是的，它可以做到这一切。
关于algorithm - 每个算法都可以用有限状态机表示吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24122014/