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:
- Create a Turing Machine M with 2 tapes.
- Copy the input string to both of the tapes.
- Set the first tape's at the beginning and the second tape's head at the end.
-
Move on the tapes and compare each
value from the tapes:- if they're different – stop and reject
- continue the check.
- 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?
Best Answer
I'm assuming you're using this definition.
Strictly speaking, no—all the headers start in the same position. However, it's fairly trivial to move one of the headers to the end of the input: if it's not at the end, move right; repeat. In fact, when you finish copying the input from tape 1 to tape 2 your headers are already at the end, so what you have to do is rewind one of them to the beginning. More often than not, it's OK to tacitly assume that you can do this and other simple preparations (except, of course, when you're asked to show your constructions explicitly).
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.