Sample question for T2 (CSC363) 
               ====================================

1. If A is recognizable and B unrecgonizable, is it always true that A<=m B?
Prove or give a counter example.

2. Let FIN = {<M> : M is a TM such that |L(M)| is finite}
Show that FIN is unrecognizable. Does Rice's thm shows anything about FIN?

3. Prove that the class of languages in TIME(n^2) is a subset of the class 
TIME(n^3).

4. Let L be a language that is decided by a 5-tape deterministic TM in 
time O(n^3). Show that L is in TIME(n^6).


MORE (added Nov 10):
5. Show that L = {<M,w1,w2,w3> : L(M) = {w1,w2,w3}  } is unrecognizable.

6. Let L1 and L2 be lnguages in P. is L1 union L2 necessarily in P?

7. Show that CUBIC = {<n,n^3> : n is natural number} is in P.

8. Show that {<m,n> : m,n are natural numbers and m>n} is in P. 

(For both 7 and 8 you may assume that the encoding of a natural number is 
in decimal or binary, whichever is more convenient.)