CSE396                Problem Set 10 Answer Key               Spring 2010
-------------------------------------------------------------------------


(1) Given a CFG G and a string x, decide whether G generates some string y
    such that x is a substring of y.

Step 1: Define R = \Sigma^* x \Sigma^*.  This is a regular expression, so
        we can build a DFA M_R such that L(M_R) = R.
Step 2: Hence we can compute a CFG G_R such that L(G_R) = L(G) intersect R.
        (The details for this are longwinded: convert G into a PDA P,
        do Cartesian product on P and the DFA M_R---which is OK for
        intersection even though P can be nondeterministic---to obtain a
        PDA P' for L(G) n R, and finally convert P' back into a CFG G_R.
        You were not asked to give these details---just appreciate that the
        construction of G_R can be carried out by a computational process.)
Step 3: Feed G_R into the text's decision procedure for E_{CFG}.  If the
        latter says "yes" L(G_R) = \emptyset, you say "no"---G does not
        generate any such y.  If it says "no", you flip the answer to "yes".

This works because R contains all and only the strings y that have x as a
substring, and so L(G_R) is empty iff G generates no such string y.
Since all three individual steps always halt, it is a decision procedure
that correctly decides the problem.



(2) Given any Turing machine M, define f(M) to be a coffeemaker CM with the
    following code in its ROM chip:
    1. Run M on input M, using the Java Turing Kit also on the ROM chip.
       (Maybe CM's chip only needs to store an URL where it can find M,
       which then could be much bigger than the chip, and can then access
       the Turing Kit "on the cloud" to run it.)
    2. When (and only when) M has accepted M, brew coffee.

If we had a decision procedure R that could decide whether /all/ coffeemakers
would brew coffee when turned on, then R ipso-facto could decide this for
coffeemakers CM programmed as above.  However, one could then design a
decision procedure S for the A_TM problem (or rather, the specific subcase
"x = M" by which it was shown undecidable since it's the complement of
the language D_TM) like so:

(a) Given M, build the coffeemaker CM by programming the above into its ROM.
(b) Feed CM to the decision procedure R, and give the same answer.

However, S cannot exist, since (the complement of) D_TM is undecidable.
This means R cannot exist, so the brew-coffee problem is undecidable too.

This sounds jocular, but haven't you wondered whether your laptop would
ever finish installing the latest suite of updates from Windows?  Or
begin a websearch that might never halt?  Most to the point, the basic
pattern of this reduction is used for many important technical results:


2(a) Given a Java program P and a line l, does there exist x so that P(x)
     executes l?

To show this is undecidable, consider Java programs P_M of the special form:

1. Input: any x (given on the stream stdin = System.in, say)
2. Load M, and call Turing Kit to run M on its own (binary) code M.
3. If and when process 2. accepts and exits, execute the line
   l: System.exit(0);

If we had a decision procedure R that could decide the problem for all Java
programs, then ipso-facto it could decide it for programs P_M of this special
form, which is conditioned on a given Turing machine M.
But then R would give rise to a decision procedure S for (the complement of)
D_TM, which cannot exist.  So R cannot exist.

(Note that my choice of the labeled statement l to be "System.exit(0)"
makes the original (a) problem identify with the Acceptance Problem For Java,
or more precisely, with "NE_Java", the "Nonemptiness Problem For Java".)


2(b) Now consider P'_M of the same form as P_M, but with this last step:

3. If and when process 2. accepts and exits, execute the statement
   l: [some line that throws an ArrayIndexOutOfBoundsException].

Since the Turing Kit never throws that exception, the only way it can
occur is for line l to be executed, which happens if-and-only-if the
TM M (which is hard-coded into P'_M) accepts its own code.  Hence a
decision procedure for 2(b) would ipso-facto become one for D_TM, but
"there is no such animal".  Hence the 2(b) problem is undecidable.

(As I've anticipated with things I've said in lecture, it may seem "dumb"
to try and analyze exceptions thrown by ridiculous programs like P'_M,
but the formal impossibility for P'_M in-practice is a tip-of-the-iceberg
effect.  The effect is that analyzing the submerged mass of "real" Java
programs for possible thrown exceptions is so hard in practice, there's
no 'silver bullet" for it.  OK that's a mixed metaphor applied to an
iceberg, but what am I supposed to say, it's like global warming?)


(3) Given a 1-tape TM M, is there an input x such that M(x) writes a B
    (over a non-blank symbol)?  Define the language of this problem by:
    L = {M: M is a 1-tape TM, and for some x, M(x) writes a blank B}.

Now given any one-tape TM T, we can convert T into an equivalent M in a
sneaky manner.  Add a new work-alphabet symbol '%'.  Convert the body
of T by changing every write of the actual blank B into a write of '%',
and for every arc that reads a B, /add/ an option to read '%' and do the same.
(Don't delete the arc reading B, because you might need it for tape cells
outside the input x, which will hold B not '%'.)  Then for any input x,
M(x) simulates T and accepts x iff T does.  Finally code M in the "nice form"
with a single accepting state q_acc, and then add two more instructions:

(q_acc,any,%,S,q_new), (q_new,%,B,S,q_new).

Thwe new state q_new can become the new accepting state if you like, but
that isn't the point---the point is that q_new is the only place in the code
of M where M would write B over a non-blank symbol (namely, '%'), and it
comes exactly when T has accepted some input x.  So a decision procedure
for L---since it would ipso-facto handle 'rogue" cases like M---would
become a decision procedure for E_TM, but this was shown undecidable in classs.