1
$\begingroup$

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.

Improve this question
$\endgroup$
22
  • 2
    $\begingroup$ Oh, so we're talking about "$PA+Con(PA) \vdash$ The machine with code $n$ halts" etc? Thanks, that clears it up. $\endgroup$
    – Johannes Hahn
    Commented Apr 26, 2018 at 18:38
  • 1
    $\begingroup$ @JohannesHahn yep, sure thing. Sorry if it was unclear. $\endgroup$
    – Christopher King
    Commented Apr 26, 2018 at 18:40
  • 2
    $\begingroup$ Let me ignore that machine for a moment and ask the question I was really interested in: what does it mean for a degree to "allow a Turing machine to exist"? $\endgroup$
    – Carl Mummert
    Commented Apr 26, 2018 at 19:33
  • 2
    $\begingroup$ @PyRulez all oracles of the form you describe are computable, since they can be computed by brute force searching for proofs in PA. Since this provides an explicit computation of them, any Turing machine with oracle access to them may as well have no oracle. $\endgroup$
    – Alex Mennen
    Commented Apr 26, 2018 at 19:41
  • 2
    $\begingroup$ That's why the issue of encoding $\alpha$ into the formula matters. We can't actually write all the bits of an oracle in the formula, instead we have to write a definition of the oracle in the language of Peano arithmetic. But then that definition is likely to find a different set of natural numbers depending on which model of Peano arithmetic we look at. $\endgroup$
    – Carl Mummert
    Commented Apr 26, 2018 at 19:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .