Skip to main content
formatting
Source Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

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

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

F: "For input x $F$:

1.Simulate M for input w
if it accepts, loop
if it rejects accept x "

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

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

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

For a given string $<M,w>$ you construct the following machine:

F: "For input x:

1.Simulate M for input w
if it accepts, loop
if it rejects accept x "

Now you can see that $<M,w> \in MP \iff <F> \in NeverHalt$

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$

Source Link
lea
  • 63
  • 1
  • 1
  • 7

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

For a given string $<M,w>$ you construct the following machine:

F: "For input x:

1.Simulate M for input w
if it accepts, loop
if it rejects accept x "

Now you can see that $<M,w> \in MP \iff <F> \in NeverHalt$