I am confused about the purpose/statement of the Acceptance problem:

$A_{TM} =\{\langle M\rangle\,s |$ Turing machine $M$ accepts $s\}$

It can be shown that $A_{TM}$ is uncomputable, so we know that, in general, one cannot compute whether an arbitrary Turing machine will accept some input.

Common sense tells me that for a total Turing machine $T$ (one that always halts on any input in finite time) we can easily check if $T$ accepts $s$ by simply running $T$. So $A_{TM}$ is only uncomputable if non-total Turing machines are allowed.

However, given that HALT is undecidable, what is the point of knowing that $A_{TM}$ is uncomputable? HALT is arguably a more relevant result, and $A_{TM}$ is anyway only uncomputable if we allow Turing machines that may not halt - and if we allow Turing machines that may not halt, then we cannot decide if they halt on input $s$.

Further, HALT and $A_{TM}$ can be many-one reduced to one another. So, what is the point of the Acceptance problem, given that HALT is among the most well-known decision problems?

  • 1
    $\begingroup$ The acceptance problem is a variant of the halting problem. That's it. $\endgroup$ Apr 29, 2021 at 6:39
  • $\begingroup$ @YuvalFilmus thank you for your comment. I was just wondering if I missed any deeper meaning/implications behind the acceptance problem. If there are none, then my question is answered $\endgroup$
    – mto_19
    Apr 29, 2021 at 6:51


Your Answer

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