===========================================================================
CSC 363H                Lecture Summary for Week  5             Summer 2007
===========================================================================

--------------------------
An Unrecognizable Language
--------------------------

Last time, we proved using a counting argument that there are languages not
recognizable by any TM, but we didn't see any explicit example
of such a language. We also saw that A_TM is an example of an undecidable
language. Here is an example of a concrete unrecognizable language.

Lemma:
    If L and L^c are both recognizable, then L is decidable.

Proof idea:
    To build a decider TM for L, use the fact that every string w
    is either in L or in L^c. Take the two not-necessarily-decider
    TMs that accept L and L^c and run them in parallel to figure
    out if w is in L or in L^c.

A_TM = { <M,w> : M is a TM and M accepts w }

Formally, (A_TM)^c = { <M,w> : M is a TM and M does not accept w } UNION
                     { x : x is not the encoding of a pair (TM,string) }

Since deciding whether or not a string x encodes a pair (TM,string) is
an easy task for an alogrithm, it is ok to ignore the second set.
For the purposes of this course, you may assume:

(A_TM)^c = { <M,w> : M is a TM and M does not accept w }


Claim:
    (A_TM)^c is not recognizable.

Proof:
    By contradiction. Assume (A_TM)^c is recognizable.
    We know from lecture 3 that A_TM is recognizable.
    Thus, by Lemma above, A_TM is decidable.
    We proved last time that this is not the case, therefore
    (A_TM)^c is not recognizable.

------------
Reducibility
------------

We would like to show that other languages are hard (undecidable,
not recognizable) without using a diagonalization argument.
For this reason, we introduce the idea of reductions.

Definition:
    Language A is _reducible_ to language B iff the following holds:
    IF we are given access to a solver (TM) for B,
    THEN we can construct a solver (TM) for A.

Note: This says nothing about how difficult it is to solve
membership in A or in B separately. Only that A can be solved
if we are provided with a solver for B.

Goal:
    If we know that A cannot be solved and we manage to show that
    A is reducible to B, then B cannot be solved either
    (otherwise, a solver for B would give us a solver A.)

Example: A_TM is reducible to HALT_TM.
HALT_TM = { <M,w> | M is a TM that halts on input w } is undecidable.
Assume there exists a decider TM R for HALT_TM.
Consider the following TM S:
S: on input <M,w>
   run R on <M,w>
   if R rejects, S REJECTS
   run M on w
   if M accepts, S ACCEPTS
   if M rejects, S REJECTS
Then, S accepts <M,w> iff M accepts w. So S is a decider for A_TM!
This is a contradiction because A_TM is undecidable.
Thus, the assumption that R exists is false. Hence, HALT_TM is undecidable.


Each of the following language is undecidable:

 -  E_TM = { <M> | M is a TM such that L(M) = {} }:
    Assume R decides E_TM, and construct S as follows:
    S = "On input <M,w>:
     -  Compute <Q>, the description of the following TM:
        Q = "On input x:
         -  Ignore x and simulate M on w;
            accept if M accepts; reject if M rejects."
     -  Run R on input <Q> and do the opposite
        (if R accepts, reject; if R rejects, accept)."
    Then S accepts <M,w> iff R rejects <Q> iff L(Q) != {} iff L(Q) = S^*
    (by construction, either Q accepts all strings or Q accepts no string)
    iff M accepts w.  Moreover, S always halts because R always halts.
    Hence, S decides A_TM, a contradiction!

 -  EQ_TM = { <M_1,M_2> | M_1 and M_2 are TMs such that L(M_1) = L(M_2) }:
    Assume R decides EQ_TM and construct S as follows:
    S = "On input <M>:
     -  Compute <M'>, the description of the following TM:
        M' = "On input x: reject."
     -  Run R on input <M,M'> and do the same."
    Then S decides E_TM, a contradiction.

 -  REGULAR_TM = { <M> | M is a TM such that L(M) is regular }:
    Exercise: try this one (use A_TM as the other language).
    The solution is in the textbook.

--------------------
Mapping Reducibility
--------------------

General structure of proof of undecidability of some language A:

    Assume R decides A.
    Construct S to decide B (some undecidable language):
    S = "On input x:
     -  Compute y such that y in A iff x in B.
     -  Run R on y and do the same."
    Then, S decides B because y in A iff x in B.

Since structure always the same, concentrate on "core" part: construction
of y from x such that y in A iff x in B.

Definition 5.20: "mapping reducibility"; "reduction".

Example 5.26: E_TM <=m EQ_TM.
    Given <M>, construct <M1,M2> as follows:
        M1 = M, M2 = fixed TM that rejects all inputs
    Clearly, this is computable (copy string, append constant string).
    Moreover, since L(M1) = L(M) and L(M2) = {}, <M> in E_TM iff L(M) = {}
    iff L(M1) = L(M2) iff <M1,M2> in EQ_TM.

Theorem 5.22:
    If A <=m B and B is decidable, then A is decidable.
Proof:  (see textbook -- done in lecture)

Theorem 5.28:
    If A <=m B and B is recognizable, then A is recognizable.
Proof:  (see textbook -- done in lecture)

Corollary 5.23:
    If A <=m B and A is undecidable, then B is undecidable.

Corollary 5.29:
    If A <=m B and A is unrecognizable, then B is unrecognizable.

Properties:

 -  A <=m B iff A^C <=m B^C.  (Straight from definition, since statement
    "w in A iff f(w) in B" is equivalent to "w not in A iff f(w) not in B"
    and "w not in A" = "w in A^C".)

 -  If A <=m B and B <=m C, then A <=m C.  (Easy exercise, based on
    function composition: if f,g computable, then g(f()) computable.)

Examples:

 -  A_TM <=m E_TM^C but A_TM not <=m E_TM (in tutorial).

 -  A_TM <=m HALT_TM: different from "informal" reduction used to prove
    HALT_TM undecidable.
    Given <M,w>, construct <M',w'> such that M accepts w (<M,w> in A_TM)
    iff M' halts on w' (<M',w'> in HALT_TM), as follows:
        M' = M except replace all transitions to q_reject with transition
        to state q_new, then add transitions from q_new to q_new for each
        input symbol (q_new is deliberate infinite loop)
        w' = w
    Clearly, this is computable.
    Moreover, if M accepts w, then M' accepts w'; if M rejects w, then M'
    loops on w'; if M loops on w, then M' loops on w', i.e., M accepts w
    iff M' halts on w', as desired.

 -  (A_TM)^c <=m EQ_TM
    We need to define a function f(<M,w>) = <M_1,M_2> satisfying:
    <M,w> in (A_TM)^c iff <M_1,M_2> in EQ_TM, or, equivalently,
    M accepts w iff L(M_1) = L(M_2).
    Consider the following function:
    M_f: on input <M,w>
         let M_1 be the following TM:
             M_1: on x
                  REJECT
         let M_2 be the following TM:
             M_2: on y
                  erase y
                  run M on w
                  if M accepts w, M_2 ACCEPTS
                  if M rejects w, M_2 REJECTS
         output <M_1,M_2>
    Note that L(M_1) = empty as M_1 rejects all strings.
    Since M_2 ignores its input, L(M_2) can be either empty or S^*.
    Notice that L(M_2) = { empty, if M does not accept w
                         { S^*, if M accepts w
    Thus,
    M does not accept w iff L(M_2) = empty iff L(M_1)=L(M_2).
    So, <M,w> in (A_TM)^c iff <M_1,M_2> in EQ_TM, as required.