Describing a Turing machine that computes $\lceil\log_{2}(n)\rceil$

Problem Detail: 

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.

Asked By : Data

Answered By : D.W.

A simple approach is:

1. Put $i \gets 0$ on the tape (store $i$ on the tape after $n$).

2. Compute $2^i$ (store it on the tape after $i$).

3. 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18537