Lecture 19 (Reductions), 11/08/17

Concepts, definitions (in italics):

·         Theorem: ATM is not decidable

·         This proof proceeds as follows:

1.       Show that D = {M: M is a Turing machine which rejects M} is undecidable

2.       Show a reduction from D to ATM

3.       Conclude that ATM is not decidable

Reading:

Skills:

Notes:

1) syntax check, REJECT if fails
2) check if there is a path in D from the intial state to any of the final states
3) if yes, then REJECT else ACCEPT

1) syntax check, REJECT if fails
2) D = NFA_DFA_converter (N)
3) Return E
DFA-decider (D)

1) syntax check, REJECT if fails
2) N = RE_NFA_converter(R)
3) Return E
NFA-decider(N)

·         Algorithm for ECFG:

1) (Init) For every rule with no variables on RHS, mark variable on LHS.
2) (Loop) For every rule with no unmarked variables on RHS, mark variable on LHS.
3) Repeat step 2 until we cannot mark any more variables.
4) If start variable is marked, REJECT; else ACCEPT.

1) syntax check, REJECT if fails
2) D3 = construct the description of DFA accepting L(D1) – L(D2)
3) D4 = construct the description of DFA accepting L(D2) – L(D1)
4) Run E
DFA decider on D3, then on D4
5) If both are ACCEPTED (i.e. they both have empty languages), then ACCEPT; else REJECT

·         Proof of undecidability of ATM:

1.      Let D be the following language: D = {M: M is a Turing machine which rejects M}

2.      Assume D is decidable

3.      Since D is decidable, there must exist a TM MD deciding D

4.      What should it return when given MD as input? It must either accept or reject all inputs, including MD  

5.      But both ACCEPT and REJECT give a contradiction.

6.      Therefore, our assumption was wrong and D is not decidable

7.      But D is reducible to ATM:

D- DECIDER(M)
{
         BOOL b = A-TM-DECIDER(M, M)
         return !b
}

8.   Therefore, the algorithm ATM is not decidable, either.