Lou*_*Lou 3 algorithm computer-science state-machine
我知道可以将一些算法表示为FSM,但FSM可以描述每种可能的算法吗？
不可以.直观地说,如果算法仅使用有限数量的状态,则它只能表示为FSM.例如,您无法使用FSM对任意长度列表进行排序.
现在,向FSM添加无限量的状态 - 比如无限的一维值数组......并在FSM和数组之间添加一点"胶水"状态 - "当前位置"的概念在那个阵列......你有一台图灵机.哪,是的,可以做到这一切.
没有.
有一个有限状态机可以描述每种常规语言.对于不规则语言,有限状态机是不够的.
所有程序的集合称为"递归可枚举"语言,并且可以由图灵机接受.
这通常被称为乔姆斯基Hirerchy:
Regular Languages <= Context Free Languages <= Context Sensitive Languages <= Recursively enumerable Languages
哪些被接受:
重要的是要注意,可以接受描述所有"更高层语言"的机器也可以描述所有较低层(例如,您可以创建图灵机以接受每种常规语言)