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.
Best Answer
No, we can construct a computable tree with no computable paths such that there is a probabilistic Turing machine which with nonzero probability constructs a path.
The basic idea is this: kill off a small-measure subset of $2^\omega$ containing all computable reals, and pick our branch completely at random (so that our probability of success is exactly the measure of the complement of the set we kill off).
Here's one way to do it. Call a sequence $\sigma\in 2^{<\omega}$ dangerous if for some $e$, we have $\Phi_e(n)[\vert\sigma\vert]\downarrow=\sigma(n)$ for all $n<4^e$. Note that the set of dangerous strings is computable, and that every infinite computable sequence extends a dangerous string.
Now let $T$ be the tree of all non-dangerous strings, and use the probabilistic Turing machine which simply picks a random extension without thinking at all. Since the function $e\mapsto 4^e$ grows sufficiently fast, we have a positive probability of getting a path. However, $T$ clearly has no computable paths.
Re: question $2$, I don't have an answer but here's a quick observation: we can defeat the coin-flipping algorithm. (I suspect the answer to 2 is yes, by diagonalizing against probabilistic Turing machines - kill nodes to shrink the measure of branches built by a given machine - but I don't immediately see the details.)
Say $\sigma$ is risky if for some $e$, we have
$\Phi_e(2^n)[\vert\sigma\vert]\downarrow=\sigma(2^n)$ for all $n<4^e$, or
for some $m$ not of the form $2^k$ we have $\sigma(m)\not=1$ (say).
Again, take the tree of non-risky strings. Note that every computable sequence extends a risky string, so this tree has no computable paths, and every sequence with only non-risky initial segments has asymptotic-density-$1$ many $1$s, so the set of paths is null.