adplus-dvertising
frame-decoration

Question

Diagonalization can be useful in:

a.

To find a non recursively ennumerable language

b.

To prove undecidablility of haltig problem

c.

both a and b

d.

None of the mentioned

Answer: (c).both a and b

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Diagonalization can be useful in:

Similar Questions

Discover Related MCQs

Q. Which of the following are undecidable problems?

Q. Which of the following are incorrect options?

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

Q. Which of the following are decidable problems?

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

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

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

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

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.

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

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.

Q. Which aong the following are undecidable theories?

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

Rec-DFA is ___________

Q. Which among the following are semi decidable?

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

Q. Decidable can be taken as a synonym to:

Q. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:

Q. An algorithm is called efficient if it runs in ____________ time on a serial computer.

Q. A problem is called __________ if its has an efficient algorithm for itself.

Q. A formal language is recursive if :