17 views

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

recategorized | 17 views

by Active
+1
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.
$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.