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 :&quot;M' on input w: it
runs M on x and accepts if M halts on x&quot; 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.