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

Question

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?

Answer 1

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.)

Answer 2

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.