Question: Design a Turing Machine to find the value of log 2n, where n is a unary number.

0

0

We first intend to take the input in the form of binary numbers, since in finite automata, we deal with sequences rather than the number as a whole.

For 2, we use 10 Therefore, $log_2 2=1$, which is represented as 01

For 4, we use 100 Therefore, $log_24=2$, which is represented as 10

Hence, we find that the logic remains in erasing some additional 0 trailing after the 1.

We consider the input 16

16 in binary is 10000

$Log_2{16} = 4$

To obtain 4, we would have to erase the last two 0’s in 10000

Hence, we would be left with 100, which in decimal is 4, which is the required answer.

Please log in to add an answer.