For a computable binary tree, is having no computable branches the same as having no probabilistic algorithm for producing branches?

Question

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.

Answer 1

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.

Answer 2

For question 2, you're asking if there's a $\Pi^0_1$-class which is Medvedev-below no set of positive measure.

For an example, take the tree of completions of PA (or any other tree where every path has PA degree). No difference random computes a PA degree, so the unions of upper cones of paths contains no difference random, and thus is measure 0. So no positive measure set is Muchnik-above the paths through the tree, let alone Medvedev-above.

Edit: One class of reals is Medvedev above a second class if there is a Turing functional that sends any element of the first class to an element of the second class. One class is Muchnik above a second class if every element of the first class computes an element of the second class; in other words, it's like Medvedev reducibility, but different reals can use different functionals.

Your notion of probabilistic machines can be instead thought of as a deterministic machine that consults a random real given as an oracle to determine which transition to follow. At each step, it consults the real in a way that's independent of the way it checked at previous steps. So a positive probability of getting a path turns into a positive set of real oracles which give a path, and the machine witnesses a Medvedev reduction from this set to your set of paths.