Skip to main content
1 of 4
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Let $T$ be an "appropriate" theory - this means $T\subseteq Th(\mathbb{N})$, and $T$ is strong enough to talk about Turing machines (I'm almost certain containing Robinson arithmetic is enough, but I could be wrong, I don't know much about it). Then we have, for any Turing machine $\Phi_e$, $$\Phi_e(e)\text{ halts}\iff e\in 0'\iff T\vdash\text{"$\Phi_e(e)$ halts"}.$$ But the statement "$\Phi_e(e)$ halts" is equivalent mod $T$ (in fact, mod Robinson arithmetic) to the existence of a root of a polynomial $p_e$, and the passage from $e$ to $p_e$ is computable. So if $D_T$ were decidable, $0'$ would be computable.

Note that we did not assume that $T$ was computably axiomatizable!

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331