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