17
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Why on earth is there a vote to close? $\endgroup$ – Noah Schweber Dec 30 '17 at 15:03
  • 1
    $\begingroup$ Do we know what the answer is if we just consider the sequence of coin flips? That is, is there a computable tree with no computable branch but with the set of branches of nonzero Lebesgue measure? $\endgroup$ – Wojowu Dec 30 '17 at 15:11
  • 1
    $\begingroup$ @Wojowu Yup - see my answer. $\endgroup$ – Noah Schweber Dec 30 '17 at 15:12
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This can be extended to a tree with the set of branches of measure arbitrarily close to $1$. Is it possible to get the measure to be exactly $1$? $\endgroup$ – Wojowu Dec 30 '17 at 15:14
  • $\begingroup$ @Wojowu No - remember that the only closed subset of $2^\omega$ with measure $1$ is $2^\omega$ itself. So this isn't a computability-theoretic barrier, just a topological barrier: the set of paths through a binary tree is always a closed subset of $2^{\omega}$ $\endgroup$ – Noah Schweber Dec 30 '17 at 15:14
  • $\begingroup$ Right, of course the set has to be closed. Thanks. $\endgroup$ – Wojowu Dec 30 '17 at 15:20
  • $\begingroup$ Great! This seems to dispatch question 1. (I assume that your square brackets mean that you run the computaton for only at most that many steps?) $\endgroup$ – Joel David Hamkins Dec 30 '17 at 15:27
  • 1
    $\begingroup$ Although even that one isn't an answer - it only defeats the coin-flipping algorithm. GAH. I'm not sure what the answer is at the moment. Let me edit my answer ... $\endgroup$ – Noah Schweber Dec 30 '17 at 15:41
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you explain a little more fully why my question is equivalent to your formulation? I guess it is something like: the paths through my desired tree is your (lightface) $\Pi^0_1$ class, and to be Medvedev below would mean from elements of the second class, we can always compute a path through the tree; so the set of positive measure is somehow the runs through the probabilistic computation or something. $\endgroup$ – Joel David Hamkins Dec 30 '17 at 16:31
  • $\begingroup$ Yes, the paths through the tree is the $\Pi^0_1$-class; I've edited in an explanation of how it turns into Medvedev reducibility. $\endgroup$ – Dan Turetsky Dec 30 '17 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.