the DFA acceptance problem

Here is the most basic computational question you can ask about a finite automaton: given a particular deterministic finite automaton (DFA) and a particular input string, does the automaton accept that string? Phrased as a language, it is the set A_DFA = {(B, w) : B is a DFA and B accepts w}. Like a turnstile that just tracks which state it is in, a DFA's behaviour on a fixed input is utterly mechanical, so this question has a dead-simple, always-halting answer.

The decision procedure is just to simulate. Read the encoding of the DFA B (its states, alphabet, transition function δ (delta), start state, and accept states) and the string w. Place a finger on the start state. For each symbol of w in turn, follow the single transition δ(state, symbol) to the next state. There is no choice and no backtracking — a DFA is deterministic, so each symbol leads to exactly one next state. After consuming the last symbol of w, check whether the current state is an accept state: if yes, accept; if no, reject. The simulation does exactly |w| transitions and then stops, so it always halts.

Therefore A_DFA is DECIDABLE. This is a foundational 'sanity' result: the simplest model of computation has a trivially decidable membership question. It also sets up a recurring theme. The same surface question — 'does this machine accept this input?' — is decidable for DFAs (and NFAs and CFGs), but for Turing machines it becomes the undecidable A_TM. The reason is exactly that a DFA's run is bounded (it lasts |w| steps and cannot loop), whereas a Turing machine's run can wander forever.