Reducibility
A way to show some languages are
undecidable !
https://www.andrew.cmu.edu/user/ko/pdfs/lecture-16.pdf
A reduces to B
• 𝐴≤𝐵
• Find area of a rectangle ≤ find length and find width
of rectangle.
• Solving B means you know how to solve the
fundamental ingredients (which are needed to solve
A).
• A solution to B can be used to solve A.
• Note, a solution to A may not be enough to solve B.
– Knowing area of a rectangular is not enough to find its
length and width !!
A reduces to B : One more example
• 𝐴≤𝐵
• Doing injection to a patient ≤ doing surgery to a
patient
• Solving B means you know how to solve the
fundamental ingredients (which are needed to solve
A).
• A solution to B can be used to solve A.
• Note, a solution to A may not be enough to solve B.
– Knowing area of a rectangular is not enough to find its
length and width !!
A reduces to B
• 𝐴≤𝐵
• Solving B means you know how to solve the
fundamental ingredients (which are needed to
solve A).
• A solution to B can be used to solve A.
• An algorithm that solves B can be converted to
an algorithm that solves A
A reduces to B
• 𝐴≤𝐵
• If B is decidable, then so is A.
• Contrapositive, if A is undecidable then so is B.
• We show that 𝐴 𝑇𝑀 is reducible to 𝐻𝐴𝐿𝑇𝑇𝑀
• Since 𝐴 𝑇𝑀 is undecidable, so is 𝐻𝐴𝐿𝑇𝑇𝑀
• Suppose 𝐻𝐴𝐿𝑇𝑇𝑀 is decidable, this means
• Then 𝐴 𝑇𝑀 is decidable.
• Then 𝐴 𝑇𝑀 is decidable.
• Then 𝐴 𝑇𝑀 is decidable.
• Contradiction
This diagram shows how 𝐴 𝑇𝑀 can be reduced to 𝐻𝐴𝐿𝑇𝑇𝑀
• A decider for 𝐴 𝑇𝑀 via 𝐸𝑇𝑀 is possible.
• We are given < 𝑀, 𝑤 >, and asked to find
whether < 𝑀, 𝑤 > ∈ 𝐴 𝑇𝑀 ?
• For this, First create 𝑀1 (from the given
< 𝑀, 𝑤 >)
• A decider for 𝐴 𝑇𝑀 via 𝐸𝑇𝑀 is possible.
• We are given < 𝑀, 𝑤 >, and asked to find
whether < 𝑀, 𝑤 >∈ 𝐴 𝑇𝑀 ?
• For this, First create 𝑀1
Now, 𝐿 𝑀1 is what?
• Now, 𝐿 𝑀1 is what?
• Now, 𝐿 𝑀1 is what?
• 𝐿(𝑀1 ) is either *𝑤+ or is 𝜙
• Now, if 𝑀1 is in 𝐸𝑇𝑀
– This means, 𝐿 𝑀1 = 𝜙
– This means, < 𝑀, 𝑤 > ∉ 𝐴 𝑇𝑀
• Now, if 𝑀1 is not in 𝐸𝑇𝑀
– This means, 𝐿 𝑀1 ≠ 𝜙
– This means, < 𝑀, 𝑤 > ∈ 𝐴 𝑇𝑀
• A decider for 𝐴 𝑇𝑀 via 𝐸𝑇𝑀 is possible.
• That is, 𝐴 𝑇𝑀 can be reduced to 𝐸𝑇𝑀 .
• Contradiction
• Decider for 𝐴 𝑇𝑀 via 𝐸𝑄𝑇𝑀
• Following is the reduction of 𝐴 𝑇𝑀 to 𝐸𝑄𝑇𝑀
This is a decider for 𝑨𝑻𝑴
Alternate way to show 𝐸𝑄𝑇𝑀 is
undecidable.
• Since, we know 𝐸𝑇𝑀 is undecidable,
• We can try to reduce 𝐸𝑇𝑀 to 𝐸𝑄𝑇𝑀
• Let R be a decider for 𝐸𝑄𝑇𝑀
• We can build a decider (call this S ) for 𝐸𝑇𝑀 by
using R
S: Decider for 𝑬𝑻𝑴
• If REGULARTM is decidable, then this can be
used to decide ATM .
• Let R be a decider for REGULARTM .
How R can be used to decide
<M,w> Є ATM ?
• Build M2 as shown
How R can be used to decide
<M,w> Є ATM ?
• Build M2 as shown
• Similar to REGULARTM , we can show CFLTM is
undecidable.
– That is, finding whether a TM’s language is CFL or
not is undecidable.
– In fact, we can extend this. TM’s language is finite
or not is undecidable.
– General theorem in this regard is called The Rice’s
Theorem.
More formal way of reductions
MAPPING REDUCTION
WE CAN GET MORE REFINED ANSWERS
Computable function
•
•
An Example:
Let A is 0* , and B is {0, 1}
Let the 𝑓 is defined as below.
If 𝑤 ∈ 0∗ and 𝑤 𝑖𝑠 𝑒𝑣𝑒𝑛 𝑡ℎ𝑒𝑛 𝑓 𝑤 = 0,
Else if 𝑤 ∈ 0∗ and 𝑤 𝑖𝑠 𝑜𝑑𝑑 𝑡ℎ𝑒𝑛 𝑓 𝑤 = 1,
Else if 𝑤 ∉ 0∗ 𝑡ℎ𝑒𝑛 𝑓 𝑤 = 11.
𝐴 𝑇𝑀 ≤𝑚 𝐸𝑇𝑀
• 𝐴 𝑇𝑀 = < 𝑀, 𝑤 > 𝑀 is a TM that accepts 𝑤+
• 𝐸𝑇𝑀 = *< 𝑀 > |𝐿 𝑀 ≠ 𝜙+
• 𝑓: Σ∗ → Σ ∗ can be defined as
Create 𝑀′ : On input 𝑥,
if 𝑥 ≠ 𝑤, output “Reject”;
if 𝑥 = 𝑤, run 𝑤 on 𝑀, output the result.
Solution given in the class.
*𝑤+ 𝑖𝑓 𝑀 𝑎𝑐𝑐𝑒𝑝𝑡𝑠 𝑤
𝐿 𝑀1 =
𝜙, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑒
𝐿 𝑀2 = *𝑤+
*𝑤+ 𝑖𝑓 𝑀 𝑎𝑐𝑐𝑒𝑝𝑡𝑠 𝑤
𝐿 𝑀1 =
𝜙, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑒
𝐿 𝑀2 = 𝜙
Alternate solutions found in the net.
Σ ∗ , 𝑖𝑓 𝑀 𝑎𝑐𝑐𝑒𝑝𝑡𝑠 𝑤
𝐿 𝑀′ =
𝜙, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝐿 𝑀′′ = Σ∗
𝐴 𝑇𝑀 ≤𝑚 𝐸𝑄𝑇𝑀
Σ ∗ , 𝑖𝑓 𝑀 𝑎𝑐𝑐𝑒𝑝𝑡𝑠 𝑤
𝐿 𝑀′ =
𝜙, 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
𝐿 𝑀′ ′ = 𝜙
http://www.cs.tau.ac.il/~bchor/CM09/Compute9.pdf
http://www.cs.tau.ac.il/~bchor/CM09/Compute9.pdf
Has (towards end) some good slides on Rice’s theorem and
its consequences.
• That is, 𝐴 𝑇𝑀 can be reduced to 𝑃𝐶𝑃.
• This reduction is via a simplified 𝑃𝐶𝑃 called
𝑀𝑃𝐶𝑃 (modified PCP).
• Several undecidable properties of CFGs are
obtained by reducing them (i.e., the
corresponding languages) from PCP.
