CSE 417 Assignment #1
Autumn 2002

Due: Friday, October 18, 2002.

1. In the original halting problem both the program and its input were given as inputs. This problem will show that we only need to give one of them.

   1. The "blank tape" halting problem is defined as follows:

      Given:	The code of a Turing machine, <Q>
      Output:	1 if Q halts when given the empty string, "", as input.
      	0 if Q runs forever on input the empty string.

      Show that the "blank tape" halting problem is undecidable.

   2. For any fixed Turing machine M we can define the M-halting problem as follows:
      

      Given:	A character string y
      Output:	1 if M halts on input y.
      	0 if M runs forever on input y.

      There are lots of different M-halting problems, an infinite number in fact, one for each possible Turing machine M (or program) we could design. Some of them are really easy to solve. However, show that there is a Turing machine M such that the M-halting problem is undecidable. Justify your answer.
      (Hint: consider of the universal Turing machine.)

2. Compare the following pairs of functions f and g. For each of the following write
   (i) whether f(n) is O(g(n)), (ii) whether f(n) is Ω(g(n)), (iii) whether f(n) is Θ(g(n)).

   	f(n)	g(n)
   a.	100n+log2 n	n+(log2 n)2
   b.	log2 n	log2 (n2)
   c.	n2/log2 n	n(log2 n)2
   d.	n1/2	(log2 n)100
   e.	2n	3n

3. The ALGORITHM Design Manual, page 26, Problem 1-9

4. The ALGORITHM Design Manual, page 50, Problem 2-5