SUNY Geneseo Department of Mathematics

Undecidable Problems

Friday, March 25

Math 304
Spring 2016
Prof. Doug Baldwin

Return to List of Lectures

Previous Lecture

Misc
- REU Talk
  - Wednesday, March 30, 3:30 PM
  - South 328
  - Walter Gerych re obstructed “mean curvature flow” and cellular automata
  - Up to 2 points homework extra credit for write-ups
Questions?
Undecidability
- First part of section 4.2
  - Undecidability with Turing machine that takes other TM and string and decides whether 2nd TM accepts or rejects
  - Similar to problem at start of semester
  - Detour re countable and uncountable sets
    - Familiar? Yes
  - There are recognizable things that aren’t decidable
- Examples
  - Does Turing machine M halt at all when run on w? (the Halting Problem)
    - Def: Halting Problem: given Turing machine M and input w, accept ⟨M,w⟩ iff M halts when run on w, reject otherwise
    - Theorem: the halting problem is undecidable
    - Proof:
      - Assume there is a decider H(M,w) for halting problem
      - Construct Turing machine PARADOX to work as follows:
        On input w Run H(w,w) If H accepted Loop forever If H rejected Accept
      - Contradiction: H does not correctly analyze PARADOX run on ⟨PARADOX⟩
  - Does computer program P print “I love undecidability” when run on input w?
    - Assume H(P,w) decides whether P(w) prints “I love...”
      - (But in PARADOX, use an implementation of H in which any print “I love undecidability” actually prints something else)
    - Construct
```
PARADOX( w )
    if H(w,w) accepts
        return
    else
        print “I love…”
```
    - Contradiction from PARADOX( PARADOX )
    - As a technical caution, beware that H doesn’t do the thing you are deciding
```
NastyH(P,w)
    if P == w
        print “I love …”
    Analyze P and w
```
Next
- An unrecognizable language
- Read “A Turing-Unrecognizable Language” in section 4.2
  - Middle of page 209 through middle of 210

Next Lecture