Acceptance, Halting, Rejection: Given a Turing machine M = (Q,Σ, Γ, δ, q0,B, F), the transition function δ is partial - it need not be defined for all inputs and states. When not defined, the machine becomes “stuck” - and is said to halt. Therefore, note that a TM can halt in any state. Also, by convention, no moves are defined out of the control states within F. Therefore, a TM always halts when it reaches a state f ∈ F. Here are further definitions:
A TM accepts when halting at f ∈ F.
A TM rejects when halting in any other state outside F.
A TM loops when not halting.
“Acceptance” of a TM closely examined Compared to DFAs and PDAs, the notion of acceptance for a TM is unusual in the following sense: a TM can accept an input without fully reading the input—or, in an extreme situation, not even reading one cell of the input (e.g., if q0 ∈ F)! Hence, curiously, any TM with q0 ∈ F has language Σ∗. On the other hand, if a TM never accepts, its language is ∅. This can be the result of the TM looping on every input, or the TM getting stuck in a reject state for every input. As a final illustration, given an arbitrary language L1, a TM that accepts any string within the set L1 and does not accept (loops or rejects) strings outside L1, has L1 as its language.
Instantaneous descriptions: While capturing the ‘snapshot’ of a TM in operation, we need to record the control state of the machine, the contents of the tape, and what the head is scanning. All these are elegantly captured using an instantaneous description containing the tape contents, w, with a single state letter q placed somewhere within it. Specifically, suppose that the string lqr represents that the tape contents is lr, the finite-state control is in state q, and the head is scanning r[0]. The initial ID is q0w, for initial input string w. We define, the ‘step’ function that takes IDs to IDS, as follows:
l1par1 l1bqr1 if and only if δ(p, a) = (q, b,R). The TM changes the tape cell contents a to b and moves right one step, facing r1[0], the first character of r1. Similarly, l1cpar1 l1qcbr1 if and only if δ(p, a) = (q, b,L). The TM changes an a to a b and moves left one step to now face c, the character that was to the left of the tape cell prior to the move.
We define the language of a TM M using ∗:
L(M) = {w | q0w ∗ lqf r, f or qf ∈ F, and l, r ∈ Σ∗}.
In other words, a TM that starts from the initial ID q0w and attains an ID containing qf (namely lqf r, for some l and r in Σ∗) ends up accepting w.
