# Proving Undecidability with reductions - Why do some proofs not use an Oracle?

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

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.

• 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 Apr 26 at 22:03
• Both ways work. Whatever you prefer and feel is more natural to you would work Apr 26 at 22:04
• Also, any proof using oracles can be converted to a proof without them, and vice versa Apr 26 at 22:04
• What is the type of method called for this approach? I know my version is a reduction, but what is this way known as? Apr 26 at 22:05
• Proving by contradiction. Its a general concept not used only in computer science. Apr 26 at 22:05