Theory of Computation (3160704) MCQs

MCQs of Computable Functions

Showing 1 to 10 out of 19 Questions
1 2
1.
Recursive languages are also known as:
(a) Undecidable
(b) Decidable
(c) Sometimes decidable
(d) None of the mentioned
Answer:

Option (b)

2.
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
Answer:

Option (d)

3.
Bounded minimalization is a technique for:
(a) Proving whether a primitive recursive function is turning computable or not
(b) Proving whether a primitive recursive function is a total function or not
(c) Generating primitive recursive functions
(d) Generating partial recursive functions
Answer:

Option (c)

4.
If there exists a language L, for which there exists a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is called
(a) Recursive
(b) Recursively enumerable
(c) NP-HARD
(d) None of these
Answer:

Option (b)

5.
Which of the following problems is solvable?
(a) Determining of a universal Turing machine and some input will halt
(b) Determining of an arbitrary Turing machine is an universal Turing machine
(c) Determining of a universal Turing machine can be written for fewer than k instructions for some k
(d) Writing a universal Turing machine
Answer:

Option (d)

6.
The statement, “A TM can’t solve halting problem” is
(a) True
(b) False
(c) Still an open question
(d) All of these
Answer:

Option (a)

7.
Which of the following statement(s) is/are correct?
(a) L = {anbnan | n = 1, 2, 3...} is recursively enumerable
(b) Recursive languages are closed under union
(c) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine
(d) All of these
Answer:

Option (d)

8.
Which of the following is not primitive recursive but partially recursive?
(a) Bounded function
(b) Carnot function
(c) Ackermann function
(d) Riemann function
Answer:

Option (c)

9.
Set of recursively enumerable language is closed under union
(a) True
(b) False
(c) May be
(d) Can’t say
Answer:

Option (a)

10.
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 mentioned
Answer:

Option (d)

Showing 1 to 10 out of 19 Questions
1 2