The Gateway to Computer Science Excellence

NIELIT 2017 DEC Scientist B - Section B: 37

0 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

NIELIT 2017 Scientist B - Section B-37

in Theory of Computation by Veteran
recategorized by | 17 views

2 Answers

0 votes
by Active
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 there expressing power is same."

So how it makes S1 true? I think correct answer should be option B.
0 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


by Active

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,222 questions
59,850 answers
118,095 users