1
$\begingroup$

I know there's some easy proof for this, but why is $A \leq_T \bar{A}$ ? ... Suppose that $\bar{A}$ is c.e. and could loop, does this mean that the oracle $TM$ $M^{\bar{A}}$ could also loop?

But shouldn't $\leq_T$ mean that $M^{\bar{A}}$ be decidable?

$\endgroup$
  • 2
    $\begingroup$ Oracles don't loop, that's the point of oracles: they always give you the correct answer. $\endgroup$ – Vladimir Lysikov Sep 20 '17 at 11:20
  • $\begingroup$ oh right, would be handy in my exam $\endgroup$ – Link L Sep 20 '17 at 12:23
2
$\begingroup$

A language $A$ Turing-reduces to $\overline{A}$ since a Turing machine with an $\overline{A}$-oracle can compute $A$. On input $x$, it determines whether $x \in \overline{A}$ using the oracle, and then outputs the reverse answer.

$\endgroup$
2
$\begingroup$

Your misunderstanding is in the definition of an oracle. An oracle is a hypothetical device that answers the question "Is string $x$ in language $L$?" in a single computational step. It doesn't matter whether or not an actual Turing machine could answer that question; the oracle is defined to answer it, and answer it immediately.

Whether or not such a device can exist in the physical universe is irrelevant to the question of reducibility. It's relevant to the question of whether the reduction is practically usable, but that's a separate issue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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