CSE237 Lecture 22, Spring 2006

Lecture 22 (Undecidability), 4/12/06

Concepts, definitions (in italics):

A_TM is not decidable (see notes below for sketch of proof)
Corollary: The complement of A_TM is not recognizable (i.e., A_TM is not co-recognizable).
Proof by diagnoalization.
There are two directions for using reductions to prove something decidable or not:
- Positive: If A reduces to B and B is decidable then A is decidable
- Negative: If A reduces to B and A is not decidable then B is not decidable
We've used reductions before to decide one language by using decider for another one. Now we are using the other direction: to show that a new language is not decidable because another one is not.
E_TM, REGULAR_TM are not decidable (reductions from A_TM)
EQ_TM is not decidable (reduction from E_TM)

Reading:

Chapter 4.2 (except for corollary 4.18)
Chapter 5.1, through the proof of Theorem 5.4

Skills:

Know new definitions, understand new concepts.
Understand the proof that A_TM is not decidable; this is our first example of a language that's recognizable but not decidable.
Prove that the complement of A_TM is not recognizable.
Understand the proofs that REGULAR_TM , E_TM are not decidable
Be able to prove that EQ_TM is not decidable

Notes:

Proof of undecidability of A_TM (by contradiction):
- Assume there is an algorithm A_TM_DECIDER(M,w)
- Then we can create another algorithm D(M) which consists of the following 2 steps:
1) bool b = A_TM_DECIDER(M,M)
2) return (!b)

- Since D is an algorithm, there must exist a TM M_D implementing D.
- What should D(M_D) return?? Either YES or NO gives a contradiction.
- Therefore, the algorithm A_TM_DECIDER(M,w) does not exist.

Proving that some language B is not decidable proceeds by contradiction, as follows:

Assume that B is decidable. Construct a reduction from A to AB where A is some non-decidable language.
Use a table-based approach to show that the construction is correct.
Argue that if B were decidable, then A would also be decidable. But A is not decidable, so B cannot be decidable either.

For the proofs by negative reduction, we use a 2-row table to figure out what's going on. The top row is for input in the language; the second is for input that is not. The algorithm should behave correctly for both types of inputs.

Here is the reduction from A_TM to REGULAR_TM:

A_TM-DECIDER(M,w) {

1. construct a description of the following machine M₂:

M₂(x) {

if x is of the form 0ⁿ1ⁿ, accept;
otherwise, run M on w and accept only if M accepts w.
}

2. return REGULAR_TM-DECIDER(M₂);

}

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

	What we want A_TMto return	M₂'s behavior	L(M₂)	REGULAR_TM(M₂)
M accepts W	accept	Accept strings of the form 0ⁿ1ⁿ ; accepts all others too	∑*	accept
M does not accepts W	reject	Accepts strings of the form 0ⁿ1ⁿ; Does not accept others	0ⁿ1ⁿ (not regular)	reject

Here is the reduction from A_TM to E_TM:

A_TM-DECIDER(M,w) {

1. construct a description of the following machine M₁:

M₁(x) {

if x ≠ w, reject;
otherwise, run M on w and accept only if M accepts w.
}

2. return ŲE_TM-DECIDER(M₁); // note that the output is negated

}

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

	What we want A_TM to return	M₁'s behavior	L(M₁)	E_TM (M₁)	We return
M accepts W	accept	Reject all x ≠ w, Accept w	{w}	Reject	Accept
M does not accepts W	reject	Reject all x ≠w, Do not accept w	Ā	Accept	Reject

Here is the reduction from E_TM to EQ_TM:

E_TM-DECIDER(M) {

1. construct a description of the following machine M₃:

M₃(x) {

reject(x);
}

2. return EQ_TM-DECIDER(M, M₃);

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

	What we want E_TM to return	L(M₃)	EQ_TM (M, M₃)
L(M) = Ā	accept	Ā	accept
L(M) ≠ Ā	reject	Ā	reject