0
$\begingroup$

I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable

I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to prove is undecidable to solve a known undecidable language.

However, with mapping reductions, am I right in assuming these calls aren't needed? In addition, in the link provided, the solution pseudocode says

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

How can you say "if it accepts"? How can you determine this, what if it loops forever and this is never found out? Why can you make such statements with a mapping reduction but not with Turing reductions? Could I make a statement like "if M halts on w, do ...". I mentioned this to my teaching assistant and he said you can't make any statements like these unless you're accessing an oracle and doing a during reduction, but I see loads of examples which seem to show otherwise. Hopefully this makes sense

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Usually, when the context of the statement "if $M$ accepts $x$" is in a loop simulating the execution of $M$ on $x$, we just mean to say that if the simulation stopped and $M$ accepted/rejected then do something, otherwise just continue simulating (the more precise way of writing this would be to say "if $M$ accepted after $t$ steps then...").

Your pseudocode doesn't do anything magical, it simply checks at a specific point of the simulation whether or not $M$ already accepted/rejected.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks for the answer. So likewise, can you say something like "if M halts on x" without accessing the halt oracle? Is that fine to do with mapping reductions? Can you do that with turing reductions as well, or can you only make such statements if you're accessing the halt oracle $\endgroup$
    – jim22394
    Commented Apr 29, 2021 at 9:02
  • $\begingroup$ Since the halting problem is not decidable, there isn't an always halting procedure that would allow you to check whether or not $M$ halts on $x$ for arbitrary $M,x$. If you had a halting oracle then this would have been easy, simply query it on $(M,x)$. $\endgroup$
    – Ariel
    Commented Apr 29, 2021 at 9:06
  • $\begingroup$ So how come you're allowed to make a statement like "if M accepts x" but not "if M halts on x"? $\endgroup$
    – jim22394
    Commented Apr 29, 2021 at 9:07
  • $\begingroup$ Both are ok in the context I described, you can always simulate $M$ and at any given point check if it already accepted/halted. The problem arises if you use this as a command which supposedly always returns an answer. $\endgroup$
    – Ariel
    Commented Apr 29, 2021 at 9:09
  • 1
    $\begingroup$ I have no problem with the pseudocode above, someone else might require you to be more specific, e.g. loop for $t\in\mathbb{N}$, and inside the loop execute $M$ on $x$ for $t$ steps and then do something if $M$ halted/accepted. $\endgroup$
    – Ariel
    Commented Apr 29, 2021 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.