A configuration of M relative to w is a pair c = (q, α), where q ∈ Q is some state and α ∈ Σ * is a sequence of tape symbols with length |α| = m. The intended interpretation of c is that the current state of M is q, the content of the circular tape is represented by α, and the tape head is positioned to read the first symbol of α.
the initial configuration of M for w, denoted by I M (w), takes the form I M (w) = (q 0 , w# m−n ), meaning that, at the start of the computation, the machine is in the initial state, the tape consists of the n symbols of the input string w followed by m − n blanks, and the tape head is positioned to read the first symbol of w. A configuration c is called existential, universal, accepting, or rejecting based on the type of its state q.