Y a-t-il un terme pour une machine à états finis qui est garantie de s'arrêter ?

Question

J'avais une discussion plus tôt sur une machine d'état, et il y avait une question concernant le fait qu'elle pourrait ne pas s'arrêter sur certaines entrées. Il semble que ce soit une propriété des machines d'état qui est importante et fréquemment mentionnée, mais je n'arrive pas à comprendre le nom de cette propriété pourtant. Existe-t-il un terme spécifique? Est-ce "arrêtable", "non-infiniment-bouclable", ou quelque chose d'autre?

Answer 1

Une machine qui s’arrête toujours est appelée un décideur.

Un décideur doit simplement être une machine qui s'arrête sur toutes les entrées. Par exemple, tous les DFA sont des décideurs, tout comme les DPDAs.

Answer 2

Je devine que ce serait "halting", dérivé du célèbre "problème de l'arrêt", qui est similaire à votre question, à savoir s'il va s'arrêter sur une entrée donnée. Une considération importante est qu'une machine n'est pas définie comme "s'arrêtant" en général, mais plutôt pour une entrée spécifique. Le cas général est prouvé être insoluble (par Turing lui-même).