# Can a stochastic Turing machine output a consistent extension of PA with positive probability?

Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel number $n$. (We can ignore bits when no sentence has number $n$, or we can choose an encoding which is an onto function; it doesn't matter.) By the first incompleteness theorem, it is not possible for any Turing machine given finite input to output a complete and consistent assignment in this way. On the other hand, it's quite possible for a Turing machine given infinite input to do so, since this allows an oracle to be constructed.

Supposing that we give a Turing machine random input, is it possible for the machine's output to be complete and consistent with nonzero probability? While this seems implausible, I haven't been able to disprove it yet.

To be precise, suppose that we take some machine $T$ and feed it fair coin-flips whenever it asks for additional input. The outcomes of the process are the states of the output tape, which will be either finite or infinite binary strings depending on whether the machine ever stops producing output. To define the probabilities, consider the $\sigma$-algebra generated by finite input-sets: for each finite binary string $b$, there is a set of possible outputs which could result from the first random bits being $b$. Each of these sets is measurable. The remaining measurable sets are generated from these by closure under countable union and complement.

Using this $\sigma$-algebra, the set of complete and consistent extensions to $PA$ is measurable, as follows. Each possible contradiction with $PA$ is a finite truth-value combination, which is measurable as the countable union of all inputs to $T$ which lead to that particular combination of truth-values. (This may be the empty set.) The set of all such contradictions is also countable, and therefore measurable. We can also measure the finite bit-strings, since these possibilities are countable. The union of these two measurable sets are the possibilities which are either inconsistent with $PA$ or finite; by closure under compliment, we can measure those which are both infinite and consistent with $PA$.

Can that measure be nonzero?

• "While this seems implausible" feels like understatement of the year... – Per Alexandersson Nov 21 '15 at 3:07
• Is it obvious that the answer is independent of the Gödel coding? – Andrej Bauer Nov 21 '15 at 16:45
• @Andrej Bauer The OP's two questions are not quite the same. The first one (roughly speaking) asks whether the class of sets that compute a completion of PA has measure 0. The second asks whether the set of completions of PA itself has measure 0. The answer to the second question could in principle depend on the coding. It turns out not to because the answer to the first question is positive. – Denis Hirschfeldt Nov 21 '15 at 23:30

The answer is no, but it's almost yes. A stochastic Turing machine can find a diagonally non-computable ($\textsf{DNC}$) function ($f$ with $f(x)\ne\varphi_x(x)$ for all $x$) and finding a complete extension of PA is equivalent to finding a $\textsf{DNC}$ function with $f(x)\in\{0,1\}$ for all $x$.

Antonin Kucera, in Measure, $\Pi^0_1$ classes, and complete extensions of PA, in Recursion Theory Week, Lecture Notes in Mathematics 1141, 245-259, showed that a stochastic TM cannot find any completion of PA. (The fact that it cannot find any given one, as in Carl Mummert's answer, was known earlier.)

• Thanks! Which Frank Stephan paper should I be looking at? – Abram Demski Nov 21 '15 at 21:43
• Actually, the fact that the class of sets that can compute a completion of PA has measure 0 was first proved by Antonin Kucera in Measure, $\Pi^0_1$ classes, and complete extensions of PA, in Recursion Theory Week, volume 1141 of Lecture Notes in Mathematics, 245-259. – Denis Hirschfeldt Nov 21 '15 at 23:04

Supposing that we give a Turing machine random input, is it possible for the machine's output to be complete and consistent with nonzero probability?

The answer is no. By a theorem due to de Leeuw, Moore, Shannon, and Shapiro (1956), which was later stated in this terminology by Sacks, if a real $x \in 2^\omega$ is computable from every real $y\in 2^\omega$ in a set of positive measure, then $x$ is already computable. (For references and background, see section 8.12 of Algorithmic Randomness and Complexity by Downey and Hirschfeldt).

Here the measure on $2^\omega$ is the standard fair-coin measure I will call $m$. No completion of PA is computable, so no completion of PA is computable from a set of oracles of positive measure.

The idea of the proof is that if $x$ is computable from a set of positive measure then there is an open subset $Z$ such that $x$ is uniformly computable from a subset $W$ of $Z$ such that $m(W) / m(Z) > 1/2$. But then we can compute $x$ up to any given precision by just enumerating computations from various elements of $Z$ until enough of them all give the same result (enough meaning more than $m(Z)/2$ of them).

The set of completions of PA is closed in $2^\omega$, so it has to be measurable. It is easy to see that the set of completions of PA has measure zero in $2^\omega$, because we can list a sequence of sentences $(\phi_n)$ such that $\text{PA} \vdash \phi_n$ for each $n$. Each condition of the form $\text{PA} \vdash \phi$ divides the measure of the set of completions by $2$, so the overall measure must be zero.

• The fact that, if a real is computable from every real in a set of positive measure, then it's computable is, as far as I know, proved, though with rather different teminology, in the paper (citation opied from MathSciNet): de Leeuw, K.; Moore, E. F.; Shannon, C. E.; Shapiro, N. Computability by probabilistic machines. Automata studies, pp. 183–212. Annals of mathematics studies, no. 34. Princeton University Press, Princeton, N. J., 1956. – Andreas Blass Nov 21 '15 at 11:13
• Thanks, Andreas. I had somehow learned the theorem as just due to Sacks. Fortunately Downey and Hirschfeldt state both versions. – Carl Mummert Nov 21 '15 at 15:06
• @Andreas Blass I think this is a slightly tricky theorem to credit. The paper you cite proves that if a set is c.e. relative to every real in a class of positive measure, then it is c.e. Of course, the analogous result for computable in place of c.e. is a one-line corollary, but I believe it was never stated in that paper. Later Sacks stated it explicitly and proved it, with essentially the same argument, though as far as I know without knowledge of the earlier paper. – Denis Hirschfeldt Nov 21 '15 at 19:19