Example: Palindromes over binary alphabet

Input alphabet: 0,1

Tape alphabet: 0,1,b

States

State	Interpretation
i	initial state
p₀	look for 0 at RHS
p₁	look for 1 at RHS
q₀	found RHS; check it's 0
q₁	found RHS; check it's 1
r	return to LHS
t	accepting state

Transitions

δ (i,b)	= (t,b,R)	accept if tape is blank
δ (i,0)	= (p₀,b,R)	delete 0 at LHS; look for 0 at RHS
δ (i,1)	= (p₁,b,R)	delete 1 at LHS; look for 1 at RHS
δ (p₀,0)	= (p₀,0,R)	move to RHS
δ (p₀,1)	= (p₀,1,R)
δ (p₁,0)	= (p₁,0,R)
δ (p₁,1)	= (p₁,1,R)
δ (p₀,b)	= (q₀,b,L)	found RHS; now check whether 0 or 1
δ (p₁,b)	= (q₁,b,L)	found RHS; now check whether 0 or 1
δ (q₀,0)	= (r,b,L)	check RHS=0; delete it
δ (q₁,1)	= (r,b,L)	check RHS=1; delete it
δ (q₀,b)	= (t,b,R)	accept if all tape is blank
δ (q₁,b)	= (t,b,R)	accept if all tape is blank
δ (r,0)	= (r,0,L)	return to LHS
δ (r,1)	= (r,1,L)	return to LHS
δ (r,b)	= (i,b,R)	found LHS; reurn to state i

Example Computation

Below is a depiction of the initial state of the Turing machine with a tape and input word, where b denotes the blank symbol. (As you can see, the word is a palindrome, so it should be accepted.) Underneath is a table of transitions, with the one that is used first highlighted. Then we depict alternately each successive state/tape and each transition that is used next.

                        step 1
 10100101bbb...         next
 i

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 2
 b0100101bbb...         next
  p                     back
   1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 3
 b0100101bbb...         next
   p                    back
    1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 4
 b0100101bbb...         next
    p                   back
     1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 5
 b0100101bbb...         next
     p                  back
      1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 6
 b0100101bbb...         next
      p                 back
       1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 7
 b0100101bbb...         next
       p                back
        1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 8
 b0100101bbb...         next
        p               back
         1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 9
 b0100101bbb...         next
         p              back
          1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 10
 b0100101bbb...         next
        q               back
         1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 11
 b010010bbbb...         next
       r                back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 12
 b010010bbbb...         next
      r                 back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 13
 b010010bbbb...         next
     r                  back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 14
 b010010bbbb...         next
    r                   back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 15
 b010010bbbb...         next
   r                    back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 16
 b010010bbbb...         next
  r                     back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 17
 b010010bbbb...         next
 r                      back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 18
 b010010bbbb...         next
  i                     back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 19
 bb10010bbbb...         next
   p                    back
    0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 20
 bb10010bbbb...         next
    p                   back
     0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 21
 bb10010bbbb...         next
     p                  back
      0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 22
 bb10010bbbb...         next
      p                 back
       0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 23
 bb10010bbbb...         next
       p                back
        0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 24
 bb10010bbbb...         next
        p               back
         0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 25
 bb10010bbbb...         next
       q                back
        0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 26
 bb1001bbbbb...         next
      r                 back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 27
 bb1001bbbbb...         next
     r                  back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 28
 bb1001bbbbb...         next
    r                   back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 29
 bb1001bbbbb...         next
   r                    back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 30
 bb1001bbbbb...         next
  r                     back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 31
 bb1001bbbbb...         next
   i                    back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 32
 bbb001bbbbb...         next
    p                   back
     1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 33
 bbb001bbbbb...         next
     p                  back
      1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 34
 bbb001bbbbb...         next
      p                 back
       1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 35
 bbb001bbbbb...         next
       p                back
        1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 36
 bbb001bbbbb...         next
      q                 back
       1

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 37
 bbb00bbbbbb...         next
     r                  back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 38
 bbb00bbbbbb...         next
    r                   back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 39
 bbb00bbbbbb...         next
   r                    back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 40
 bbb00bbbbbb...         next
    i                   back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 41
 bbbb0bbbbbb...         next
     p                  back
      0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 42
 bbbb0bbbbbb...         next
      p                 back
       0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 43
 bbbb0bbbbbb...         next
     q                  back
      0

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 44
 bbbbbbbbbbb...         next
    r                   back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 45
 bbbbbbbbbbb...         next
     i                  back

δ (i,b) = (t,b,R)	δ (p₀,0) = (p₀,0,R)	δ (p₀,b) = (q₀,b,L)	δ (q₀,b) = (t,b,R)
δ (i,0) = (p₀,b,R)	δ (p₀,1) = (p₀,1,R)	δ (p₁,b) = (q₁,b,L)	δ (q₁,b) = (t,b,R)
δ (i,1) = (p₁,b,R)	δ (p₁,0) = (p₁,0,R)	δ (q₀,0) = (r,b,L)	δ (r,0) = (r,0,L)
δ (r,b) = (i,b,R)	δ (p₁,1) = (p₁,1,R)	δ (q₁,1) = (r,b,L)	δ (r,1) = (r,1,L)

                        step 46
 bbbbbbbbbbb...
      t                 back

At this point the machine is in accepting state t, and there are no transitions from t, so the machine halts and accepts.