Homework 1Due Feb 6

COURSE WEBSITE: www.cs.umd.edu/ gasarch/858/858.html

(there is a tilde before the ``g'' in ``gasarch'')

READING: Download and read the course notes. Read the whole thing- it only covers the first few lectures.

1. (5 points) Write your name clearly. Staple the HW so its not loose pages. Where and when will the midterm be? Where and when will the final be?

2. (35 points) For each of the following problems write them with quantifiers and a computable predicate. Try to minimize the number of alternations of quantifiers. Let $M_0, M_1, \ldots$ be a standard list of Turing machines. Let $W_e$ be the set of $x$ such that $M_e(x)\cvg$.
   1. $\{ e \st \vert W_e\vert\ge 10 \}$
   2. $\{ e \st \vert W_e\vert\le 10 \}$
   3. $\{ e \st \vert W_e\vert= 10 \}$
   4. $\{ e \st W_e\hbox{ is decidable } \}$
   5. $\{ e \st W_e = K \}$
   6. $\{ e \st \hbox{ $W_e$ and $K$ differ on AT MOST 10 numbers} \}$
   7. $\{ e \st \hbox{$W_e$ and $K$ differ on A FINITE number of numbers} \}$

3. (35 points) Show that each problem in part 1 is undecidable. (Do not use Rice's theorem. If you don't know what that is, thats okay since I'm not letting you use it anyway.)

4. (25 points) Let $T(n)$ be a computable function (we think of it as being quite large). Show that there is a set $A$ such that $A\notin DTIME(T(n))$ in the following strong sense:

   For all $e$, if $M_e$ is a Turing Machine that, on inputs of length $n$, always takes $\le T(n)$ steps, then $M_e$ and $A$ differ INFINITLY OFTEN.

5. (EXTRA CREDIT) Let $T(n)$ be a computable function (we think of it as being quite large). Show that there is a set $A$ such that $A\notin DTIME(T(n))$ in the following strong sense:

   For all $e$, if $M_e$ is a Turing Machine that, on inputs of length $n$, always takes $\le T(n)$ steps, then $M_e$ and $A$ differ ON ALL BUT A FINITE NUMBER OF INPUTS.