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 :


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 :


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 :


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 :


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.




Suggest an improvement