===========================================================================
CSC 363H              Tutorial Exercises for Week  4            Summer 2006
===========================================================================

 -  Exercises 4.6, 4.7 on p.183.
    4.6. Let B be the set of all infinite sequences of {0,1}. Show that B
	is uncountable, using a proof by diagonalization.
    4.7. Let T = {(i,j,k) : i,j,k are natural numbers}. Show that T is
	countable.

 -  Show that there are uncountably many irrational numbers.

 -  Prove that HALT_TM = { <M,w> : M is a TM that halts on input w } is
    undecidable.  (Hint:  Do a proof by contradiction using what you
    already know about A_TM.)