# What is this turing machine doing

There is a following Turing machine. I want to understand what it is doing :

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.