代码之家 › 专栏 › 技术社区 › Brandon Yarbrough

有限状态机是否有一个保证停机的术语?

turing-machines theory

10

Brandon Yarbrough · 技术社区 · 14 年前

我之前正在讨论一个状态机,有一个问题是它是否会在某些输入上停止。它看起来像是一个状态机的属性,这很重要而且经常被提到,但是我一辈子都搞不清这个属性的名称是什么。有这样一个术语吗?它是“可停止的”、“不是无限循环的”还是其他什么?

2 回复 | 直到 14 年前

1

9

Welbog 14 年前

总是停机的机器称为 decider .

决策者只需要一台停止所有输入的机器。例如,所有DFA都是决策者,DPDAS也是。

2

0

nearlymonolith 14 年前

我的猜测是“停止”,源自著名的 "halting problem" 这与您的问题类似,即它是否会在给定的输入上停止。一个重要的考虑是,机器一般不被定义为“停止”,而是特定的输入。The general case is proven to be unsolvable (by Turing himself).