====================================================================
                          Exercise 2   (due Oct 15)                              
=====================================================================
 
1. If L1 is recognizable and L2 decidable, can you say that L1 intersection 
with L2 decidable (prove or give a counter example)? Is it recognizable 
(prove or give a counter example)? 

2. Let L be an infinite language in {0,1,2,3}*. Is L necessarily countable?

3. Let HaltSomething = {<M> | M halts on some inputs}. Show that 
HaltSomething is recognizable. (bonus*) Show that it is not decidable by showing that if it were then
HALT_TM would have been decidable as well.
* This is bonus only since at this point you only saw one exmple of such an argument. It is going to 
be the bread and butter of the next two weeks.