It is a classical result of computability theory that there is a computable infinite binary tree $T\subset 2^{<\omega}$ with no computable infinite branch.

One way to construct such a tree is to fix a pair $A$, $B$ of computably inseparable c.e. sets, and to consider the tree of attempts to find a separation of them. Thus, a finite binary sequence of length $n$ is in the tree, if the set it describes forms a separation of the numbers that have been enumerated into $A$ and $B$ by stage $n$, that is, containing all such numbers from the stage $n$ approximation to $A$ and none from the stage $n$ approximation to $B$. This tree is computable, but any computable branch would provide a computable separation, contrary to hypothesis.

My question is whether a probabilistic Turing machine can have a non-zero chance to find a branch through $T$. Let us consider a probabilistic model of Turing machines where the Turing machine program transitions are given by computable probabilities on the outcome of each step, rather than single-value determistic outcomes.

**Question 1.** If a computable infinite binary tree has a probabilistic
algorithm for producing a branch with non-zero probability, then
must it have a computable infinite branch?

In other words, if a computable tree has no computable branch, then must it also admit no probabilistic algorithm to find a branch with non-zero probability?

One can imagine following the greedy algorithm, say, and deterministically following the most likely outcome at each step. But it is easy to see that this won't always work, since we can easily design a tree for which such a move leads to a dead part of the tree on the first move. To turn the probabilistic algorithm into an actual computable branch, we have to imagine that the probabilistic algorithm will often be producing different branches.

One can also imagine trying to use the probabilistic algorithm by running it far ahead until one sees that a certain accumulation of probability, based on a comparison to the fixed probability of success, means that certain choices are good choices. But I haven't yet been able to make this idea work.

The question above is asking whether the property of having no computable branches is the same as having no probabilistic algorithm for producing branches with non-zero probability. But a weaker question would be:

**Question 2.** Is there a computable infinite binary tree with no
probabilistic algorithm for computing an infinite branch with non-zero
probability?

That is, can we strengthen the classical result from no-computable-branches to produce a computable tree with no probabilistic algorithm for producing branches? I expect that we can.

These question arose from the discussion thread on a post of John Baez's concerning infinite chess.