Hints for Homework 13
---------------------

(1) You only need to turn in a sentence or two of justification.
However, you may want to sketch a longer proof in your head,
to make sure your short explanation is really right.

Look at the examples in lecture 23.   

==========================================================================

(2 and 3) Look at the sample reductions in lectures 22-23 (first half of
Sipser section 5.1).  Your solutions will be very, very similar to
some of the examples from lecture.  So you need to identify an example
that looks similar, copy it, and make minor modifications.

That makes these problems sound easy.   They aren't, because you probably
find reductions confusing at this stage.   But writing reductions from
scratch would be harder.

Also see the "reduction help" page linked next to lecture 22.

==========================================================================

(4) Enumerators should be familiar from HW 13.  Remember that it's ok for
an enumerator to print a value twice.  And it's legit for an enumerator to
have multiple working tapes (only one output tape).

Your answer should be short.  Less than a page.  Maybe only a paragraph for
each part.  Don't get into details of the input and output formats.   

You can assume that our TM simulator U_TM can do things like single-stepping
a simulation or stopping when the simulation does some easily-observed thing.

(a) is basically not hard.  Looking at Sipser Theorem 4.22 might be helpful.

(b) The two enumerators might not be in sync.   Perhaps language L is much
easier to enumerate than L'.   You need to explain how to synchronize them,
so their outputs can be combined in the right order.


==========================================================================

(5) The answer is simple.  However, unlike problems (2) and (3), you
need a clear understanding of reductions because you have to write more
of it from scratch.   Don't attack this problem until you are on top
of the two easier reductions.

Try writing an outline of the reduction proof.   Get clear on what program
components you are given, and what function you have to construct.   The
top-level outline will be similar to the examples from lecture.   It's
mostly the code for the auxiliary TM (M_w in the lecture examples)
that will be different.   

If you want some motivation for this proof, L is a version of the
Halting problem.  So we could have used L as our original "seed"
language for the diagonalization proof of undecidability.  Then we'd
have to go on and prove A_TM undecidable, by reducing L to it.