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:
• ETM
• REGULARTM
• EQTM

• 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:
1. Run TM R on input <M, w> to see if M halts on w

2. 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

3. 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:
1. Run R on input <M, M1>, where TM M1 rejects all inputs
2. 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)