Skip to main content
2 of 2
formatting
Raphael
  • 72.9k
  • 30
  • 181
  • 393

You can reduce the $MP= \{\langle M,w \rangle : w \in L(M)\}$ to $NeverHalt$

For a given string $\langle M,w \rangle $ you construct the following machine $F$:

For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

Now you can see that $\langle M,w \rangle \in MP \iff \langle F \rangle \in NeverHalt$

lea
  • 63
  • 1
  • 1
  • 7