Is there a term for a finite state machine that is guaranteed to halt?

Question

I was having a discussion earlier about a state machine, and there was a question as to whether it might not halt on some input. It seems like a property of state machines that is important and frequently mentioned, but I can't for the life of me figure out what the name of that property is. Is there such a term? Is it "haltable", "not-infinitely-loopy", or something else?

Virgilio

Had to give it +1 for "not-infinitely-loopy" – Auctioneer

Answer 1

A machine that always halts is called a decider.

A decider need only be a machine that halts on all inputs. For example, all DFAs are deciders, as are DPDAs.

Sustentacular

Ah, yes, that was it exactly! Thank you very much! – Virgilio

Cool! Didn't know that. I'll leave my previous answer below just in case people are interested in the Halting Problem. – Pleasant

Answer 2

My guess would be "halting", derived from the famous "halting problem", which is similar to your question, namely whether it will halt on a given input. An important consideration is that a machine is not defined as "halting" in general, but rather for a specific input. The general case is proven to be unsolvable (by Turing himself).

Pleasant