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

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

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

enter image description here

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more