Click to Get updated NTA UGC NET CS Test Series           Study Material for UGC NET Computer Science- 2019

# Theory Of Computation MCQ - Recursively enumerable sets and Turning machines

16:

The statement, “A TM can’t solve halting problem” is

 A. true B. false C. still an open question D. all of these Answer Report Discuss Option: A Explanation : Click on Discuss to view users comments. Write your comments here:
17:

If there exists a TM which when applied to any problem in the class, terminates, if correct answer is yes and may or may not terminate otherwise is called

 A. stable B. unsolvable C. partially solvable D. unstable Answer Report Discuss Option: C Explanation : Click on Discuss to view users comments. Write your comments here:
18:

Given a Turing machine T and a step-counting function f, is the language accepted by T in Time(f) ? This decision problem is

 A. solvable B. unsolvable C. uncertain D. none of these Answer Report Discuss Option: B Explanation : Click on Discuss to view users comments. Write your comments here:
19:

A total recursive function is a

 A. partial recursive function B. premitive recursive function C. both (a) and (b) D. none of these Answer Report Discuss Option: D Explanation : Click on Discuss to view users comments. Write your comments here:
20:

The running time T (n), where 'n' is input size of a recursive algorithm, is given as
T (n) = c + T (n - 1), if n > 1
= d, if n ≤ 1
The order of the algorithm is

 A. n2 B. n C. n3 D. nn Answer Report Discuss Option: B Explanation : Recuesivelt applying the relation, we get T( n + 1 ) = C ( n - 1 ) + T (1)                  = C ( n - 1 ) + d Hence order is n. Click on Discuss to view users comments. Write your comments here: X