Skip to main content
1 of 2
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Let $TA$ be the theory of true arithmetic, that is, the set of all truths of the usual standard model of arithmetic $\langle\mathbb{N},+,\cdot,0,1,<\rangle$. It is a theorem of ZFC that TA is consistent and sound for arithmetic truth, since for a theory to be sound means precisely that it agrees with $TA$.

Meanwhile, the theory TA proves all and only the true instances of halting and non-halting, so every instance of the halting problem or indeed any arithmetic question is correctly settled by the theory TA, by definition.

Probably you don't find this answer satisfactory, because we can't so easily tell what are the axioms of TA. But in this case, my response is that there will be no satisfactory answer for you. There can be no assignment of every instance $p$ of the halting problem to a sound consistent theory $T_p$ that settles the question of whether $p$ halts or not. The reason is that if we could compute this map $p\mapsto T_p$, then we could solve the halting problem: on input $T_p$, start enumerating all proofs in the theory $T_p$ until you find one solving whether $p$ halts or not.

We can't even have a computable procedure by which from $p$ we can gradually enumerate the axioms of $T_p$, since from any such procedure we can still enumerate all proofs from $T_p$.

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k