ISRO2011-79

Question

A problem whose language is recursion is called?

• A. Unified problem
• B. Boolean function
• C. Recursive problem
• D. Decidable

Answer 1

A problem whose language is recursion is called Decidable (Recursive Language)

Answer 2

It will call Recursive Problems. Recursive problem is decidable. Hence it is decidable

Comments

Recursive problem

Decidable

Both are the options then what to do?

Answer 3

ans is (d)

Decidable: If the problem and its complement are both semidecidable (or recursively enumerable), then the problem is decidable (recursive).

Undecidable: If the problem is semidecidable and its complement is not semidecidable (that is, is not recursively enumerable).

Answer 4

Since the program has recursion it uses an algorithm so by Church Turing thesis its a recursivelanguage  and decidable