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?



Can a stochastic Turing machine output a consistent extension of PA with positive probability?
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.)


