Q. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.
By Markov’s inequality, the chance that it will answer before we stop is:

View solution

Q. State true or false:
Statement: ZPP is closed under complement function.

View solution

Q. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?

View solution

Q. Diagonalization can be useful in:

View solution

Q. Which of the following are undecidable problems?

View solution

Q. Which of the following are incorrect options?

View solution

Q. If a problem has an algorithm to answer it, we call it _________

View solution

Q. Which of the following are decidable problems?

View solution

Q. Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}

View solution

Q. Statement: If L id R.E., L^c needs to be R.E. Is it correct?

View solution

Q. Which of the following is true for The Halting problem?

View solution

Q. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.

View solution

Q. With reference to enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.

View solution

Q. The decision problem is the function from string to ______________

View solution

Q. A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.

View solution

Q. Which aong the following are undecidable theories?

View solution

Q. Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:

Rec-DFA is ___________

View solution

Q. Which among the following are semi decidable?

View solution

Q. The language accepted by a turing machine is called ____________

View solution

Q. Decidable can be taken as a synonym to:

View solution