This is the third part of the Turing Machine series. For your convenience you can find other parts in the table of contents in Part 1 – Addition

Today we check if given word w is a palindrome. First, we add delimiters at the beginning and at the end. Next, we check first character from the left, go to the end and check if the last character matches. Then we go to the beginning and repeat.

States:

q0 - start
q1 - a in buffer
q2 - b in buffer
q3 - add $ at the end
q4 - return to begin
q5 - checking first character from the left
q6 - going to the end with a
q7 - going to the end with b
q8 - checking a as the last character
q9 - checking b as the last character
q10 - success

The input looks like this:

abba

Transition table:

a,q0,$,q1,R
b,q0,$,q2,R

a,q1,a,q1,R
b,q1,a,q2,R
.,q1,a,q3,R

a,q2,b,q1,R
b,q2,b,q2,R
.,q2,b,q3,R

.,q3,$,q4,L

a,q4,a,q4,L
b,q4,b,q4,L
$,q4,$,q5,R

a,q5,$,q6,R
b,q5,$,q7,R
$,q5,$,q10,R

a,q6,a,q6,R
b,q6,b,q6,R
$,q6,$,q8,L

a,q7,a,q7,R
b,q7,b,q7,R
$,q7,$,q9,L

a,q8,$,q4,L
$,q8,$,q10,L

b,q9,$,q4,L
$,q9,$,q10,L