1
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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… $\endgroup$
    – Nathaniel
    Feb 23, 2021 at 10:26
  • $\begingroup$ The thing is, I need an efficient Turing machine... $\endgroup$
    – haidar.caldwell
    Feb 23, 2021 at 10:45
  • $\begingroup$ Less states does not mean more efficient. What you should look at is the asymptotic number of transitions. $\endgroup$
    – Nathaniel
    Feb 23, 2021 at 11:02
  • $\begingroup$ 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? $\endgroup$
    – haidar.caldwell
    Feb 23, 2021 at 11:09
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Feb 23, 2021 at 11:20

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$
15
  • $\begingroup$ Wdym by "go over the tape in passes"? $\endgroup$
    – haidar.caldwell
    Feb 24, 2021 at 21:35
  • $\begingroup$ Go over the tape once, then go over the tape again, and so on. Each time you go over the tape is a "pass". $\endgroup$
    – Yuval Filmus
    Feb 24, 2021 at 21:37
  • $\begingroup$ 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? $\endgroup$
    – haidar.caldwell
    Feb 24, 2021 at 21:39
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Feb 24, 2021 at 21:53
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Feb 24, 2021 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.