Estaba discutiendo anteriormente sobre una máquina de estado, y había una pregunta sobre si podría detenerse en alguna entrada. Parece una propiedad de las máquinas de estado que es importante y se menciona con frecuencia, pero no puedo imaginar cuál es el nombre de esa propiedad. ¿Hay tal término? ¿Es "escalable", "no infinitamente repetitivo", o algo más?¿Hay un término para una máquina de estado finito que se garantiza que se detenga?
Una máquina que siempre se detiene se llama decider.
Un decisor solo necesita ser una máquina que detenga todas las entradas. Por ejemplo, todos los DFA son determinantes, al igual que los DPDA.
Ah, sí, eso fue exactamente! ¡Muchas gracias! –
¡Genial! No lo sabía Dejaré mi respuesta anterior a continuación solo en caso de que las personas estén interesadas en el problema de detención. – nearlymonolith
Mi conjetura sería "detener", derivada de la famosa "halting problem", que es similar a su pregunta, es decir, si se detendrá en una entrada determinada. Una consideración importante es que una máquina no se define como "detención" en general, sino más bien para una entrada específica. El caso general ha demostrado ser insoluble (por el propio Turing).
es mi favorito – nearlymonolith
Tuve que darle +1 por "no infinito-loopy" –