1^3^n for n>=1 turing machine

Question

I want to make a turing machine which accept strings of 1's of length power of 3. 111, 111111111, 111111111111111111111111111, so on. But I am unable to make algorithm for this. So far I am able to make machine which accepts length of multiple of 3. Kindly help me

Answer 1

As with any programming task, your goal is to break the task into smaller problems you can solve, solve those, and put the pieces together to answer the harder problem. There are lots of ways to do this, generally, and you just have to find one that makes sense to you. Then, and only then, should you worry about getting a "better", "faster" program.

What makes a number a power of three?

1. the number one is a power of three (3^0)
2. if a number is a power of three, three times that number is a power of three (x = 3^k => 3x = 3^(k+1)).

We can "reverse" the direction of 2 above to give a recursive, rather than an inductive, definition: a number is a power of three if it is divisible by three and the number divided by three is a power of three: (3 | x && x / 3 = 3^k => x = 3^(k+1)).

This suggests a Turing machine that works as follows:

1. Check to see if the tape has a single one. If so, halt-accept.
2. Otherwise, divide by three, reset the tape head to the beginning, and start over.

How can we divide by three? Well, we can count a one and then erase two ones after it; provided that we end up erasing twice as many ones as we counted, we will have exactly one third the original number of ones. If we run out of ones to erase, however, we know the number isn't divisible by three, and we can halt-reject.

This is our design. Now is the time for implementation. We will have two phases: the first phase will check for the case of a single one; the other phase will divide by three and reset the tape head. When we divide, we will erase ones by introducing a new tape symbol, B, which we can distinguish from the blank cell #. This will be important so we can remember where our input begins and ends.

Q    T    |    Q'    T'    D
----------+-----------------
// phase one: check for 3^0
----------+-----------------
q0   #    |    h_r   #     S    // empty tape, not a power of three
q0   1    |    q1    1     R    // see the required one
q0   B    |    h_r   B     S    // unreachable configuration; invalid tape
q1   #    |    h_a   #     L    // saw a single one; 1 = 3^0, accept
q1   1    |    q2    1     L    // saw another one; must divide by 3
q1   B    |    q1    B     R    // ignore previously erased ones
----------+-----------------
// prepare for phase two
----------+-----------------
q2   #    |    q3    #     R    // reached beginning of tape
q2   1    |    q2    1     L    // ignore tape and move left
q2   B    |    q2    B     L    // ignore tape and move left
----------------------------
// phase two: divide by 3
----------------------------
q3   #    |    q6    #     L    // dividing completed successfully
q3   1    |    q4    1     R    // see the 1st one
q3   B    |    q3    B     R    // ignore previously erased ones
q4   #    |    h_r   #     S    // dividing fails; missing 2nd one
q4   1    |    q5    B     R    // see the 2nd one
q4   B    |    q4    B     R    // ignore previously erased ones
q5   #    |    h_r   #     S    // dividing fails; missing 3rd one
q5   1    |    q3    B     R    // see the 3rd one
q5   B    |    q5    B     R    // ignore previously erased one
----------+-----------------
// prepare for phase one
----------+-----------------
q6   #    |    q0    #     R    // reached beginning of tape
q6   1    |    q6    1     L    // ignore tape and move left
q6   B    |    q6    B     L    // ignore tape and move left

There might be some bugs in that but I think the idea should be basically sound.