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. |
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. |
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. |
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. |
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. | n^{2} |
B. | n |
C. | n^{3} |
D. | n^{n} |
Option: B Explanation :
Recuesivelt applying the relation, we get Click on Discuss to view users comments. |