Turing jump

Remarks

Example: for $A = \emptyset$, the machine $M_e^{\emptyset}$ never gets a "yes" answer, so it behaves like an ordinary Turing machine. Hence $\emptyset'$ is the set $\set{e : M_e \text{ halts on input } e}$, a form of the halting problem.

The definition of $\mathbf{a}'$ is legitimate: if $A \le_T B$, then $A' \le_T B'$, so $A \equiv_T B$ implies $A' \equiv_T B'$. For every $A$, one has $A <_T A'$, that is, $A \le_T A'$ and $A' \not\le_T A$; the proof is a diagonal argument as for the halting problem. The jump of $A$ does depend on the chosen list of machines, but only up to a computable permutation, so its degree does not. By Post's theorem, $\emptyset^{(n)}$ is complete for the $\Sigma^0_n$ sets of the arithmetical hierarchy for $n \ge 1$.