===========================================================================
CSC 363                     Homework Exercise 4                 Winter 2008
===========================================================================

Due: 29 Feb in tutorial
Worth: 3%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  Prove that for all decidable languages L, L <=m {00,11} (over alphabet
   \Sigma = {0,1}).
   Hint:  Take the time to write down precisely what it means for L to be
   decidable, and what it means to show "L <=m {00,11}".

2.  Prove or disprove that E_TM <=m A_TM.

3.  Prove that REGULAR_TM is unrecognizable, by making appropriate use of
   <=m.