Gibt es einen Begriff für eine endliche Zustandsmaschine, die garantiert zum Stillstand kommt?

Question

Ich hatte zuvor eine Diskussion über eine Zustandsmaschine, und es gab eine Frage, ob es bei einigen Eingaben nicht anhalten könnte. Es scheint eine Eigenschaft von Staatsmaschinen zu sein, die wichtig und häufig erwähnt ist, aber ich kann nicht für das Leben von mir herausfinden, was der Name dieser Eigenschaft ist. Gibt es einen solchen Begriff? Ist es "haltbar", "nicht-unendlich-loopy" oder etwas anderes?

Answer 1

Eine Maschine, die immer anhält, wird decider genannt.

Ein Entscheider muss nur eine Maschine sein, die an allen Eingängen anhält. Zum Beispiel sind alle DFAs Entscheider, ebenso wie DPDAs.

Answer 2

Meine Vermutung wäre "Halt", abgeleitet von der berühmten "halting problem", die Ihrer Frage ähnlich ist, nämlich, ob es bei einer gegebenen Eingabe anhält. Eine wichtige Überlegung ist, dass eine Maschine nicht generell als "Halt" definiert ist, sondern für eine bestimmte Eingabe. Der allgemeine Fall erweist sich als unlösbar (von Turing selbst).