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?
risposta
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
- 1. Una macchina a stati finiti dovrebbe avere una macchina a stati finiti "annidati"?
- 2. GUI come macchina a stati finiti
- 3. Convalida una macchina a stati finiti (utilizzando AASM) su Rails
- 4. Akka design per autenticazione (macchina a stati finiti)
- 5. Macchina a stati finiti generali (trasduttore) in Scala
- 6. Che cos'è una macchina a stati finiti e a cosa serve?
- 7. Segnalazione di macchina a stati finiti e inter-FSM
- 8. macchina a stati finiti guidata dagli eventi + thread: come?
- 9. Compilatore a stati finiti
- 10. Una catena di Markov è uguale a una macchina a stati finiti?
- 11. Come testare una macchina a stati?
- 12. Il C# include macchine a stati finiti?
- 13. Attuare un codice per simulare un automa a stati finiti non deterministico in C++
- 14. Altro approccio .net per macchina a stati dinamici
- 15. Esiste un termine per una monade che è anche una comonad?
- 16. Esiste una direttiva preprocessore GCC per verificare se il codice viene compilato su una macchina a 64 bit?
- 17. Idiomi per un interruttore a tre stati?
- 18. Esiste un elenco pubblicamente disponibile degli Stati Uniti in forma leggibile dalla macchina?
- 19. Una definizione per set finiti in Agda
- 20. Esiste un termine per questo concetto e esiste in un linguaggio tipizzato staticamente?
- 21. Esiste un compilatore di codice macchina nativo per JavaScript?
- 22. Come rilevare se l'app Android viene forzata arrestata o disinstallata?
- 23. macchine a stati e stati multipli
- 24. Esiste un editor come jsfiddle disponibile per la macchina locale
- 25. sfortunatamente l'app viene arrestata durante il controllo della rete
- 26. Esiste un servizio o una procedura che può generare un IP quando viene data una posizione
- 27. Come si salva una variabile ansible in un file temporaneo che viene automaticamente rimosso al termine dell'esecuzione della playbook?
- 28. Esiste comunque un modo per indicare il tipo di dati in un array Postgres?
- 29. Esiste un metodo iOS che si attiva al termine di Autolayout?
- 30. MSSQL: esiste un modo per aggiungere automaticamente una voce a una tabella quando una voce viene aggiunta a un'altra tabella?
Ho dovuto dargli +1 per "non infinitamente-loopy" –