I need to describing a Turing machine that computes $\lceil\log_{2}(n)\rceil$ I know that:n = 1, 2, 3, 4, 5, 6, 7, 8, ... f(n) = 0, 1, 2, 2, 3, 3, 3, 3, ...So I'm thinking of putting $n$ on the tape. Then keeping a count of how many times I multiply 2*2 until it is greater than than $n$. For example for n=5, 2*2*2=8, number of two's is 3 so then $f(n)$ is 3. I don't know how to translate this to the ticker tape of the Turing machine.But would something like this work? Put $n$ 1's on the tape followed by a 0. Compute 1^(2^1), then check if 1's on the left of the 0 on the tape is less than or equal to the 1's on the right of the 0. If its not then repeat it for 1^(2^(1)). It keeps doing this until the left side has less than or equal number of 1's.
Describing a Turing machine that computes $\lceil\log_{2}(n)\rceil$
complexity theory;turing machines;automata
A simple approach is:Put $i \gets 0$ on the tape (store $i$ on the tape after $n$).Compute $2^i$ (store it on the tape after $i$).Check if $2^i \ge n$.  If yes, output $i$.  If no, increment $i$ and go to step 2.You can work out the gory details on your own -- this is your exercise, after all!  This requires you to be able to compute $2^i$ (given $i$) and to be able to compute $i+1$ (given $i$), but it sounds like you already know how to do that.