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:(a) Decidable(b) Undecidable(c) Computable(d) None of the mentionedI have been asked this question in a national level competition.This question is from The Universal Language-Undecidability in division Undecidability of Automata Theory

The problems which have no algorithm, regardless of whether or not the

1.	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:(a) Decidable(b) Undecidable(c) Computable(d) None of the mentionedI have been asked this question in a national level competition.This question is from The Universal Language-Undecidability in division Undecidability of Automata Theory
Answer» CORRECT ANSWER is (b) Undecidable For explanation: The problems that can be SOLVED by a turing machine can divided into two classes: a) Those that have an algorithm b) Intractable problems: Those that are only solved by a turing machine that may RUN forever on inputs they do not accept.

Discussion

No Comment Found

Related InterviewSolutions

The class of recursive language is known as:(a) R(b) RC(c) RL(d) All of the mentionedThis question was posed to me in a national level competition.This question is from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
Decidable can be taken as a synonym to:(a) recursive(b) non recursive(c) recognizable(d) none of the mentionedThe question was asked in a job interview.I'd like to ask this question from The Universal Language-Undecidability topic in section Undecidability of Automata Theory
The language accepted by a turing machine is called ____________(a) Recursive Ennumerable(b) Recursive(c) Both (a) and (b)(d) None of the mentionedThe question was posed to me in an interview for job.Question is taken from The Universal Language-Undecidability topic in division Undecidability of Automata Theory
Which among the following are semi decidable?(a) Empty-DFA(b) Rec-NFA(c) Infinite-DFA(d) All of the mentionedI got this question in an internship interview.I would like to ask this question from The Universal Language-Undecidability topic in chapter Undecidability of Automata Theory
Which of the following technique is used to find whether a natural language isnt recursive ennumerable?(a) Diagonalization(b) Recursive Induction(c) Both (a) and (b)(d) None of the mentionedThe question was asked during an interview for a job.This intriguing question originated from The Diagonalization Languages topic in chapter Undecidability of Automata Theory
Recursive languages are also known as:(a) decidable(b) undecidable(c) sometimes decidable(d) none of the mentionedI have been asked this question by my school teacher while I was bunking the class.This question is from The Universal Language-Undecidability in section Undecidability of Automata Theory
Which of the following are incorrect options?(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 mentionedThis question was addressed to me during an online interview.My question is taken from The Diagonalization Languages in division Undecidability of Automata Theory
A formal language is recursive if :(a) a total turing machine exists(b) a turing machine that halts for every input(c) turing machine rejects if the input does not belong to the language(d) all of the mentionedThe question was asked during an interview for a job.The origin of the question is The Universal Language-Undecidability in chapter Undecidability of Automata Theory
A problem is called __________ if its has an efficient algorithm for itself.(a) tractable(b) intractable(c) computational(d) none of the mentionedI have been asked this question in an interview.This intriguing question comes from The Universal Language-Undecidability topic in portion Undecidability of Automata Theory
If a problem has an algorithm to answer it, we call it _________(a) decidable(b) solved(c) recognizable(d) none of the mentionedThis question was posed to me in homework.My query is from The Diagonalization Languages in section Undecidability of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment