Theory of Computation

Mock benchtest

Part I: Models of Computation

Question 1

Which of the following two assertions about a Turing Machine (TM) is true?

(i) The input alphabet can be the same as the tape alphabet.

(ii) At a given moment, there could be infnitely many symbols from the input alphabet onto the tape.

(A)  The frst only.

(B)  The second only.

(C)  Both of them.

(D)  Neither of them.

Question 2

Consider the complement of the Halting Problem (H), co −H: given a TM M and an input w, is it the case that M doesn’t terminate on input w? Which of the following is true?

(A)  This problem is not semi-decidable.

(B)  This problem is semi-decidable but not decidable.

(C)  This problem is decidable.

(D)  None of them.

Question 3

What can you say about reducibilities between H and co −H?

(A)  H is m-reducible to co −H .

(B)  co −H is m-reducible to H .

(C)  Neither is true.

(D)  Both are true.

The same question but this time with T-reduction, instead of m-reduction.

Question 4

What is the sequence encoded by the Gödel Number 600?

(A)  3, 1, 1.

(B)  2, 0, 1.

(C)  2, 3, 5.

(D)  None of them.

Question 5

Which of the following has a proof?

(A)  Every positive instance of the Halting Problem H .

(B)  Some negative instances of H .

(C)  All negative instances of co −H .

(D)  All of the above.   (E)  None of the above.

Part II: Algorithms and Complexity

Question 6

Let f(n) and g(n) be two positive functions defned on the natural numbers. Suppose there exist constants c > 0 and n0  such that f(n0 ) ≤ cg(n0 ).  Which statement below can we deduce from this?

(A)  f(n) = O(g(n))

(B)  f(n) = Ω(g(n))

(C)  f(n) = Θ(g(n))

(D)  Each of the above can be deduced. (E)  None of the above can be deduced.

Question 7

Let T(n) = 8T()+ n2  (where we interpret  to mean # $). Which statement below is true?

(A) T(n) = Θ(n2 ).

(B) T(n) = Θ(n3 ).

(C) T(n) = Θ(n3 lg n).

(D) T(n) = Θ(n4 ).

(E)  None of the above is true.