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

• I answered that question here: cs.stackexchange.com/questions/132571/… You just need a little modification for the entry $0$ and for the head position. Also, your numbers are oddly specific… – Nathaniel Feb 23 at 10:26
• The thing is, I need an efficient Turing machine... – haidar.caldwell Feb 23 at 10:45
• Less states does not mean more efficient. What you should look at is the asymptotic number of transitions. – Nathaniel Feb 23 at 11:02
• oh okay. Btw, my blank symbol is $^$ and not $#$. Plus in your simulator, I can see $#$ and " " are 2 different symbols, since $#$ sometimes changes into " ". Why's that? My Turing machine basically needs to have something like $...^^^111111^^^...$ with the $...$ representing $^$'s. Does your simulation do the same thing? And is there an alternative way that doesn't deal with binary representation? – haidar.caldwell Feb 23 at 11:09
• The way you write the blank symbol is not important, you just need to adapt to your needs. Same thing for the simulator, I did not create the simulator, only the simulation, and I adapted my TM to the simulator. I don’t know if there is a way not to use binary representation, but I find it the simplest way to understand. – Nathaniel Feb 23 at 11:20

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

• Wdym by "go over the tape in passes"? – haidar.caldwell Feb 24 at 21:35
• Go over the tape once, then go over the tape again, and so on. Each time you go over the tape is a "pass". – Yuval Filmus Feb 24 at 21:37
• Okay so, where did the 2 come from? And wdym by every other 1? If we Delete every other 1 from step 2, don't we end up in all blanks? – haidar.caldwell Feb 24 at 21:39
• The 2 is a counter that counts the number of passes. It's easier to use a different symbol in order to avoid a mixup with the 1s, though perhaps it can be avoided. – Yuval Filmus Feb 24 at 21:53
• You do end up in all blanks, and that's on purpose. Take a look at my example. At this point, I suggest spending an hour (at least) trying to understand the algorithm and why it works. – Yuval Filmus Feb 24 at 21:54