Reversing a binary string with a restricted Turing Machine

Question

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.

Answer 1

You can find an implementation of my solution at this link.

Here's the idea behind the solution:

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.

The main technical difficulty is that the first time the head moves over from the left to the right, there is no X on the right at which to drop off the carried bit, hence in order to both place an X and drop off the value, we essentially need to pick up two bits from the right instead of one. This extra information increases the number of states needed (as I am using different states to 'store' the information about which bit is carried, so doubling the number of carried bits almost doubles the number of states).

At the link you can see step-by-step how my machine works which should help it be more understandable. It also contains the code with comments describing the states.