Using a Turing machine. If the input tape of the machine consisted of a string of 0's and 1's, how would you approach the problem given that the output of the machine should be 1 or 0 respectively depending if it's a palindrome or not.

I'm really struggling to get my head round the idea.

Any guidance is much appreciated.

I tried working out the idea in my head and on paper for example: 1, 0, 1, 0, 1

I would start at 1 in state "start" and then check the symbol. In this example, the symbol is 1, so I would set the symbol to a new "marked" symbol and move to the right in a new state called "compare_right_1", in this state the machine would reach the end and read a blank symbol and hence reach the end of the tape, so move left and check the symbol for a 1, if the symbol is a 1 then move to the next space on the left, if not then quit as its not a palindrome.

I'm not sure if this is the right approach.

  • $\begingroup$ Yes, you start from the left; mark the first symbol and check whether the last symbol matches. If it does match, you do the same with second symbols from both ends, and so on. The processed symbols needs to be marked so that you know your current boundary. This is a standard textbook example, and there are plenty of solutions floating online. Let us know if you still have any doubts. $\endgroup$
    – codeR
    Commented May 15 at 7:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.