0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dmitry Oct 4 at 15:20
  • $\begingroup$ @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. $\endgroup$ – ChikChak Oct 4 at 15:21
  • $\begingroup$ 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. $\endgroup$ – plshelp Oct 4 at 23:20
  • $\begingroup$ @plshelp If you could please draw a state diagram, I'd be grateful $\endgroup$ – ChikChak Oct 4 at 23:22
0
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

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.