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!
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 '20 at 15:20