Java or python
Rony
Reduction_highlights.pptxReduction is Ubiquitous
● Calling Jen
Call Jen
Get hold of Jim
● Crisis detection via pizza orders
Show national crisis exists
Show spike in pizza orders at Pentagon
● Fixing dinner
Fix dinner
Fix entrée Fix salad Fix dessert
Suppose L₁ is reducible to L₂. Which of these statements are true?
L₂ ∈ D → L₁ ∈ D
L₂ ∉ D → L₁ ∉ D
L₁ ∈ D → L₂ ∈ D
L₁ ∉ D → L₂ ∉ D
It may help to think about languages representing events from everyday life, such as L₁ = Decide where the museum is L₂ = Decide if the map app is working
A reduction R from L1 to L2 is one or more Turing
machines such that:
If there exists a Turing machine Oracle that decides (or
semidecides) L2, then the Turing machines in R can be
composed with Oracle to build a deciding (or a
semideciding) Turing machine for L1.
P £ P¢ means that P is reducible to P¢.
1. Using Reduction to prove L ∉ D
(R is a reduction from L1 to L2) Ù (L2 is in D) ® (L1 is in D)
If (L1 is in 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 L1 to L2) is true,
then (L2 is in D) must be false.
2. Using Reduction to prove L ∉ D
1. Choose a language L1:
● that is already known not to be in D, and
● that can be reduced to L2.
2. Define the reduction R.
3. Describe the composition C of R with Oracle (the hypothetical TM that can decide L2.)
4. Show that C does correctly decide L1 iff Oracle exists. We
do this by showing:
● R can be implemented by Turing machines,
● C is correct:
● If x Î L1, then C(x) accepts, and
● If x Ï L1, then C(x) rejects.
4. Using Reduction to prove L ∉ D
Showing that L2 is not in D:
H (known not to be in D) H in D But H not in D
R
L (a new language whose if L in D So L not in D
decidability we are
trying to determine)
modus tollens
3. Using Reduction to prove L ∉ D
Mapping Reductions
L1 is mapping reducible to L2 (L1 £M L2) iff there exists
some computable function f such that:
"xÎS* (x Î L1 « f(x) Î L2).
To decide whether x is in L1, we transform it, using f,
into a new object and ask whether that object is in L2.
Mapping reductions change a membership question about L1 into a membership question about L2.
A Block Diagram of C
The Oracle will accept L(M#) iff Hℇ ∈ D.
A clear declaration of the reduction “from” and “to” languages.
A clear description of R.
If R is doing anything nontrivial, argue that it can be implemented as a TM.
Note that machine diagrams are not necessary or even sufficient in these proofs. Use them as thought devices, where needed.
Run through the logic that demonstrates how the “from” language is being decided by the composition of R and Oracle. You must do both accepting and rejecting cases.
Declare that the reduction proves that your “to” language is not in D.
Important Elements in a Reduction Proof
The right way to use reduction to show that L2 is not in D:
1. Given that L1 is not in D, L1
2. Reduce L1 to L2, i.e., show how to solve L1
(the known one) in terms of L2 (the unknown one) L2
Doing it wrong by reducing L2 (the unknown one to L1):
If there exists a machine M1 that solves H, then we could build a
machine that solves L2 as follows:
1. Return (M1(<M, e>)).
This proves nothing. It’s an argument of the form:
If False then … everything is true.
The Most Common Mistake: Doing the Reduction Backwards
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?
W ≤M X; X ≤M Y; Z ≤M Y, and 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?
W ≤M X; X ≤M Y; Z ≤M Y. 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.
• 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.
Is it true that if Y∈ D then ¬Z ∈ D?
W ≤M X; X ≤M Y; Z ≤M Y; 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.
Theorem: He = {<M> : TM M halts on e} is not in D.
Proof: by reduction from H:
H = {<M, w> : TM M halts on input string w}
R
(?Oracle) He {<M> : TM M halts on e}
R is a mapping reduction from H to He:
R(<M, w>) =
1. Construct <M#>, where M#(x) operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
2. Return <M#>.
He = {<M> : TM M halts on e}
R(<M, w>) =
1. Construct <M#>, where M#(x) operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
2. Return <M#>.
If Oracle exists, C = Oracle(R(<M, w>)) decides H:
● C is correct: M# ignores its own input. It halts on everything or
nothing. So:
● <M, w> Î H: M halts on w, so M# halts on everything. In
particular, it halts on e. Oracle accepts M#.
● <M, w> Ï H: M does not halt on w, so M# halts on nothing and
thus not on e. Oracle rejects M#.
Proof, Continued
R can be implemented as a Turing machine.
C is correct.
So, if Oracle exists:
C = Oracle(R(<M, w>)) decides H.
But no machine to decide H can exist.
So neither does Oracle.
Conclusion
If we could decide whether M halts on the specific string e, we
could solve the more general problem of deciding whether M
halts on an arbitrary input.
Clearly, the other way around is true: If we could solve H we
could decide whether M halts on any one particular string.
But doing a reduction in that direction would tell us nothing
about whether He was decidable.
The significant thing that we just saw in this proof is that there
also exists a reduction in the direction that does tell us that He is
not decidable.
This Result is Somewhat Surprising
H = {<M, w> : TM M halts on input string w}
R
(Oracle) He {<M> : TM M halts on e}
R is a reduction from H to He:
R(<M, w>) =
1. Construct <M#>, where M#(x) operates as follows:
1.1. Erase the tape. x is our name for the contents of M#'s tape
1.2. Write w on the tape.
1.3. Run M on w.
2. Return <M#>.
● Oracle (the hypothetical machine that could decide He).
● R (the machine that builds M#. Actually exists).
● C (the composition of R with Oracle).
● M# (the machine we will pass as input to Oracle). Note that we never run it. Think of the Oracle as like a source code analyzer.
● M (the machine whose membership in H we are interested in determining;
thus also an input to R along with w)
Note that x is the input to M#, and w is the input to M. Do not confuse them!
To prove He ∉ D we consider 5 distinct TMs
H = {<M, w> : TM M halts on input string w}
R
(?Oracle) He {<M> : TM M halts on e}
H contains strings of the form:
(q00,a00,q01,a10,¬),(q00,a00,q01,a10,®),…,aaa
where aaa is one example of w ∈ ∑*.
He contains strings of the form:
(q00,a00,q01,a10,¬),(q00,a00,q01,a10,®),…
The language on which some M halts contains strings of some arbitrary form, for example,
(letting S = {a, b}): aaa
How Many Languages Are We Dealing With?
Recall that a mapping reduction from L1 to L2 is a computable function f where:
"xÎS* (x Î L1 « ƒ(x) Î L2)
The function ƒ transforms a membership question in L1 into a membership question in L2.
When we use a mapping reduction, we return:
Oracle(f(x))
Note that Rich uses R as the name for ƒ in her reduction proofs.
Sometimes we need a more general ability to use Oracle
as a subroutine and then to do other computations after it
returns.
Sometimes Mapping Reducibility Isn’t Right
H = {< M, w> : TM M halts on input string w}
R
(?Oracle) L2 = {<M> : M accepts no even length strings}
R(<M, w>) =
1. Construct the description <M#>, where M#(x) operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return <M#>.
If Oracle exists, then C = Oracle(R(<M, w>)) decides H:
● C is correct: M# ignores its own input. It accepts everything or nothing,
depending on whether it makes it to step 1.4. So:
● <M, w> Î H: M halts on w. Oracle:
● <M, w> Ï H: M does not halt on w. Oracle:
Does C = Oracle(R(<M#>)) work in this proof that L₂ ∉ D?
H = {< M, w> : TM M halts on input string w}
R
(?Oracle) L2 = {<M> : M accepts no even length strings}
R(<M, w>) =
1. Construct the description <M#>, where M#(x) operates as follows:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept.
2. Return <M#>.
If Oracle exists, then C = ØOracle(R(<M, w>)) decides H:
● R and Ø can be implemented as Turing machines.
● C is correct:
● <M, w> Î H: M halts on w. M# accepts everything, including some
even length strings. Oracle rejects so C accepts.
● <M, w> Ï H: M does not halt on w. M# gets stuck. So it accepts
nothing, so no even length strings. Oracle accepts. So C rejects.
But no machine to decide H can exist, so neither does Oracle.
It won't work without inverting the decision of the Oracle
We show that A is not in D by reduction from H.
H = {<M, w> : TM M halts on input string w}
R
(?Oracle) A = {<M, w > : w Î L(M) }
R(<M, w>) =
1. Construct the description <M#>:
1.1. Erase the tape.
1.2. Write w on the tape.
1.3. Run M on w.
1.4. Accept
2. Return <M#, w>.
If an Oracle to decide A exists, then C = Oracle(R(<M, w>)) decides H:
● R can be implemented as a Turing machine.
● C is correct: M# accepts everything or nothing. So:
● <M, w> Î H: M halts on w, so M# accepts every possible input x. In particular, it accepts x = w. So Oracle accepts <M#, w>.
● <M, w > Ï H: M does not halt on w. M# gets stuck in step 1.3 and so
accepts nothing. In particular, it does not accept x = w.
So Oracle rejects <M#, w>.
But no machine to decide H can exist, so neither does Oracle.
A = {<M, w> : w Î L(M)}
L = {<Ma, Mb> : e Î L(Ma) – L(Mb)}. That is, the strings in L are pairs of TM string encodings, such that e is in the language accepted by the first encoded TM, but not the second.
We can prove L ∈ ¬SD by a reduction from ¬H.
R( … ) is a reduction from ¬H to L:
1. Define M#1
1.a Accept
2. Define M#2
2.a Erase the tape.
2.b Write w on the tape.
2.c Simulate M on w.
2.d …
Return <M#1, M#2>.
<M, w> Î ØH: L(M#1) - L(M#2) = …, and Oracle accepts <M#1,M#2> because …
<M, w> Ï ØH: L(M#1) - L(M#2) = …, and Oracle rejects <M#1,M#2> because …
We can prove L ∈ ¬SD by a reduction from ¬H.
R( <M,w> ) is a reduction from ¬H to L:
1. Define M#1
1.a Accept
2. Define M#2
2.a Erase the tape.
2.b Write w on the tape.
2.c Simulate M on w.
2.d Accept
Return <M#1, M#2>.
<M, w> Î ØH: L(M#1) - L(M#2) = ∑*, and Oracle accepts <M#1,M#2> because ℇ ∈ ∑*.
<M, w> Ï ØH: L(M#1) - L(M#2) = Ø, and Oracle rejects <M#1,M#2> because ℇ ∉ Ø.
| The Problem View | The Language View | Status |
| Does TM M have an even number of states? | {<M> : M has an even number of states} | D |
| Does TM M halt on w? | H = {<M, w> : M halts on w} | SD/D |
| Does TM M halt on the empty tape? | He = {<M> : M halts on e} | SD/D |
| Is there any string on which TM M halts? | HANY = {<M> : there exists at least one string on which TM M halts } | SD/D |
| Does TM M halt on all strings? | HALL = {<M> : M halts on S*} | ØSD |
| Does TM M accept w? | A = {<M, w> : M accepts w} | SD/D |
| Does TM M accept e? | Ae = {<M> : M accepts e} | SD/D |
| Is there any string that TM M accepts? | AANY {<M> : there exists at least one string that TM M accepts } | SD/D |
