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

Question

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

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

状态 A(输入 X)---> 状态 B

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

这还是状态机吗？

Answer 1

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

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

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