TM configuration; TM for palindromes

Configuration of a Turing machine

A configuration (instantaneous description) records everything needed to continue a computation: the current state, the tape contents, and the head position. It is written as a triple (q, u, a v) or as the string u q a v, where q is the state, u the tape contents to the left of the head, and a v the contents from the scanned symbol a onward (trailing blanks omitted). One move gives the relation ⊢. The start configuration for input w is q0 w, and w is accepted if q0 w ⊢* (a configuration in an accepting state).

Example: the configuration 10 q2 1 means the tape holds 101 with the head on the last symbol, in state q2.

TM for palindromes over {0,1}

Idea. Erase the first symbol, remember it, go to the last symbol, and check it equals the remembered one; erase it and repeat. If the string becomes empty (even length) or exactly one symbol is left (odd length), accept; otherwise reject.

States: q0 start; q1 / q3 go right remembering 0 / 1; q2 / q4 check the last symbol; q5 return left; qa accept.

The only difference from the wwᴿ machine is the two rules q2/q4 on ⊔, which accept when the middle symbol of an odd palindrome is left alone.

Examples

• 010: q0 erases 0 and goes right; the last symbol 0 matches and is erased; q0 now reads 1, erases it, finds nothing to the right, and q4 reads ⊔, so it accepts.
• 0110: two rounds of matching 0-0 and 1-1, then q0 reads ⊔ and accepts.
• 01: the last symbol is 1 but 0 was remembered; no move exists, so it halts without accepting.