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