From [Wikipedia](http://en.wikipedia.org/wiki/Oracle_machine) (bold emphasis at the end is mine):



> 
> In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. **Even undecidable problems, like the halting problem, can be used.**
> 
> 
> 


Isn't assuming the existence of a machine which can decide the halting problem... problematic? The way I've heard it explained is that it's only problematic if you assume it can solve its own halting problem or any of the "super-oracles" above it. However, if an oracle O can solve the halting problem for machine M, can't M just use O to solve its own halting problem? Isn't that a contradiction, from which all propositions follow?


I'm sure I'm making an elementary mistake, so please point it out :)



Aren't "oracle machines" unsound concepts?
Oracle machines are not "problematic". Let us consider oracle machines that have the halting problem as their oracle. Now, by "the halting problem" we mean the collection of all Turing machines (without oracle) that halt when started with an empty tape.


This can be decided by an oracle machine with the halting problem as its oracle.
However, such oracle machines with halting problem oracle cannot solve the halting problem
for Turing machines with the ordinary halting problem as their oracle.
I.e., there is no oracle machine using the usual halting problem as an oracle that decides
the set of all oracle machines with the halting problem as their oracle that halt on the empty input. 


In recursion theory, there is the jump operator or Turing jump that assigns to every problem
$P$ (set of words, set of natural numbers, whatever you prefer), the set of all
(codes of) oracle Turing machines with the oracle $P$ that halt on the empty tape.
The Turing jump of a problem $P$ is strictly more complicated (more "uncomputable") than
$P$ itself, i.e., no machine with oracle $P$ decides the jump of $P$. 


