adplus-dvertising
frame-decoration

Question

The space complexity of a turing machine is undefined if:

a.

It is a multitape turing machine

b.

If no string of length n causes T to use infinite number of tape squares

c.

If some input of length n causes T to loop forever

d.

None of the mentioned

Answer: (c).If some input of length n causes T to loop forever

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. The space complexity of a turing machine is undefined if:

Similar Questions

Discover Related MCQs

Q. Which among the following is smallest for n=50

Q. Which of the following can be referred to as applications of Randomized algorithm?

Q. Which of the following can be solved in computer science?

Q. For the given algorithm, find the probability of finding after k iterations:
find_a(array A, n, k)

begin

i=0

repeat

Randomly select one element out of n elements

i=i+1

until i=k or a is found

end

Q. State true or false:
Statement: A turing machine has the capability of using randomly ‘generated’ numbers.

Q. Unix sort command uses _________ as its sorting technique.

Q. Prisonner’s dilemma can be related to the following:

Q. Which of the following algorithms are probably correct as well as fast?

Q. Which of the following are probalistic algorithms?

Q. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.

Q. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.

Q. Which of the following PSPACE can be characterized into?

Q. Complement of all the problems in PSPACE is ________

Q. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.

Q. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.
State true or false:

Q. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?

Q. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE

Q. The class PSPACE is closed under the following operations:

Q. Savitch theorem relates to which of the following:

Q. PSPACE is strictly the super set of: