3
$\begingroup$

For example, many reductions from $A_{TM}$ will often have the lines:

Simulate M on w:
    if M accepts 
       ...
    else

But: a reduction is a computable function, right? So why are we allowed to say "if M accepts"? Also, I can take the same logic and reduce $A_{TM}$ to a deciable language: Let L be the empty language. Clearly L is decidable.

Given $(M,w)$:

 Output output:
      If M accepts w
            output = '0'
      else
            output = $\emptyset$

Obviously I'm wrong here. But why? Thanks in advance.

Improve this question
$\endgroup$
2
  • $\begingroup$ I doubt that you are given as input "$(M,w) \in A_{TM}$". Perhaps you are given an instance $(M,w)$ of the halting problem, that is, an element of the domain of $A_{TM}$. $\endgroup$
    – Yuval Filmus
    Mar 13, 2017 at 19:44
  • $\begingroup$ Right, that's what I meant, I'll fix it, thanks. $\endgroup$
    – Jeff A
    Mar 13, 2017 at 19:45

1 Answer 1

Reset to default
0
$\begingroup$

There are two options:

  • Either the pseudocode means "run $A_{TM}$ on the pair $M,w$" when it says "Simulate $M$ on $w$";
  • or it really means to simulate $M$ on $w$, and if it ever stops then do something; there is no "else" clause in that case.
Improve this answer
$\endgroup$
5
  • $\begingroup$ So basically "If M accepts" should be changed to "If M ever accepts?" What if I wanted to do something in the case that M rejects? Is that possible? $\endgroup$
    – Jeff A
    Mar 13, 2017 at 19:47
  • $\begingroup$ You can do whatever you want once $M$ halts. $\endgroup$
    – Yuval Filmus
    Mar 13, 2017 at 19:56
  • $\begingroup$ I guess my question is this: Someone asks me to give them a computable function.. I give them a function that contains "if/when M halts on W, accept x"... How is that computable? $\endgroup$
    – Jeff A
    Mar 13, 2017 at 20:04
  • $\begingroup$ Simple. You simulate $M$ on $w$, and if it ever halts, you do something. Otherwise, your machine also never halts. $\endgroup$
    – Yuval Filmus
    Mar 13, 2017 at 20:05
  • $\begingroup$ Oh I get it now. The problem I was having was that I was thinking of giving the output only after simulating M on w, when in fact you first give M', which itself simulates M on w. Thanks :) $\endgroup$
    – Jeff A
    Mar 13, 2017 at 20:06

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.