1
$\begingroup$

I'm specifically referring to this group of questions here: https://www.cs.rice.edu/~nakhleh/COMP481/final_review_sp06_sol.pdf

So as I've learnt it, say we want to prove a new Language L is undecidable using a known undecidable language D, we use Oracle calls to L to solve an instance of D right?

In none of these questions is an oracle used - For example, with L9 :"M' on input w: it runs M on x and accepts if M halts on x" That's the algorithm; no oracle is used. I understand the reasoning to their solutions, but shouldn't they be using an oracle call? I'm very new to this so sorry if I'm misunderstanding

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle.

What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ solving a problem that can't be solved - hence $M$ doesn't exist.

Improve this answer
$\endgroup$
10
  • $\begingroup$ So what is the correct way of doing it for proving undecidability of languages? With or without the calls, or do they both work? And thanks for the help $\endgroup$
    – jim22394
    Commented Apr 26, 2021 at 22:03
  • $\begingroup$ Both ways work. Whatever you prefer and feel is more natural to you would work $\endgroup$
    – nir shahar
    Commented Apr 26, 2021 at 22:04
  • $\begingroup$ Also, any proof using oracles can be converted to a proof without them, and vice versa $\endgroup$
    – nir shahar
    Commented Apr 26, 2021 at 22:04
  • $\begingroup$ What is the type of method called for this approach? I know my version is a reduction, but what is this way known as? $\endgroup$
    – jim22394
    Commented Apr 26, 2021 at 22:05
  • $\begingroup$ Proving by contradiction. Its a general concept not used only in computer science. $\endgroup$
    – nir shahar
    Commented Apr 26, 2021 at 22:05

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.