There is a following Turing machine. I want to understand what it is doing :
enter image description here

I tried running it on input 100, 10000. Both these strings are accepted whereas 10,1000 are rejected
That leads to a good guess that it's accepting the string's with 1 followed by 0's where number of
0's = power of 2. But I can't prove it or deduce it from looking at the state diagram of it.
Any insights into it ?


I think your interpretation is correct. $q_i$ and $q_{ii}$ are states that guarantee that $10$ and $100$ will be correctly accepted. It is clear that any other input of size $\leq 3$ will be rejected.

Now suppose you are in state $q_s$, the tape is $1Z^{2^k}u$ (with $u\in \{0,1\}^*$), and the head is in position of the first $Z$ of the tape. The cycle $q_s, q_d, q_r, q_l$ will let you do round trips, each trip transforming a $Z$ in $Y$, and a $0$ in $X$.

On the last trip, you will transform the last $Z$ in $Y$, then cross all $X$'s (in $q_{pf}$), and transform a zero in $X$. Therefore, if $u\neq 0^{2^k}v$, the Turing machine will reject. If not, we will get in $q_f$.

If $u = 0^{2^k}v$, then three cases are presented:

  • $v = \varepsilon$, we finish in $q_{acc}$ so the word is accepted (and the input was necessarily $10^{2^{k+1}}$);
  • $v = 1w$, we reject;
  • $v = 0w$, we transform all $X$'s and $Y$'s into $Z$'s, reach the left most symbol (which must be 1), and finish in $q_s$. The tape is then $1Z^{2^{k+1}}v$ and we are in the first situation.

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.