1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
a) PSPACE
b) NPSPACE
c) EXPSPACE
d) None of the mentioned
View Answer
Answer: a
Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.
Explanation: PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.
a) Vertex Cover problems
b) Knapsack
c) 0-1 integer programming
d) None of the mentioned
View Answer
Answer: d
Explanation: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.
Explanation: There exists a set of 21 problems that are NP-complete and the set is called Karp’s 21 NP-complete problems.
3. A generalization of P class can be:
a) PTIME
b) DTIME
c) NP
d) None of the mentioned
View Answer
Answer: c
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.
Explanation: P is a specific case of NP class, which is the class of decidable problems decidable by a non deterministic turing machine that runs in polynomial time.
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: d
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.
a) Finite State Automaton
b) Universal Turing Machine
c) Counter machines
d) All of the mentioned
View Answer
Answer: b
Explanation: The computational aspect of any possible real world computer can be simulated using an Universal Turing Machine so can be any turing machine.
Explanation: The computational aspect of any possible real world computer can be simulated using an Universal Turing Machine so can be any turing machine.
Statement: Using a two track tape, we can use a semi infinite tape to simulate an infinte tape.
a) true
b) false
View Answer
Answer: true
Explanation: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.
Explanation: A TM with a semi-infinite tape means that there are no cells to the left of the initial head position. A TM with a semi infinite tape simulates a TM with an infinite tape by using a two-track tape.
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.
d) None of the mentioned
View Answer
Answer: d
Explanation: All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.
Explanation: All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.
a) Yes
b) No
View Answer
Answer: b
Explanation: One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.
Explanation: One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned
View Answer
Answer: d
Explanation: In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.
Explanation: In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.
10. Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing machine
e) More than two options are incorrect
View Answer
Answer: d
Explanation: In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.
Explanation: In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.
Statement: In theory of computation, abstract machines are often used in ___________ regarding computability or to analyze the complexity of an algorithm.
a) thought experiments
b) principle
c) hypothesis
d) all of the mentioned
View Answer
Answer: d
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
Explanation: A thought experiment considers some hypothesis, theory or principle for the purpose of thinking through its consequences.
Statement: Given a turing machine, an input for the machine, and a number T(unary), does that machine halt on that input within the first T-steps?
The given problem is P-complete.
a) true
b) false
View Answer
Answer: a
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
Explanation: If we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so every other problem in P.
a) writes the symbol
b) moves the tape one cell left/right
c) proceeds with next instruction or halts
d) none of the mentioned
View Answer
Answer: d
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
Explanation: After the read head reads the symbol from the input tape, it performs the following functions:
a) writes a symbol(some model allow symbol erasure/no writing)
b) moves the tape left or right (some models allows no motion)
c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.
a) polynomial time
b) non-polynomial time
c) cannot be calculated
d) none of the mentioned
View Answer
Answer: a
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.
Explanation: The value of such constants can be calculated using algorithms which have time complexity in terms if O(nk) i.e polynomial time.
For a given Turing Machine M,
a) does M halt on an empty input tape
b) does M halt for anly inputs at all?
c) is L(M) regular? Context free? Turing decidable?
d) all of the mentioned
View Answer
Answer: d
Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
Explanation: All of the following mentioned are immediate results of Rice’s theorem and thus, undecidable.
