Known lower bounds on halting for finite machines?
It seems that your machine runs without any further input once it is
started. Whatever input it has is encoded in its starting state. Since
your machine is deterministic, there is at most a single transition
from each state. So the state-transition graph of your automaton is a
directed graph composed of paths that either are isolated cycles or
are simply open linear path from an initial node/state to a final node
(corresponding to a halting state without transition). There may be
any (positive) number of such paths, possibly only one. Actually, only one of these paths is relevant, the one containing the initial state.

Depending on whether the initial state of your automaton is on a
cyclic path or on an open path, the automaton will run for ever or
halt at the end of the open path. The former is identified by checking
whether a state is visited twice. The latter is identified by the fact
that a halting state (without transition) is encountered.

In the question, you do not give any constraint or information on the way states and
transitions are defined, other than the following:


from a given state, there is a transition function that gives you
the next state;
you can know whether two states are the same or not.


So the only way you can map the graph structure to reason about it is
to follow the transition function from state to state, even when
knowing the total number of states $n$.

With $n$ states, you can have a graph $C_n$ composed of one cycle of
$n$ states. You can also have a graph $L_n$ composed of one open
linear path of $n$ states starting with the initial state and ending
with a halting state. The former is non-halting, while the latter is
halting.

Still assuming you know the number of states, and using only the gven
primitives, the only way to find a difference is to follow $n-1$
transition. Then you are either in a halting or a non-halting state.
The former tells you that computation halts, while the latter tells
you it does not halt.

You clearly will not do better when you do not know $n$ in
advance. Actually, you then need only one more transition to detect that
the computation is not halting.

So there is no way to decide whether your automaton halts in fewer
steps, unless you have other means for analyzing the state-transition
graph.

In other words, the only way you can have a faster algorithm is to
have some formalism that structures the state-transition graph with
properties that can be used to analyze it without having to follow the
transitions.