theory - 是否有保证停止的有限状态机的术语？

Question

我之前讨论过状态机，有一个问题是它是否可能不会因某些输入而停止。它似乎是状态机的一个重要且经常被提及的属性，但我一生都无法弄清楚该属性的名称是什么。有这样的说法吗？它是“可停止的”、“不是无限循环的”还是其他什么？

Answer 1

总是停止的机器称为决策者。

决策者只需是一台在所有输入上都停止的机器。例如，所有 DFA 都是决策者，DPDA 也是如此。

Answer 2

我的猜测是“停止”，源自著名的“停止问题”，这与您的问题类似，即它是否会在给定输入时停止。一个重要的考虑因素是机器通常不被定义为“停止”，而是针对特定输入。一般情况被证明是无法解决的（图灵本人）。