# Construct a Turing Machine that recognizes the set $\{0^{2n}1^n|n\geq 0\}$

The full question is: Construct a Turing machine that recognizes the set $\{0^{2n}1^n \mid n\geq 0\}$. The Turing machine starts with the input on the tape and the head over the leftmost symbol of the input. The symbols to the left of the input are blanks out to infinity, as are the symbols to the right of the input. If the string is accepted, the machine should halt with 1 on the tape (the rest of the tape should be blank). If the string is rejected, the machine should halt with 0 on the tape.

Yes, this is a homework question, but I think I just need some help understanding the problem. We have not gone very in depth into Turing Machines, and he suggested we should just write the answer graphically like a Deterministic Finite State Machine with read, write, and direction in the transitions.

I am getting stuck because I can only think about it in terms of 3 different paths (being 001, 100, 010), but I know this is most likely not correct, and I do not know how to recognize if the string is not in the set. I understand that the machine know the string has ended when it reads a blank, and then it will move right one and write either a 1 or 0 depending on if the string is accepted or not, but I can only think about it as 3 different paths.

Help would be appreciated! Thanks!

• Assume you are the Turing machine, and you have to decide whether to accept a tape with $0000000000000001111111$. You can't directly count, as you have no "infinite" memory, other than writing on the tape. If you can describe that process you have written an informal TM program. – Hendrik Jan Oct 30 '16 at 18:23
• If you have a long string it would be good to mark or erase symbols on the both sides. Check if there are consecutive 0 followed by consecutive 1 (reject otherwise). And then erase on the both sides. If there is nothing to erase while the state indicates there should be - reject, otherwise you will end up with a blank tape, write 1 and accept. – Evil Oct 30 '16 at 19:50
• Do not think in terms of a DFA. Many students have the misunderstanding that Turing machines are glorified finite-state automata. Unless the Church-Turing-thesis is false, the Turing machine model is powerful enough to describe any algorithm imaginable. So instead write down a pseudocode algorithm that describes how a Turing machine should examine its input to check if it is of the form $0^{2k}i^k$ for some $k$. One idea that might be useful here is to cross off one $1$ every time the machine has seen two consecutive $0$s. Once you have the algorithm, you can describe the machine in detail. – Hans Hüttel Oct 30 '16 at 20:08
• To avoid further misunderstanding - not every algorithm imaginable... I imagine algorithm that tells me whether another one stops... – Evil Oct 30 '16 at 20:14
• By "imaginable" I of course mean "that can be constructed". – Hans Hüttel Oct 30 '16 at 21:18

Here is a Turing machine on the online simulator I found here.

name: Recongnize 0^2n 1^n
init: s0
accept: acc

s0, 0
s1, _, >

s1, 0
s2, _, >

s2, 0
s2, 0, >

s2, 1
s2, 1, >

s2, _
s3, _, <

s3, 1
s4, _, <

s4, 0
s4, 0, <

s4, 1
s4, 1, <

s4, _
s0, _, >

s0, _
acc, _, -


The idea is to delete the two zeroes on the left, got to the end on the right, delete one, go to the way to the left, repeat. Accept only when after deleting 1 on the right the tape is empty.

You have two main steps. You first have to verify that the input is in the language. If so, erase it all and write a $1$, otherwise erase it all and write a $0$. I'm assuming the input alphabet is $\left\{0,1\right\}$ and the tape alphabet is $\left\{0,1,x,␣\right\}$.

Roughly, you're going to want to pair up the first half of $0$s with $1$s, by crossing off a $0$ then a $1$ with $x$s, moving the tape head back and forth across the tape, until you run out of $1$s. If you run out of $0$s to cross off before $1$s, you should reject since there's less $0$s than $1$s.

Then you should pair up the rest of the $0$s with the crossed off $1$s, crossing and uncrossing them respectively, one at a time, moving back and forth like before. If you run out of $0$s to cross off before uncrossing all of the $1$s, you have less than twice as many $0$s as $1$s, so reject. If you uncross the rest of the $1$s before crossing off the rest of the $0$s, you have more than twice as many $0$s as $1$s.

If you end up crossing off the rest of the $0$s along with uncrossing all of the $1$s, you have twice as many $0$s as $1$s and should accept, but first you need to clear the tape and write your output. If you have already rejected, do the same.

After you have constructed a TM, I highly urge you to test it with varying inputs, like $\epsilon$, $0$, $1$, $10$, $01$, $001$, $0010$ to verify it's accepting and rejecting the appropriate inputs.