# «Abstract A nonconstructive proof can be used to prove the existence of an object with some properties without providing an explicit example of such ...»

Probabilistic Constructions of Computable Objects

and a Computable Version of Lovász Local Lemma.

Andrei Rumyantsev, Alexander Shen*

January 17, 2013

Abstract

A nonconstructive proof can be used to prove the existence of an object with

some properties without providing an explicit example of such an object. A special

case is a probabilistic proof where we show that an object with required properties

appears with some positive probability in some random process. Can we use such

**arguments to prove the existence of a computable inﬁnite object? Sometimes yes:**

following [8], we show how the notion of a layerwise computable mapping can be used to prove a computable version of Lovász local lemma.

1 Probabilistic generation of inﬁnite sequences We want to show that one can use probabilistic arguments to prove the existence of iniﬁnite objects (say, inﬁnite sequences of zeros and ones) with some properties. So we should discuss ﬁrst in which sense a probabilistic algorithm can generate such a sequence.

The most natural approach: consider a Turing machine that has an output write-only tape where it can print bits sequentially. Using fair coin tosses, the machine generates a (ﬁnite or inﬁnite) sequence of output bits. The output distribution of such a machine T is some probability distribution Q on the set of all ﬁnite and inﬁnite sequences. Distributions of this class are determined by their values on cones Σx (of all ﬁnite and inﬁnite extensions of a binary string x). The function q(x) = Q(Σx ) that corresponds to the measure Q

**satisﬁes the following conditions:**

q(x) ≥ q(x0) + q(x1) for all strings x.

q(Λ) = 1;

(Here Λ denotes the empty string.) Any non-negative real function that satisﬁes these conditions corresponds to some probability distribution on the set of ﬁnite and inﬁnite binary sequences. The output distributions of probabilistic machines correspond to functions q that are lower semicomputable; this means that some algorithm, given a binary string x, computes a non-decreasing sequence of rational numbers that converges to q(x).

Now we are ready to look at the classical result of de Leeuw – Moore – Shannon – Shapiro: if some individual sequence ω appears with positive probability as an output of a probabilistic Turing machine, this sequence is computable. Indeed, let this probability be * LIRMM CNRS & UM 2, Montpellier; on leave from IITP RAS, Moscow. Supported by ANR NAFITgrant. E-mail: azrumuyan@gmail.com, alexander.shen@lirmm.fr some ε 0; take a rational threshold r such that r ε 2r, and consider some preﬁx w of ω such that q(w) 2r. (Such a preﬁx exists, since q(x) for preﬁxes of ω converges to ε.) Startingfrom w, we can compute the next preﬁx of ω by ﬁnding a son where q exceeds r. The correct son satisﬁes this condition, and no branching is possible: if for two sons the value exceeds r, then it should exceed 2r for the father.

This result can be interpreted as follows: if our task is to produce some speciﬁc inﬁnite sequence of zeros and ones, randomization does not help (at least if we ignore the computational resources). However, if our goal is to produce some sequence with required properties, randomization can help. A trivial example: to produce a noncomputable sequence with probability 1 it is enough to output the random bits.

All these observations are well known, see, e.g., the classical paper of Zvonkin and Levin [9]. For a less trivial example, let us consider another result (proved by N.V. Petri) mentioned in this paper: there exists a probabilistic machine that with positive probability generates a sequence ω such that (1) ω contains inﬁnitely many ones; (2) the function i → the position of i-th one in ω has no computable upper bound. (In the language of recursion theory, this machine generates with positive probability a characteristic sequence of a hyperimmune set.) A nice proof of this result was given by Peter Gacs; it is reproduced in the next section (we thank M. Bondarko for some improvements in the presentation).

2 Fireworks and hyperimmune sequences Consider the following “real-life” problem. We come to a shop where ﬁreworks are sold.

After we buy one, we can test it in place (then we know whether it was good or not, but it is not usable anymore, so we have to buy a new one after that), or go home, taking the untested ﬁrework with us. We look for a probabilistic strategy that with 99% probability either ﬁnds a bad ﬁrework during the testing (so we can sue the shop and forget about the ﬁreworks) or takes home a good one.

Solution: take a random number k in 0..99 range, make k tests (less if the failure happens earlier); if all k tested ﬁreworks were good, take home the next one. The seller does not get any information from our behavior: he sees only that we are buying and testing the ﬁreworks; when we take the next one home instead of testing, it is too late for him to do anything. So his strategy is reduced to choosing some number K of good ﬁreworks sold before the bad one. He wins only if K = k, i.e., with probability at most 1%.

Another description of the same strategy: we take the ﬁrst ﬁrework home with probability 1/100 and test it with probability 99/100; if it is good, we take the second one with probability 1/99 and test it with probability 98/99, etc.

Why this game is relevant? Assume we have a program of some computable function f and want to construct probabilistically a total function g not bounded by f if f is total.

(It is convenient to consider a machine that constructs a total integer-valued function and then use this function to determine the numbers of zeros between consecutive ones.) We consider f (0), f (1),... as “ﬁreworks”; f (i) is a good one if computation f (i) terminates.

First we buy f (0); with probability 1/100 we “take” it and with probability 99/100 we “test” it. Taking f (0) means that we run this computation until it terminates and then let g(0) := f (0) + 1. If this happens, we may relax and let all the other values of g be zeros.

(If the computation does not terminate, i.e., if we take a bad ﬁrework, we are out of luck.) Testing f (0) means that we run this computation and at the same time let g(0) := 0, g(1) := 0, etc. until the computation terminates. If f (0) is undeﬁned, g will be zero function, and this is OK since we do not care about non-total f. But if f (0) is deﬁned, at some point testing stops, we have some initial fragment of zeros g(0), g(1),..., g(u), and then consider f (u + 1) as the next ﬁrework bought and test [take] it with probability 98/99 [resp. 1/99]. For example, if we decide to test it, we run the computation f (u + 1) until it terminates, and then let g(u + 1) := f (u + 1) + 1. And so on.

In this way we can beat one computable function f with probability arbitrarily close to 1. To construct with positive probability a function not bounded by any total computable function, we consider all the functions as functions of two natural arguments (tables), and use ith row to beat ith potential upper bound with probability 1 − ε2−i. To beat the upper bound, it is enough to beat it in some row, so we can deal with all the ∑ rows in parallel, and get error probability at most ε i 2−i = ε.

3 Computable elements of closed sets Let us return now to the original question: can we use probabilistic arguments to construct a computable sequence with some property? As we have seen, if we are able to construct a probabilistic machine that generates some speciﬁc sequence with positive probability, we can then conclude that this speciﬁc sequence is computable. However, we do not know arguments that follow this scheme, and it is diﬃcult to imagine how one can describe a speciﬁc sequence that it is actually computable, and prove that it has positive probability — without actually constructing an algorithm that computes it.

**Here is another statement that may be easier to apply:**

Proposition 1. If F is some closed set of inﬁnite sequences, and if output of some probabilistic machine belongs to F with probability 1, then F contains a computable element.

Proof. Indeed, consider the output distribution and take a computable branch along which the probabilities remains positive (this is possible since the measure function is lower semicomputable). We get some computable sequence ω. If ω ∈ F, then some preﬁx of / ω has no extensions in F (recall that F is closed). This preﬁx has positive probability by construction, so our machine cannot generate elements in F with probability 1. This contradiction shows that ω ∈ F.

In the following sections we give a speciﬁc example when this approach (in a signiﬁcantly modiﬁed form) can be used.

4 Lovász Local Lemma Let X be a sequence of mutually independent random variables; each variable has a ﬁnite range. (In the simplest case xi are independent random bits.) Consider some family A of forbidden events; each of them depends on a ﬁnite set of variables, denoted vbl(A) (for an event A). Informally speaking, Lovász Local Lemma (LLL) guarantees that forbidden events do not cover the entire probability space if each of them has small probability and the dependence between the events (caused by common variables) is limited.

To make the statement exact, we need to introduce some terminology and notation.

Two events A and B are disjoint if they do not share variables, i.e., if vbl(A)∩vbl(B) = ∅.

For every A ∈ A let Γ(A) be the open (punctured) neighborhood of A, i.e., the set of all events E ∈ A that have common variables with A, except for A itself.

for all A ∈ A. Then there exists an assignment that avoids all the forbidden events A ∈ A.

Proof. This is just a combination of ﬁnite LLL and compactness argument. Indeed, each event from A is open the the product topology; if the claim is false, these events cover the entire (compact) product space, so there exists a ﬁnite subset of events that covers the entire space, which contradicts the ﬁnite LLL.

Our goal is to make this theorem eﬀective. To formulate the computable version of LLL, assume that we have a countable sequence of independent random variables X = x0, x1,..., the range of xi is {0, 1,..., ni − 1}, and ni and the probability distribution of xi is computable given i. Then we consider a sequence of events, A = {A0, A1,...}. We assume that these events are eﬀectively presented, i.e., for a given j one can compute the list of all the variables in vbl(Aj ), and the event itself (i.e., the list of tuples that belong to that event). Moreover, we assume that for each variable xi only ﬁnitely many events involve this variable, and the list of those events can be computed given i.

Theorem 1 (Computable version of LLL). Suppose there is a rational constant ε ∈ (0, 1) and a computable assignment of rational numbers x : A → (0, 1) such that ∏ Pr[A] ≤ (1 − ε)x(A) (1 − x(E)), E∈Γ(A) for all A ∈ A. Then there exists a computable assignment that avoids all A ∈ A.

Note that the computability restrictions look quite naturally and that we only need to make the upper bounds for probability just a bit stronger (adding some constant factor 1 − ε). It should not be a problem for typical applications of LLL; usually this stronger bound on Pr[A] can be easily established.

This theorem is the main result of the paper (it was published as an arxiv prepint [8]).

To prove it we use Proposition 1 and construct a computable probability distribution on inﬁnite sequences such that every forbidden event A ∈ A has zero probability. The construction of this distribution is based on the Moser–Tardos probabilistic algorithm [4] for ﬁnding an assignment that avoids all the bad events in the ﬁnite version of LLL.

However, we need ﬁrst to extend the class of probabilistic machines.

5 Rewriting machines and layerwise computability Now we change the computational model and make the output tape rewritable: the machine can change several times the contents of a cell, and only the last value matters.

(We may assume that ith cell may contain integers in 0... ni − 1 range, and that initially all cells contain zeros.) The last value is deﬁned if a cell changes its value ﬁnitely many times during the computation. Of course, for some values of random bits it may happen that some cell gets inﬁnitely many changes. We say that the output sequence of the machine is not deﬁned in this case.

If the output sequence is deﬁned with probability 1, we get an almost everywhere deﬁned mapping from Cantor space (of random coin sequences) into the space of all assignments (input sequence is mapped to the limit output sequence). This mapping deﬁnes the output distribution on the assignments (the image of the uniform distribution on fair coin bits). This distribution may be not computable (e.g., for every lower semicomputable real α it is easy to generate 0000... with probability α and 1111... with probability 1−α).

However, we get a computable output distribution if we impose some restrictions on the machine.

The restriction: for every output cell i and for every rational δ 0 one can eﬀectively compute integer N = N (i, δ) such that the probability of the event “the contents of cell i changes after step N ”, taken over all possible random bit sequences, is bounded by δ.

Proposition 4. In this case the limit content of the output is well deﬁned with probability 1, and the output distribution on the sequences of zeros and ones is computable.

Proof. Indeed, to approximate the probability of the event “output starts with z” for a sequence z of length k with error at most δ, we ﬁnd N (i, δ/k) for k ﬁrst cells (i.e., for i = 0, 1,..., k − 1). Then we take n greater than all these values of N and simulate ﬁrst n steps of the machine for all possible combinations of random bits.