# Reversing a binary string with a restricted Turing Machine

Some malevolent entity (me) asks you to construct a Turing Machine which, given an input on its tape of the form $$LbR$$ where $$b$$ is some binary string, changes this to $$Lb^{-1}R$$ then halts (where $$b^{-1}$$ signifies $$b$$ in reverse order).

For example, given input $$L001R$$, after the machine halts the tape should be $$L100R$$

The catch: you only have precisely the input space to use for the computation: i.e., the head of the Turing machine may not move left of the endpoint $$L$$ nor right of $$R$$, nor may it write over $$L$$ or $$R$$ (it may however move onto them and read them as it would any other letter in its alphabet). Your machine must be able to handle $$b$$ of arbitrary length. You may assume the head begins on $$L$$.

The following website may be very helpful for making your machine: https://morphett.info/turing/turing.html.

Bonus: My solution (posted as an answer) uses an alphabet of $$3$$ (non-endpoint) letters $$\{0,1,X\}$$ and has $$15$$ internal states. Can you do better in either capacity (or prove that it is not possible to do so)? I imagine it is impossible to do this with only the letters $$\{0,1\}$$, but I am not sure how to prove it.

The main idea behind the implementation is to have the head bounce back and forth between the two sides of the string, carrying a bit from one side over to the other, dropping it off, picking up a new bit, bringing it back over to the other side, etc. I use the letter $$X$$ on either side of the string to demarcate where I should 'drop off' the bit being carried. Each time I drop off a bit at an $$X$$, I move that $$X$$ toward the center of the string and pick up the bit where I wrote the $$X$$. Once the two $$X$$s meet, I drop off the final bit and halt.