# Multi-Tape Turing Machines to find palindrome

Given an Alphabet {a,b,c} , produce a Turing Machine which recognize if a given input string X is a palindrome. means if X is a palindrome, TM is halting and accepting, else halting and rejecting. You can use any model of Turing Machine (in terms of number of tapes)

My solution is:

1. Create a Turing Machine M with 2 tapes.
2. Copy the input string to both of the tapes.
3. Set the first tape's at the beginning and the second tape's head at the end.
4. Move on the tapes and compare each value from the tapes:

• if they're different - stop and reject
• continue the check.
5. stop and accept.

My question is it possible to initialize the header position of the different tapes in different places as I want? Another thing is how to describe this (the headers position) and the value's checking in a transition diagram or transition table?

As for the transition table (diagrams become a bit unwieldy here), decomposing the algorithm into smaller steps like you did is a good start. Try decomposing it further into even smaller steps, and replacing terms like "repeat" with "go back to step $n$". You'll eventually end up with steps that look like "if header 1 sees $a$ and header 2 sees $a$: move header 1 right, move header 2 left, and go back to step $15$". By that point, the transition table should be straightforward.
• The exact details depend on the model you're using, but one usually assumes that every cell (except those holding the input) starts out with a special blank symbol (say, $\phi$), which is different from all the letters in your alphabet. You know you've read past the end of the input when you see a blank instead of a normal letter. May 28 '14 at 17:01