Classical

Theory Of Computation MCQ - Recursively enumerable sets and Turning machines

11:  

 Bounded minimalization is a technique for

A.

proving whether a promotive 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

 
 

Option: C

Explanation :


12:  

 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

 
 

Option: B

Explanation :


13:  

Which of the following statement(s) is/are correct?

A.

L = {an bn an | n = 1, 2, 3...} is recursively enumerable

B.

Recursive languages are closed under union

C.

Every recursive is closed under union

D.

All of these

 
 

Option: D

Explanation :


14:  

Universal TM influenced the concept of

A.

stored program computers

B.

interpretative implementation of program­ming language

C.

computability

D.

all of these

 
 

Option: D

Explanation :


15:  

 Number of external states of a UTM should be atleast

A.

1

B.

2

C.

3

D.

4

 
 

Option: B

Explanation :




Suggest an improvement