0
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ thanks for the answer, another question is how can i know if the all string was checked? i mean if the string is "ABCBA" then i'm copying it to both of the tapes, and i'm checking for "A" and "B" so the first header will reach to C and "BA" from right of C will remain, and for the second header "BA" from left of C will remain.. so it will not stop.. $\endgroup$
    – Elior
    May 28, 2014 at 16:55
  • $\begingroup$ 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. $\endgroup$
    – askyle
    May 28, 2014 at 17:01
  • $\begingroup$ Think of it like this: if you copy the input word from one tape to the other cell by cell, how do you know when you're done copying the word? $\endgroup$
    – askyle
    May 28, 2014 at 17:03
  • $\begingroup$ yes i understand but this is work when you 1 tapes.. what about multitapes? $\endgroup$
    – Elior
    May 28, 2014 at 17:04
  • $\begingroup$ Why would it work any differently? :) $\endgroup$
    – askyle
    May 28, 2014 at 17:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .