Skip to main content
4 of 5
added 205 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.

EDIT: To clarify, you must define your degree $d$ in such a way that $k \in d$ is decidable in $PA$ for all $k \in \mathbb N$ (so the degree itself does not simply encode the $\operatorname{Con}(PA)$).

Christopher King
  • 6.4k
  • 1
  • 32
  • 60