Java or python

Reduction workshop 4/30 (10 extra credit points) HW #3 due 2pm Monday May 4. Midterm #3 Tuesday May 5

Lab #9 due Friday midnight L = { <M,s> : s ∈ L(M) and |L(M)| % 2 = 0}. For example, suppose that L(M) = {aa}. Then <M,aa> ∉ L bc |L(M)| = 1, 1 % 2 = 1; If L(M) {a,aaa} then <M,ℇ> ∉ L bc ℇ ∉ L(M), but <M,aaa> ∈ L. Prove that L ∉ L by reduction from H.

Your proof could implement R, the mapping reduction function, as a Java or Python program in the form demonstrated, which allows the user to configure whether M halts on w

could R return <M#>? R, as a mapping reduction functions, transforms the question of whether <M,w> is in H to the question of whether R(<M,w>) is an element of L.

Reduction Overview

Reduction is ubiquitous — solving one problem in terms of another.

Break down cleaning your house into components

• take out garbage, etc.

Reframe on problem in terms of another.

And remember our 520 perspective — any problem can be defined in terms of language recognition

L₁ = Decide where the museum is L₂ = Decide if your map app is working correctly Suppose L₁ is reducible to L₂. Which of these statements are true? √ L₂ ∈ D → L₁ ∈ D if you can tell the app is working then can figure out where the museum is.

This is the relationship we will use in 520, with a twist, to show that some new language Lᵩ ∉ D. We reason as follows:

1. Lᵩ ∈ D → H ∈ D #We demonstrate the Lᵩ is reducible to H.

2. H ∉ D #We know this already

Reduction raw lecture notes Page 1

∴ Lᵩ ∉ D #Applying the Modus Tollens logic rule to steps 1 and 2.

Reduction raw lecture notes Page 2

L₂ ∉ D → L₁ ∉ D (False) — if the map app remains a mystery, there could be some other way to locate the museum

√ L₁ ∉ D → L₂ ∉ D if you're not sure where the museum is then you can't decide if the map app is working.

L₁ ∈ D → L₂ ∈ D (False) — You could have located the museum usng a paper map


Reduction raw lecture notes Page 3

Proving if H ∉ D then L ∉ D

(R is a reduction from H to L) ∧ (L ∈ D) → (H ∈ D) If H ∉ D is false, then at least one of the two antecedents of that implication must be false (invoking modus tollens). So:

If (R is a reduction from H to L) is true, then (L ∉ D) must be false.

Don't do reduction backwards by reducing L to H: if H ∈ D then L ∈ D

This will always be vacuously true.

Mapping Reduction—a transitive relationship L₁ is mapping reducible to L₂ (L₁ ≤M L₂) iff there exists some computable function f such that:

∀x∈Σ* (x ∈ L₁ iff ƒ(x) ∈ L₂).

Mapping reductions transform a membership question about L₁ into a membership question about L₂ Suppose that there are four languages W, X, Y, and Z. Each of the languages may or may not be in SD. However, we know the following about them:

• W ≤M X (There is a mapping reduction from W to X.)

• X ≤M Y (There is a mapping reduction from X to Y.)

• Z ≤M Y There is a mapping reduction from Z to Y.

If W ∈ SD/D, is it possible that Y ∈ D? No, because the ≤M relationship is transitive, so W ≤M Y. So if Y ∈ D, then W ∈ D

Is it possible that W ∉ D and Z ∉ SD. Yes. If Y ∉ SD, then it’s possible that none of the others are either. On the other hand, if Y∈ D, then all the others must be too.

Y ∈ D. Is it always true that ¬Z ∈ D? Yes. if Y ∈ D, then all the others are too, and D is closed under compliment.

Reduction raw lecture notes Page 4

Anatomy of an H Reduction

L = { <M> : L(M) is a regular language} For example, if L(M)= { w : w = aⁿbⁿ}, then <M> ∉ L, since aⁿbⁿ is not a regular language.

The textbook uses this mapping reduction from H to prove that L ∉ D:

R(<M, w>) = 1. Define M# 1.1. If x ∈ aⁿbⁿ then accept, else: 1.2. Erase the input tape. 1.3. Write w on the input tape. 1.4. Simulate M on w. 1.5. Accept 2. Return <M#>.

To complete the proof, a good place to start is work out equivalent TMs for M# depending on whether or not <M,w> ∈ H (that is, whether or not M halts

w), and then to write characteristic functions for L(M#) for each case.

• If <M,w> ∈ H, then M# is equivalent to M#H: 1.1. If x ∈ aⁿbⁿ then accept, else: 1.5. Accept Thus M#H would accept aⁿbⁿ at step 1.1, and all other input at step 1.5, so L(M#H) = ∑*

• If <M,w> ∉ H, then M# is equivalent to M#¬H: 1.1 If x ∈ aⁿbⁿ then accept

Thus M#¬H would accept aⁿbⁿ at step 1.1 and nothing else, so L(M#¬H) = aⁿbⁿ.

The next step is to consider whether a hypothetical TM MORACLE that could decide L would accept or reject <M#H> and <M#¬H>:

• MORACLE would accept <M#H> since L(M#H) = ∑* is a regular language.

• MORACLE would reject <M#¬H> since L(M#¬H) = aⁿbⁿ, not a regular language.

Thus if MORACLE could decide L(M#), in could also decide H. But no TM could decide H, so MORACLE could not possibly exist.

Reduction raw lecture notes Page 5

Dovetailing Exampe SD/D Proof # 1

L = {<M> : M rejects at least two even length strings}. Prove that L ∈ SD/D.

Prove L is in SD. Verbal desctription: Enumerate the strings for ∑* and then run M on the strings to avoid the twin problems of being infinte, and that M may not halt on processing some string. As soon as M rejects two even length strings, accept.

Pseudocode answer: //Use tDovetailing to find two strings that tm rejects accept/reject rejectsAtLeastTwotrings(TM tm) {

int acceptCount = 0;

SetofStrings SigmaStar = ∑*; SetofCandidateStrings candidates = Ø;

while (true) { String anotherStr = SigmaStar.pickdEvenLengthElement(); SigmaStar.remove(anotherStr); candidates.add(anotherStr);

for (String str : candidates) { // nextConfig remembers the current state and r/w head // position, and returns the next state after executing // one step in the computation on str. // State state = tm.nextConfig(str); if (state == reject) { if (++rejecttCount == 2) return accept } // if str rejected by tm else if (state == accept) { //remove str from further consideration // candidates.remove(str); } //else if str accepted by tm } //for all current candidate strings } // while considering possible candidate strings

//but of course L ∉ D, so rejectsAtLeastTwotrings will // never exectute this return statement return false; }

Reduction raw lecture notes Page 6

Complete the proof below that uses reduction to show that L ∉ D.

R(<M, w>) is a reduction from H to L, defining M# as follows: 1. Erase the tape. 2. Write w on the tape. 3. Run M on w. 4. Reject.

If Oracle exists and decides L, then Oracle(M#) decides H: • <M,w> ∈ H: Oracle accepts (M#) because … M# rejects ∑*, and |∑*| contains an infinite number of even length strings assuming ∑≠ Ø. M# rejects ∑* because it will always reach step 4 after M halts on w. Note that because M#'s input tape is erased in step 1, it will reject regardless of the input. • <M,w> ∉ H: Oracle rejects (M#) because …

M# rejects Ø, and |Ø| = 0 < 2. M# rejects no even length strings because if M does not halt in w, M# will never reach step 4.

But no machine to decide H can exist, so neither does Oracle.

Reduction raw lecture notes Page 7