Turing machine, alphabet: $\{0,1\}$, accepts any word $w$, and on the tape the word $w$ is written followed by $0$-s as the number of the $1$-s in $w$

Question

So I just started studying Introduction to the Theory of Computation (I'm a student for Computer Science, this is the first week of the course), and I've got some exercises, which are only for myself (this is not an assignment or homework or something I need to deliver).

I stumbled across this problem which is basic I guess, and I know that the community here hates people who just ask questions without expressing what they tried so far and where they failed, so I'll try my best to express what my idea is (although I didn't accomplish any real result just an idea).

I can't express too much of what I tried because it was mostly brainstorming and I'm kinda frustrated after a good 6 hours of thinking about how to solve it.

The full problem is this:

• Build a Turing machine, which when it receives as input a word $w$ over the alphabet $\{0,1\}$, it ends in accept mode, and on the tape, the word $w$ is written followed by $0$-s as the number of the $1$-s in $w$. (for example if $w = 011001$ then on the tape will be $011001000$)

• There are a maximum of 5 states which you can use (including the accept/reject states).

• The tape alphabet is $\{0,1,B\}$ ($B$ for blank)

So the language that is recognizable by this Turing machine is obviously $\{0,1\}^*$ because it accepts any word $w$ over that alphabet.

My idea was to start from the left side going to the right and when encounter '$1$', replace it with '$B$', go to the very end right side, replace the end '$B$' with '$0$', and go back to the left side and start again to go to the right until we encounter the next '$1$' (the previous '$1$' is "marked" with '$B$' so we won't count him again) when all the '$1$'s' replaced with '$B$' that means that we finished and we can start replacing the '$B$' that replaced the '$1$'s'

My problem is how do I execute this idea, and is this kind of thinking is good? is this idea really solving the problem without any edge cases making it fail? how can I know when I finished and can go to the accept state?

Thanks

Answer 1

I would say your idea is good, but terminating following that approach is nontrivial. If I were to suggest a different approach for which reaching termination is easier, I'd sketch something like:

1. Start from the left and move right until either (a: you find B, thus accept; b: you find a 1, then you replace it with B and go to state 2)
2. Move to the right until you find a B, replace it with 0 and got to state 3
3. Move to the left until you find B, replace it with 1 and go to state 1.

I leave the details to you, but this approach makes it easier to detect when to accept.

Hope this helps!