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

 modified 3.3 years ago  • written 3.3 years ago by Pooja Joshi • 740
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.