它与内存一起工作时是状态机吗？

Question

在状态机中，据说它只保存有关当前状态的信息，并根据输入转移到下一个状态。

有附加条件的情况呢，例如：

状态 A（输入 X）---> 状态 B

状态 B
(输入 X) AND (SomeValue>=100) ---> 状态 C
(输入 X) AND (SomeValue < 100) ---> 状态 D

这还是状态机吗？

Answer 1

状态机可以没有内存（例如有限自动机）、访问受到某种方式限制的内存（例如具有堆栈访问的下推自动机）或访问本质上不受限制的内存（例如图灵机或随机存取机 (RAM)） ）。我认为将所有这些东西称为状态机是公平的，因为它们根据其内部状态改变行为。

如果自动机不写内存，而只是读内存，并且它没有能力“返回”并读取之前读过的内存，那么无论它读什么内存，都相当于没有记忆，只是简单地响应它接收到的正常输入。例如，无法写入且只能从左到右读取磁带的图灵机相当于有限自动机；不能将符号压入堆栈的下推自动机相当于有限自动机；ETC。

如果自动机可以写入内存内容并有能力最终读回这些内容 - 并且如果可以如此操作的内存量不是固定的 - 那么它仍然是一个状态机，但不再相当于有限自动机。请注意，我说内存量一定不能是固定的：如果内存量是固定的，那么任何使用它的机器就相当于一个有限自动机，对于所有内存的每种可能的配置都有重复的状态。即使你现在使用的计算机也不比有限自动机强大：事实上，你的计算机比一般的有限自动机强大得多，因为有无限多种常规语言不可能被任何物理上可实现的计算机所接受。