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

Mumbai university > Comp > SEM 4 > TCS

Marks: 10M

Year: Dec 2014

ADD COMMENTlink
modified 3.0 years ago  • written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
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

ADD COMMENTlink
written 3.0 years ago by gravatar for Pooja Joshi Pooja Joshi740
Please log in to add an answer.