NIELIT 2017 DEC Scientist B - Section B: 37

Question

Which of the following statement is true?

$S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine.

$S2$: Every non-deterministic Turing machine has an equivalent deterministic Turing machine.

• A. $S1$
• B. $S2$
• C. Both $S1$ and $S2$
• D. None of the options

Answer 1

$B$  (Only $S_{2}$) is correct as NDTM and a DTM are equivalent in power.

For $S_{1}, $no matter how many tapes there are in a Turing-machine, it's power eventually is equivalent to a single tape turing machine.

Reference: Multi-tape turing machine

 

Answer 2

->Even you do many modifications for a Turing machine the powers will remain same as before modifying it.

some of the modifications of TM are

1.stay option  2.infinite tape  3.offline Turing machine  4.multitape,multihead, multidimensional Turing machine  5.jumping turing machine 7.non erasing turing machine etc....

even you do modifications like this the power of it remains the same.

(By all these statements we can say S1 is false)

->only for PDA the NPDA>DPDA for all other machines their non-determinism is equal to determinism.

Answer: opt B(S2 only)

Answer 3

Only S2 is correct , for S1: multi-tape turing machines are faster not more powerful, every solution given by multi-tape turing machine can be calculated by a single tape turing machine.

Answer 4

Ans:Option C

S1:https://gateoverflow.in/2110/gate2011-8

S2: https://gateoverflow.in/1439/gate2013-17

Comments

How S1 is true? in the linked shared by you it is written that:

 "In turing machine if we increase the number of tape then also language accepted by that machine is same as single tape turing machine.so there expressing power is same."

So how it makes S1 true? I think correct answer should be option B.