0
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

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.

enter image description here

0
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