Skip to main content
1 of 5
Christopher King
  • 6.4k
  • 1
  • 32
  • 60

Lowest Turing degree that allows a Turing machine to tell whether $Con(PA)$?

Let $T$ be a turing machine. We say that $T$ decides $Con(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { rejects}$ (in any case, $PA \vdash T \text{ halts}$ by cases). What is the minimal Turing degree(s) that allow such a $T$ to exist?

It is clear that is $\le 0'$. Simply ask the oracle "Does the machine that looks for the $n$ encoding $PA \vdash 0=1$ halt?". I do not think $0'$ is the lowest such degree though.

Christopher King
  • 6.4k
  • 1
  • 32
  • 60