Skip to main content
5 of 5
deleted 206 characters in body
Christopher King
  • 6.4k
  • 1
  • 32
  • 60

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

Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{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 allows 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