2
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ The answer would depend of the version of Turning machine you have to use. One would need its configurations, what its in- and output facilities are. The various mathematical models can differ slightly, and we do not know what kind of model you use. $\endgroup$ – mvw Nov 20 '16 at 16:31
  • $\begingroup$ I don't know if this is correct... but alphabet={0,1}; empty cells are zeroes and I can only place 1 and 0 to the cell. That's all I can get from description of the problem. $\endgroup$ – Viktor K Nov 20 '16 at 16:35
1
$\begingroup$

Here is a start:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Thanks! I'll try to construct my table of instructions, seems to be exactly what I needed. $\endgroup$ – Viktor K Nov 20 '16 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.