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 well known theorem of 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. 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.

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.

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 well known theorem of 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. 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 $W$ 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.

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 well known theorem of 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. 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.