Sample question for T1 (CSC363) 
               ====================================

1. Give an implementation level description of a TM that decides the lnguage 
L = {(a#b) : a in 1*, b in {0,1}* and b is the 'a'th word in the lecicographic 
order in {0,1})*}, where 'a' is read as a unary number, so we think of 1 as 1, 11 as 2, 111 as 3, etc.

Recall, the lexicographic order looks like 
epsilon (empty word),0,1,00,01,10,11,000,001,010,011,100,101,110...
so (epsilon,epsilon), (111,01), (111111,000) are in L and
(11,0), (111,00) are not.

2. - Is the intersection of two recognizable languages recognizable? prove 
     or disprove (give counter example).
   - Is the intersection of an unrecognizble and a decidable language 
     recognizable? prove or disprove.
   - If L1 is contained in a decidable language L, is L1 decidable? 
     recognizable? prove/disprove.

3. Give an example of two TM, M1 and M2, that accept the same language. M1 
 should be a decider and M2 not.

4. Show that the set of languages the are not recognizable is uncountable.

5. Consider the language L of strings of length 1000000 that belong to A_TM. Is
L decidable?