Question

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 mentioned

I 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 1

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.