- Using
**reducibility**in decidability proofs - Prove HALT
_{TM}is**NOT decidable** - Define some other undecidable languages:
- E
_{TM} - REGULAR
_{TM} - EQ
_{TM} - Reducibility is also central to studing P and NP (Chapter 7)

- To prove that A
_{TM}is undecidabile we used diagonalization - Now we use the undecidability of A
_{TM}to prove that other languages are undecidable - Key idea - Prove by contradiction that language L is undecidable:
- Assume TM B decides L
- Then use B to create a decider for A
_{TM}(or another undecidable language) - This is a contradiction, and so B must not exist and L must be undecidable
- Example: Prove HALT
_{TM}is undecidable

- HALT
_{TM}= {<M, w> | M is a TM and M halts on input w} - Prove that HALT
_{TM}is undecidable: - Assume that TM R is a DECIDER for HALT
_{TM}. - Construct TM S to decide A
_{TM}, as follows: - "On input <M, w>, an encoding of a TM M and a string w:
- Run TM R on input <M, w> to see if M halts on w
- If R accepts (ie M halts on w) simulate M on w until it halts
- If the simulation halts in M's Accept state, then S enters its Accept state
- If the simulation halts in M's Reject state, then S enters its Reject state
- If R rejects (ie M does not halt on w), then S enters its Reject state
- Thus TM S decides A
_{TM}, but this is a contradiction since A_{TM}is NOT DECIDABLE. - Thus, R can not exist and HALT
_{TM}is undecidable

- We have proved HALT
_{TM}is not decidable without using diagonalization - The proof used
**reduction**: - We reduced A
_{TM}to HALT_{TM} - We used the (assumed) solution to HALT
_{TM}to solve A_{TM} - General approach to use reduction to prove that P is undecidable:
- Assume that P is decidable with decider M
- Use M to build a decider for some undecidable language
- This contradiction implies that P is NOT decidable
- We can now use HALT
_{TM}to prove that OTHER languages are not decidable

- The following languages are not decidable:
- E
_{TM}= {<M> | M is a TM and L(M) = {} }- Proof: reduce A
_{TM}to E_{TM}(ie use a decider for ... in a decider for ...) - See book for details

- Proof: reduce A
- REGULAR
_{TM}= {<M> | M is a TM and L(M) is Regular} - Proof: reduce A
_{TM}to REGULAR_{TM} - See book for details
- EQ
_{TM}= {<M1, M2> | M1 and M2 are TMs and L(M1) = L(M2)} - Proof is to reduce E
_{TM}to EQ_{TM}: - Let TM R decide EQ
_{TM}and construct TM S to decide E_{TM}as follows: - On input <M>, where M is a TM:
- Run R on input <M, M1>, where TM M1 rejects all inputs
- If R accepts, accept; if R rejects, reject
- If R decides EQ
_{TM}, then S decides E_{TM}. But E_{TM}is undecidable and so EQ_{TM}must also be undecidable. - In Python, the code would look like this:

# E(M) is a decider for E_{TM}= {Machines that recognize empty langs} def E(M): M1 = Some TM that rejects all strings (ie L(M1) = {}) return EQ(M, M1) # EQ(M, M1) is a decider for EQ_{TM}# = {Pairs of machines that recognize the same langs}

- To reduce Problem A to Problem B:
- write a solution to A that uses a solution to B
- Example from book: finding area of a rectangle reduces to finding its length and width
- Python solution:

def findArea(r): (l, w) = findLenWid(r) return l * w

def findMin(a): b = sort(a) return b[1]