Problem: Write program for Turing Machine (set of instructions) to transform some pre-formatted input to fixed-formatted output.
$$q _{1}1^{x}01^{y}0 => \begin{cases} q _{0}1^{x}, & \text{if } y>x\\ q_{0}0, & \text{if } y \le x \end{cases} $$
Test:
Some examples of what I need to achieve:
Input: 111011110
Output: 111
and
Input: 1110110
Output: 0
and
Input: 110110
Output: 0
Algorithm:
1. Start position, head at left symbol.
1. If 0, then shift by 2 to the right then go to step 18.
2. If 1, then we move by the first group of ones to the right to 0.
2. Shift to the right.
1. If 0, then shift by 2 to the left and go to step 19.
2. If 1, then we move by the second group to the right to 0.
3. Shift to the left by 1 and change 1 to 0.
4. Shift to the left.
1. If 0, then go to step 11.
2. If 1, then we move by the second group to the left.
5. Shift to the left, then we move by the first group of ones to the left to 0.
6. Shift to the right by 1 and change 1 to 0.
7. Shift to the left by 1 and change 0 to 1.
8. Shift to the right by 2.
1. If 1, then go to step 1.
2. If 0, then go to step 9.
9. Shift to the right.
1. If 1, then go to step 10 (x<y).
2. If 0, then shift by 2 to the left and go to step 13 (x=y).
10. Move by all ones in a group to the right and change them to 0 END (x<y).
11. Shift to the left by 3.
1. If 0, then we move by group of zeroes to 1 and go to step 18.
2. If 1, then we go to step 14.
12. We move by group of ones to the left to 0.
13. Shift to the left.
14. We move by group of ones to the left to 0.
15. Shift to the right.
16. We move by group of ones to the right to 0 and change them to 0.
17. Shift to the right.
18. We move by group of ones to the right to 0 and change them to 0 END.
19. We move by group of ones to the left to 0 and change them to 0 END.
Question: I tested my algorithm and it works, but how to build the instruction table for Turing machine? I don't understand the basic logic here.
I need instructions in this way (kinda):
$q_{1}1 \to 1Rq_{1}$ (example)
Can you, please, show me how to do this, at least for some first instructions...
Here is a start:
The nodes are the states, and the transitions show how you go from state to state depending on what symbol you read. So for example, the transition from $q_1$ to $1_a$ would translate to the instruction $q_1 0 \rightarrow 0R1_a$. But I would recommmend using this kind of more graphical representation as you can keep better track of the flow of the program as compared to when you would just generate a list of instructions. After you have completed the flow diagram, you can straightforwardly translate it to a list of instructions.
Notice how I tried to keep your numbering, but clearly there is no perfect mapping between your numbering and states of the TM. In other words, the line numbers in your algorithm may translate to multiple nodes in the TM, hence the $1_a$, $1_b$, etc. Also note that this is just for the first two and last two lines of your algorithm, so the whole diagram will be pretty big: get out a nice and big sheet of paper!
I hope this is a helpful start for you. Let me know if you need some more help.