Which of the following set of computable functions are decidable?(a) The class of computable functions that are constant, and its complement(b) The class of indices for computable functions that are total(c) The class of indices for recursively enumerable sets that are cofinite(d) All of the mentionedI had been asked this question in a national level competition.My doubt stems from Rice’s Theorem, Properties and PCP topic in division Undecidability of Automata Theory

Which of the following set of computable functions are decidable?(a) T

1.	Which of the following set of computable functions are decidable?(a) The class of computable functions that are constant, and its complement(b) The class of indices for computable functions that are total(c) The class of indices for recursively enumerable sets that are cofinite(d) All of the mentionedI had been asked this question in a national level competition.My doubt stems from Rice’s Theorem, Properties and PCP topic in division Undecidability of Automata Theory
Answer» The correct choice is (d) All of the mentioned To elaborate: ACCORDING to Rice’s THEOREM, if there exists atleast ONE computable FUNCTION in a particular class C of computable functions and another computable function not in C then the problem DECIDING whether a particular program computes a function in C is undecidable.

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