SUNY Geneseo Department of Mathematics

Reduction Proof Examples

Friday, April 1

Math 304
Spring 2016
Prof. Doug Baldwin

Questions?
Reduction Proof Examples
- Does L(M) = Σ*?
  - Reduce to A_TM
  - Assume U(M) decides L(M) = Σ*
  - Solve A_TM(M,w) as…
```
construct M2(x) as
    { not-Σ*-language = ∅ }
    run M on w
    if M accepts w, accept x {M accepts w implies L(M2)= Σ*}
    otherwise reject x {L(M2) = ∅}
run U(M2)
if U accepts, accept
otherwise reject
```
- Is |L(M)| even?
  - Show undecidable by reduction to halting
  - Assume E(M) decides |L(M)| even
  - Solve HALT_TM(M,w) as…
```
construct M2(x) with alphabet {a} as
    if x = ε, accept    { Ensure |L(M)| at least 1, which is odd }
    run M on w
    if x = aa, accept           { Only get here is M(w) halts, but if it does L(M) has 2 members, even }
    otherwise reject
run E(M2)
if E accepts M2, accept
otherwise reject
```
- Does an algorithm for computing function f(x) compute x²?
  - Outline of undecidability proof
  - Reduce to HALT_program, halting problem for programs or pseudocode algorithms
  - To solve HALT_program(P,w), construct f(x) as
```
P(w)
return x²
```
  - Now f(x) = x² only if P(w) halts, otherwise f itself never halts and so doesn’t compute any function
Next
- A few more reduction proof examples
- Rice’s Theorem, sort of a metatheorem about using reduction to prove undecidability of problems about Turing machines’ languages
- No reading