Turing Machine Notes

• As we discussed in lecture, if the string starts with an "a", it begins by erasing it and then proceeds to find the rightmost character. That leads to state q2. From there, it either finds a "b", which means it is not a palindrome, and heads towards final state q4 (which outputs "0") or it finds an "a" which it erases as it heads back toward state q0.

• We were discussing palindromes of odd length. Suppose that the middle character of such a palindrome is "a". Then you end up in state q2 finding yourself looking at a space. So I added a transition from q2 to the final state q6 with output 1 (verifying that it found a palindrome).

• I then added a parallel set of states for dealing with a first character of a "b". That takes you to q1 and q8. From q8 you go in one of three directions. If you see a "b", then that's a match and you head back to q0 through q5. If you see an "a", then it's not a palindrome, and you head towards q4 through q3 to provide the "0" output. And if you see a space, then you've found an odd-length palindrome with a "b" in the middle and you go to q6 with the output "1" to verify the palindrome.