Turing machine to compute $⌈\log_2n⌉$ with 1 tape and unary input/output I'm trying to figure out how to make the action table for a Turing Machine computing $⌈\log_{2}(n)⌉$. The input and output shall be unary (meaning $3$ should represent $111$). I can only deal with 1 tape.
Also, I would prefer having 7 transition states, 1 final state, 24 actions and 5 symbols, but any other numbers are fine too. At the end of the computation, the TM head should be at the 1st $1$ from the left, of the output.
For $⌈\log_{2}(0)⌉$, I would like to have the symbol $N$ on the tape.
I would also like an easy-to-understand explanation, if possible.
One simple approach is repeated halving.
Remove a single 1 from the input (if you fail, output N).
Then go over the tape in passes. Each pass deletes every other 1 encountered (starting with the first). The number of passes required to delete all 1s is $\lceil \log_2 n \rceil$. You can count the number of passes as you go.
For example, suppose that $n=6$:
111111       Delete the first 1
b11111       Delete every other 1
2b1b1b       Delete every other 1
22bb1b       Delete every other 1
222bbb       Convert back to 1
111bbb       Done

The number of passes is $3 = \lceil \log_2 n \rceil$.