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

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$$?

• 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? Why do you want to do this? I mean, why should it work? Well, you can cross every third and remain with 2/3, and then cross every second and remain with 1/3.
– user114966
Oct 4, 2020 at 15:20
• @Dmitry I'm asking only out of curiosity, as I was sitting for a few hours trying to find a machine that corsses every third and remain with 2/3. I'm asking for a state diagram because I couldn't find such. I already have a solution that I've found with state diagram that crosses 2/3. Oct 4, 2020 at 15:21
• Yes you can do it like that. First your machine moves to the right and replaces every third zero with a X than once you hit empty character move back to the left until you hit an empty character now move right and repeat but if you hit an X you just stay in the state you were. If you need further detail I can write an answer. Note that there are 3 states for counting zeros (0,1,2) and the one responsible for "1" zero is accepting. Oct 4, 2020 at 23:20
• @plshelp If you could please draw a state diagram, I'd be grateful Oct 4, 2020 at 23:22

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"}
"count 1 back"
read X: {move: left}
read 0: {move: left, next: "count 1 not finished"}
"count 2 back"
read X: {move: left}
read 0: {move: left, next: "count 2 not finished"}