Lecture 20 (Undecidability), 11/13/17
Concepts, definitions (in italics):
·
Review:
reduction from D to A_{TM}
·
E_{TM}, REG_{TM} are
not decidable (reductions from A_{TM})
·
EQ_{TM}
is not decidable (reduction from E_{TM})
·
Tablebased
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 A_{TM} to E_{TM}:
ATMDECIDER(M_{1},w)
{
1. construct encoding of the following machine M_{2}:
M_{2}(x)
{
if x
≠ w,
reject;
otherwise,
run M_{1} on w and accept only if M_{1}
accepts w.
}
2. return ! ETMDECIDER(M_{2}); // note that the output is
negated
}
Here is the
table for proving that the reduction above is correct:

ATMDECIDER 

M_{2}'s behavior 
L(M_{2}) 
ETMDECIDER (M_{2}) 
THE REDUCTION WILL 
M_{1} accepts w 
ACCEPT 

Reject all x ≠
w, 
{w} 
REJECT 
ACCEPT 
M_{1} does not accept w 
REJECT 

Reject all x ≠w, 
empty 
ACCEPT 
REJECT 
·
Here
is the reduction from A_{TM} to REG_{TM}:
ATMDECIDER(M_{1},w)
{
1. construct a description of the following machine M_{2}:
M_{2}(x)
{
if x
is of the form 0^{n}1^{n},
accept;
otherwise,
run M_{1} on w and accept only if M_{1} accepts
w.
}
2. return REGTMDECIDER(M_{2});
}
Here is the table for proving that the reduction above is
correct

ATMDECIDER 
M_{2}'s behavior 
L(M_{2}) 
REGTMDECIDER 
THE REDUCTION WILL 
M_{1} accepts 
ACCEPT 
Accept strings of the form 0^{n}1^{n} ; accepts
all others too 
∑* 
ACCEPT 
ACCEPT 
M_{1} does not accept w 
REJECT 
Accepts strings of the form 0^{n}1^{n}; 
0^{n}1^{n} 
REJECT 
REJECT 
·
Here
is the reduction from E_{TM} to EQ_{TM}:
E_{TM}DECIDER(M_{1})
{
1. construct encoding
of the following machine M_{2}:
M_{2}(x)
{
reject(x);
}
2. return
EQTMDECIDER(M_{1}, M_{2});
}
Here is the table for proving
that the reduction above is correct:

ETMDECIDER 
L(M_{2}) 
EQTMDECIDER (M_{1}, M_{2}) 
THE REDUCTION WILL 
L(M_{1}) is empty 
ACCEPT 
empty 
ACCEPT 
ACCEPT 
L(M_{1}) is not empty 
REJECT 
empty 
REJECT 
REJECT 