Problem Detail: I need to describing a Turing machine that computes $lceillog_{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.
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:
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/18537
