Turing machine and coming up with an idea

Question

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?

Answer 1

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

Answer 2

Try using visual designers like this or turingkara-en, which also contains exercises.

Keep in mind that the TM is meant to be a theoretical, minimalistic model to simplify proofs. Programming on the other hand will get nasty fast. So don't think it's a shame to have problems with programs requiring more than half a dozen states.

Answer 3

Suppose you're given some string over a three-character alphabet $\{0,1,\,\_ \}$, where the latter is the blank character. You'd like to know if the input consists of a single "word" over $\{0,1\}$, ending with one or more blank characters, which is a palindrome. (There could be multiple words later on the tape, but you're not paid to care.) How could you figure this out?

A word $W = a W' b$ is a palindrome if and only if $a = b$, and $W'$ is also a palindrome. To find the end of the word, you'll need to look for the last character preceding a blank; and whether or not $W$ (or $W'$) is a palindrome, you don't really need to hang onto that first input character $a$ for very long. So you can probably proceed by blanking out the first character (while "storing" what value it is in one of two branches in the program code, using some of the states as a limited memory), and basically shuttle back and forth between the left- and right-hand sides of the string, checking whether the two ends of the word are the same. This is basically the same as working it out for a two-hundred long string of characters over the alphabet where you might scratch out letters on either end (rather than blanking, but it's basically the same) until you found a mismatch, or made your way to the middle.

Generally when designing a Turing machine to solve some problem, you have to find some way to break up the problem into little pieces that can be easily solved by either making local changes to the input, or by recording some piece of information in some long branches or decision-tree-like structures in the state transitions while the machine head searches back and forth for the information that it needs to solve the problem. The challenge in solving problems on a Turing machine is to find a way that involves little to no local memory at the machine head, because it has no stored memory of its own aside from what state it is in; and so it's a sort of a challenging parsing problem. But in the end it's doing basically the same thing — in an extremely primitive way — that you do when you solve a problem involving a long input: it simply reads and rereads the input as it needs to, going back and forth. For simple problems such as this, if you think very carefully about how you personally would go about solving such a problem (perhaps while sleep deprived and therefore not having the sharpest memory), you can start to figure out how to write the state transitions for the problem.

Now, if you're told to do it in a specific number of states, that can be difficult, but certainly you can start by trying to find a straightforward way of doing it first, and then thinking (if you've used too many states) if there are any simplifications or optimizations that you can apply, by taking advantage of the structure of the problem somehow. There isn't any sort of general procedure that you can apply to do this, so it's basically down to whether or not you can find the essential structure of the problem (and whether or not your exercise is free from typos).