0
$\begingroup$

How would you construct a Turing Machine that calculates log2(n)?

The process must take in an input such as 4 and output the result in a unary format such as a 11 (11 = 2 in unary)?

In the final output tape, the tape should only contain blank symbols followed by a consecutive number of 1's from the final head position.

Many Thanks

$\endgroup$
5
  • 1
    $\begingroup$ What is the format of the input? If it is binary there is not much to do, just turn all characters into $1$s and remove the last one. $\endgroup$
    – plop
    Feb 23, 2021 at 16:11
  • $\begingroup$ The format is a natural number but in unary, so if the user wants an input of 4 they will use 1111. $\endgroup$ Feb 23, 2021 at 16:15
  • 1
    $\begingroup$ Then this question has been answered here before, if I remember correctly. Essentially pass over the input replacing each pair of $1$s by a single one. Every time you finish going over the input, write a $1$ in the output. Repeat with the modified input until it dissapears. $\endgroup$
    – plop
    Feb 23, 2021 at 16:22
  • 1
    $\begingroup$ Popular question, it has been asked before, earlier today actually: Turing machine to compute ⌈log2(n)⌉ with 1 tape and unary input/output. And for the answer, see @plop's comment for a excellent suggestion. $\endgroup$ Feb 23, 2021 at 16:24
  • $\begingroup$ That is much more efficient than the method I am currently trying to pursue, thanks Plop! $\endgroup$ Feb 23, 2021 at 16:36

0

Browse other questions tagged or ask your own question.