Belatedly, this notion has – unsurprisingly – been studied before; see Yamaguchi, Effective nonrecursiveness.
Say that a function $f:\omega\rightarrow\omega$ is a noncomputability witness for a set $X\subseteq\omega$ iff for no $e$ do we have $\Phi_e(f(e))\downarrow=X(f(e))$. Note that $f$ does not have to tell us why the proposed computation fails (that is, whether $\Phi_e(f(e))\uparrow$ or $\Phi_e(f(e))\downarrow\not=X(f(e))$), simply some bit on which it fails.
I'm interested in how hard it can be to compute noncomputability witnesses (hehehe). For example, the halting problem $\emptyset'$ has a computable noncomputability witness, and every non-computable $X$ has a noncomputability witness $\le_TX\oplus \emptyset'$. Meanwhile, it's not hard (if a bit tedious) to construct a set of Turing degree ${\bf 0'}$ all of whose noncomputability witnesses are $\ge_T{\bf 0'}$. (Consequently the notion of noncomputability witness plays better with $\le_m$ than with $\le_T$; if we want a Turing-well-behaved version we should allow $f$ to pick out a finite set of candidate disagreements.)
However, I can't get a c.e. example at the moment:
Is there a noncomputable c.e. set all of whose noncomputability witnesses have Turing degree $\ge_T{\bf 0'}$?
I would be especially interested in an example which itself has Turing degree ${\bf 0'}$ – there is no obvious (to me) reason why such cannot exist.
Best Answer
Yes, there is a c.e. set of Turing degree ${\bf 0}'$ all of whose noncomputability witnesses have Turing degree $\geq_T {\bf 0}'.$
Pick a pairing function $p:\omega\times\omega\to\omega.$ Let $\Sigma:\omega\to\omega$ be the busy beaver function. Take $X$ to be the set of $p(i,j)$ with $j\leq \Sigma(i).$ So $X$ is c.e. and has Turing degree ${\bf 0}'.$
Given the pair $(i,\Sigma(i)),$ we can uniformly construct a machine $e$ which computes $X$ correctly on $p(i',j')$ with $i'\leq i,$ and always outputs $1$ if $i'>i.$ Such an $e$ computes $X$ correctly except on $p(i',j')$ with $i'>i$ and $j'>\Sigma(i')\geq \Sigma(i+1).$ A noncomputability witness $f$ for $X$ therefore gives us the power to turn $(i,\Sigma(i))$ into an upper bound $\pi_2(f(e))$ for $\Sigma(i+1),$ and therefore lets us compute $\Sigma(i+1).$ By iterating this we can compute any $\Sigma(n),$ using $f$ as an oracle.