ITEC 420 - Section 5.1 - Reducibility and More
Undecidable Problems
Main Ideas in Section 5.1
- Using reducibility in decidability proofs
- Prove HALTTM is NOT decidable
- Define some other undecidable languages:
- Reducibility is also central to studing P and NP (Chapter 7)
Reducibility and Proving Decidability
- To prove that ATM is undecidabile we used diagonalization
- Now we use the undecidability of ATM
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 ATM (or another undecidable
language)
- This is a contradiction, and so B must not exist and L must be
undecidable
- Example: Prove HALTTM is undecidable
HALTTM is Undecidable
- HALTTM = {<M, w> | M is a TM and M halts on input w}
- Prove that HALTTM is undecidable:
- Assume that TM R is a DECIDER for HALTTM.
- Construct TM S to decide ATM, 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 ATM, but this is a contradiction since
ATM is NOT DECIDABLE.
- Thus, R can not exist and HALTTM is undecidable
Proving Undecidablity by Reduction
- We have proved HALTTM is not decidable without
using diagonalization
- The proof used reduction:
- We reduced ATM to HALTTM
- We used the (assumed) solution to HALTTM
to solve ATM
- 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 HALTTM to prove that
OTHER languages are not decidable
More Decidability Results
- The following languages are not decidable:
- ETM = {<M> | M is a TM and L(M) = {} }
- Proof: reduce ATM to ETM (ie use a decider for
... in a decider for ...)
- See book for details
- REGULARTM = {<M> | M is a TM and L(M) is Regular}
- Proof: reduce ATM to REGULARTM
- See book for details
- EQTM = {<M1, M2> | M1 and M2 are TMs and L(M1) = L(M2)}
- Proof is to reduce ETM to EQTM:
- Let TM R decide EQTM and construct TM S to
decide ETM 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 EQTM, then S decides ETM. But ETM is
undecidable and so EQTM must also be undecidable.
- In Python, the code would look like this:
# E(M) is a decider for ETM = {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 EQTM
# = {Pairs of machines that recognize the same langs}
Reducibility
- 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
Example: finding array minimum by sorting:
Python solution:
def findMin(a):
b = sort(a)
return b[1]
Reducibility is a key concept in P and NP (Chapter 7)