Turing machine and coming up with an idea

ignougroup
Problem Detail: I read many things about the Turing machine and understand how it works but what I can’t get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am given to solve? I mean: checking if a word is a palindrome, for example, consists of 11 states in the book I’m learning from. For my current state of knowledge, just sitting over an empty sheet of paper and coming up with all these states seems next to impossible, to say the least. When I try to do something like this, I get stuck immediately since I don’t know what should I do to make these states work somehow “together”. I don’t have such problems when programming in some prog languages but here, I just can’t figure out how I should approach something consisting of some n-teen states. Could you please point me some direction to learn about it?

Asked By : Straightfw

Answered By : Vor

Just to expand the comments above, you should try to find a high level algorithm, and then refine its steps in smaller pieces. For example, if you want to recognize palindrome words, a high level agorithm can be: 

1. check if the leftmost symbol is equal to the rightmost symbol 2. if they are not equal reject, otherwise delete them 3. if there are other symbols then goto 1, otherwise accept

That can be refined in the following way: 

1.1 move the head on the leftmost symbol 1.2 "store" its value 1.3 if it is the only symbol left then accept (w has an odd length) 1.4 otherwise move the head to the rightmost symbol 2.1 compare it to the "stored" one 2.2 if they are not equal halt and reject, otherwise 2.3 delete the rightmost symbol 2.4 move the head to the leftmost symbol 3.1 delete it 3.2 if the tape is empty halt and accept, otherwise 3.3 goto 1.1

The steps are “implemented” using the internal states of the Turing machine. While designing the Turing machine you can name the states with labels instead of “q0, q1, q2” to make the design process easier. If you have a single tape Turing machine, the step [1.2 “store” its value] means that you must use the internal states to “remember” the symbol read while the head moves to the rightmost one. Suppose you have two input symbols $a,b$ and $-$ is the blank symbol, then you can use a set of states La,L’a,CMPa and Lb,L’b,CMPb to represent (store) the leftmost symbol read; so steps 1.1, 1.2, 1.3, 1.4, 2.1, can be implemented in this way: 

     |  a      |   b     |   - START| a,R,La  | b,R,Lb  | -,R,START << move right until you find a symbol       La   | a,R,L'a | b,R,L'a | ACCEPT    << step 1.3   Lb   | a,R,L'b | b,R,L'b | ACCEPT    << step 1.3 L'a  | a,R,L'a | b,R,L'a | -,L,CMPa  << step 1.4  L'b  | a,R,L'b | b,R,L'b | -,L,CMPb  << step 1.4 CMPa | -,L,MVL | REJECT  |           << compare to a CMPb | REJECT  | -,L,MVL |           << compare to b MVL  | .......                       << move left

As you can see after reading the leftmost symbol the states are doubled: 

Lx we are on the first symbol after the leftmost one (which is symbol x) L'x we are moving rightward from the leftmost symbol x CMPx we are comparing the rightmost symbol with the leftmost symbol x

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7708