===========================================================================
CSC 363H                  Tutorial Exercises # 5                  Spring 2007
===========================================================================

 -  Show that it is undecidable to determine whether or not a TM M halts
    when started on a blank input tape.

 -  Show that A_TM <=m (E_TM)^c (the complement of E_TM) but
    A_TM does not <=m E_TM.

 -  5.4 in P211

 -  show that <= m is a transtive relation.