Avevo una discussione precedente su una macchina a stati e c'era una domanda sul fatto che non potesse fermarsi su qualche input. Sembra una proprietà delle macchine di stato che è importante e spesso citata, ma non posso per la vita di me capire quale sia il nome di quella proprietà. Esiste un termine del genere? È "haltable", "not-infinely-loopy" o qualcos'altro?Esiste un termine per indicare una macchina a stati finiti che viene arrestata?
Una macchina che si arresta sempre viene chiamata decider.
Un decisore deve essere solo una macchina che si arresta su tutti gli ingressi. Ad esempio, tutti i DFA sono decisori, come lo sono i DPDA.
Ah, sì, era esattamente così! Grazie mille! –
Fantastico! Non lo sapevo. Lascerò la mia risposta precedente qui di seguito, nel caso in cui le persone fossero interessate al problema dell'arresto. – nearlymonolith
La mia ipotesi sarebbe "fermarsi", derivata dal famoso "halting problem", che è simile alla tua domanda, vale a dire se si fermerà su un dato input. Una considerazione importante è che una macchina non è definita come "arresto" in generale, ma piuttosto per un input specifico. Il caso generale è dimostrato irrisolvibile (dallo stesso Turing).
è il mio preferito – nearlymonolith
Ho dovuto dargli +1 per "non infinitamente-loopy" –