Classical

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

 
 

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

 
 

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

 
 

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

 
 

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

 
 

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:







Suggest an improvement