Give the diagram of transitions of a Turing machine to a ribbon which accepts the language on the alphabet $\{0, 1\}$ of the words which contain as many $0$ as of $1$. (Note well that the $0$ and the $1$ can appear in any order.)
This problem is similar to $\{0^n 1^n : n \in \mathbb{N}\}$ except the fact that we mix up all the $0$'s and $1$'s and can be solved with a simple pushdown automata. An instance of an accepting word on the tape would be $010011000111$ and a rejecting word would be $010111$.
I am confused how to set that up. I have thought building a transition with two states :
- $q_0$ would be the starting starting which is also the accepting state.
- $q_1$ would be the rejecting state.
I have thought using the transition function which will move left when I meet a $0$, move right when I meet a $1$ and using the symbol $\$$ whenever a state has been visited.
Am I on the right track? How to build such diagram?
The machine below uses the standard $5$-tuple transition representation $(q_i,s_i,q_f,s_f,d)$ where $d\in\{L,R\}$; accepting and rejecting are expressed as $(q_i,s_i,Yes/No)$. The tape head is initially on the leftmost bit of the input, surrounded by a sea of blanks $-$. $b$ or $c$ represent either $0$ or $1$ and $\neg$ the negation.
Each pass of the machine will do the following, pairing up bits and recursing into smaller and smaller strings until a result is clear:
There are eight states in the machine and initially we start in state $L$. The transitions are as follows: $$(L,b,L_{\neg b},-,R)\\ (L,-,Yes)\\ (L_b,\neg b,L_b,\neg b,R)\\ (L_b,-,No)\\ (L_b,b,R,-,L)\\ (R,b,R,b,L)\\ (R,-,P,-,R)\\ (P,b,P_b,-,R)\\ (P,-,L,-,R)\\ (P_b,c,P_b,c,R)\\ (P_b,-,S,b,L)\\ (S,b,S,b,L)\\ (S,-,L,-,R)$$
A refinement of the above machine combines searching for an opposite bit and bit pickup into one forward-and-backward motion: $$(L,-,Yes)\\ (L,b,L_{\neg b},-,R)\\ (L_b,-,No)\\ (L_b,b,L,-,R)\\ (L_b,\neg b,M_b,-,R)\\ (M_b,-,No)\\ (M_b,\neg b,M_b,\neg b,R)\\ (M_b,b,R,\neg b,L)\\ (R,b,R,b,L)\\ (R,-,L,-,R)$$