Lecture 20 (Undecidability), 11/13/17

Concepts, definitions (in italics):

         Review: reduction from D to ATM

         ETM, REGTM are not decidable (reductions from ATM)

         EQTM is not decidable (reduction from ETM)

         Table-based approach to checking correctness of reductions

         All interesting properties of TMs are not decidable (will be defined and proved next time)

         Theorem 1: A language is decidable iff its complement is decidable

Reading:

         Chapter 4.2, p. 207 to end

         Chapter 5.1, introduction through theorem 5.4

Skills:

Notes:

         Here is the reduction  from ATM to ETM:

 

A-TM-DECIDER(M1,w)

{

1. construct encoding of the following machine M2:

M2(x)

{

if x w, reject;

otherwise, run M1 on w and accept only if M1 accepts w.

}

2. return ! E-TM-DECIDER(M2); // note that the output is negated

}


Here is the table for proving that the reduction above is correct:

 

A-TM-DECIDER
(
M1, w) should

 

M2's behavior

L(M2)

E-TM-DECIDER (M2)

THE REDUCTION WILL

M1 accepts w

ACCEPT

 

Reject all x ≠ w,
Accept w

{w}

REJECT

ACCEPT

M1 does not accept w

REJECT

 

Reject all x ≠w,
Do not accept w

empty

ACCEPT

REJECT

 

         Here is the reduction  from ATM to REGTM:

A-TM-DECIDER(M1,w)

{

1. construct a description of the following machine M2:

M2(x)

{

if x is of the form 0n1n, accept;

otherwise, run M1 on w and accept only if M1 accepts w.

}

2. return REG-TM-DECIDER(M2);

}

 

Here is the table for proving that the reduction above is correct

 

A-TM-DECIDER
(M, w) should

M2's behavior

L(M2)

REG-TM-DECIDER
(M2)

THE REDUCTION WILL

M1 accepts
w

ACCEPT

Accept strings of the form 0n1n ; accepts all others too

∑*

ACCEPT

ACCEPT

M1 does not accept w

REJECT

Accepts strings of the form 0n1n;
Does not accept others

0n1n
(not regular)

REJECT

REJECT

 

         Here is the reduction  from ETM to EQTM:

ETM-DECIDER(M1)

{

1. construct encoding of the following machine M2:

M2(x)

{

reject(x);

}

2. return EQ-TM-DECIDER(M1, M2);     

}

 

Here is the table for proving that the reduction above is correct:

 

E-TM-DECIDER
(
M1) should

L(M2)

EQ-TM-DECIDER (M1, M2)

THE REDUCTION WILL

L(M1) is empty

ACCEPT

empty

ACCEPT

ACCEPT

L(M1) is not empty

REJECT

empty

REJECT

REJECT