retagged by
3,028 views
1 votes
1 votes

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.

  1. $S1$
  2. $S2$
  3. Both $S1$ and $S2$
  4. None of the options
retagged by

4 Answers

2 votes
2 votes

$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

 

1 votes
1 votes
->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)
1 votes
1 votes
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.
0 votes
0 votes
Answer:

Related questions

2 votes
2 votes
2 answers
1
admin asked Mar 30, 2020
1,615 views
Which machine is equally powerful in both deterministic and non-deterministic form?Push Down AutomataTuring machineLinear Bounded AutomataNone of the options
0 votes
0 votes
6 answers
2
admin asked Mar 30, 2020
2,409 views
According to the given language, which among the following expressions does it correspond to ?Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.$(0+1+0+1+0...
1 votes
1 votes
3 answers
4