Can a probabilistic Turing Machine compute an uncomputable number?

Question

Can a probabilistic Turing Machine compute an uncomputable number?

My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should add that I am pretty much ignorant of probabilistic TM and randomized algorithms. I looked at wikipedia, but may even have misunderstood what I read.

The reason I am asking that is that only the computable numbers can have their digits enumerated by a Turing Machine.

But with a probabilistic Turing Machine, I can enumerate any infinite sequence of digits, hence also sequences corresponding to non computable numbers.

Actually, since there are only countably many computable numbers, while there are uncountably many reals that can have their digit enumerated, I could say that my probabilistic Turing Machine can be made to enumerate the digits of a non computable number with probability 1.

I believe this can only be fallacious, but why? Is there a specific provision in the definition of probabilistic TM that prevents that?

Actually, I run into this by thinking whether various computation models can be simulated by a deterministic TM, in question "Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?". Another p[ossibly related question is "Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?".

Answer 1

Consider the following reasonable definition for a Turing machine computing an irrational number in $[0,1]$.

A Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, it outputs the first $n$ digits (after the decimal) of the binary representation of $r$.

One can think of many extensions of this definition for probabilistic Turing machines. Here is a very permissive one.

A probabilistic Turing machine computes an irrational $r \in [0,1]$ if, on input $n$, (1) it outputs the first $n$ digits of $r$ with probability $p$; (2) it outputs any other string with probability less than $p$; (3) it never halts with probability less than $p$.

Under this definition, it is not immediately clear whether everything that you can compute is indeed computable (under the sense of the first definition).

However, there are some modifications that do allow us to conclude that the resulting number is computable, for example:

1. We can insist that the machine always halt.
2. We can insist that $p > 1/2$.

Other modifications are not necessarily enough. For example, does it help if we assume that the non-halting probability tend to $0$ with $n$?

Summarizing, it might depend on the model.