Create a Turing-machine that decides $A=\{0^{3^n} | n\ge 0\}$

Question

I need to find a Turing machine that decides $A=\{0^{3^n} | n\ge 0\}$.

I tried doing the same as Sipser does on page 172 in his back, where he creates a Turing machines that decides $A=\{0^{2^n} | n\ge 0\}$, by iterating over the input, and crossing (by writing $x$) on every other $0$.

I wanted to cross every third $0$, but I failed getting to any possible machine. Either I create a machine that does not accept $000$, or a machine that accepts $00000$ or $000000$.

I found a solution that for each iteration cross off $2/3$ of the $0$ over the tape, meaning after each iteration we remain with third of the $0$. But is it possible to get to a solution as I wanted? where on each iteration we cross off third, and remain with $2/3$?

Answer 1

Okay I can't draw and the only tools for visualizing Turing machines aren't the most practical so I'll give you a list of states and how they behave. Note that next refers to the next state and that if next and write aren't assigned the machine doesn't move to another state / doesn't write something.

A brief verbal description since the machine is somewhat big (9 states). There are states for count 0/ count 1 and count 2. Which count zeros...; Now when the machine reaches a third zero it is replaced with X and we are back to "count 0". Every of those three states has a "back" state responsible for moving back to start if we encounter an "empty". Notice that if we do not encounter a zero on our way back we are done and have to report accept or reject. If however we encounter a zero on our way back "count i back" switches to state "count i not finished" which if it encounters a "empty" (while moving left) will switch back to "count i" ($i \in \{0,1,2\}$.

"count 0" (initial state)
    read 0: {move: right, next: "count 1"}
    read X: {move: right}
    read empty: {move: left, next: "count 0 back"}
"count 1"
    read 0: {move:  right, next: "count 2"}
    read X: {move: right}
    read empty: {move: left, next: "count 1 back"}
"count 2":
    read 0: {move: right, write: X, next: "count 0"}
    read X: {move: right}
    read empty: {move: left, next: "count 2 back"}
"count 0 back"
    read X: {move: left}
    read 0: {move: left, next: "count 0 not finished"}
    read empty: reject
"count 1 back"
    read X: {move: left}
    read 0: {move: left, next: "count 1 not finished"}
    read empty: accept
"count 2 back"
    read X: {move: left}
    read 0: {move: left, next: "count 2 not finished"}
    read empty: reject
"count 0 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 0"}
"count 1 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 1"}
"count 2 not finished"
    read X/0: {move: left}
    read empty: {move: right, next: "count 2"}

Hope you get the idea!