WWW.DISSERTATION.XLIBX.INFO FREE ELECTRONIC LIBRARY - Dissertations, online materials

<< HOME
CONTACTS

Pages:   || 2 |

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

-- [ Page 1 ] --

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.

Pages:   || 2 |

Similar works:

«Departamento de Geociências Laboratório de Pesquisas Urbanas e Regionais Simpósio Nacional sobre Geografia, Percepção e Cognição do Meio Ambiente HOMENAGEANDO LÍVIA DE OLIVEIRA |Londrina 2005| Londrina-Imagens, Paisagens & Personagens um Olhar Geográfico pelo Atlas Digital Lúcia Helena Batista Gratão Geógrafa, Profa. DGEO/UEL lugratao@uel.br Rosely Sampaio Archela Geógrafa, Profa. DGEO/UEL roarchela@uel.br Mírian Vizintim F. Barros Geógrafa, Profa. DGEO/UEL vizintim@uel.br Omar...»

«Contiki Holidays USA & Canada 2013 2015 America, Canada, Mexico & Hawaii 2013/15 ONE LIFE ONE SHOT SO MAKE IT COUNT THE ORIGINAL SINCE '62 Welcome to Contiki. You’re about to head out on the adventure of a lifetime & experience the way we travel. We can’t wait to show you our Backstage Pass to the USA & Canada. Here at Contiki, we’re a bunch of passionate travellers like you, so we know all the top tips that you need to know before & during your trip. We’ve put together this handy (&...»

«INL/EXT-09-16715 A Comparison of Modifications to MELCOR Versions 1.8.2 and 1.8.6 for ITER Safety Analysis Brad J. Merrill Paul W. Humrickhouse Richard L. Moore June 2010 The INL is a U.S. Department of Energy National Laboratory operated by Battelle Energy Alliance INL/EXT-09-16715 A Comparison of Modifications to MELCOR Versions 1.8.2 and 1.8.6 for ITER Safety Analysis Brad J. Merrill Paul W. Humrickhouse Richard L. Moore June 2010 Idaho National Laboratory Fusion Safety Program Thermal...»

«Making Tax Digital: Transforming the tax system through the better use of information Consultation document Publication date: 15 August 2016 Closing date for comments: 7 November 2016 Subject of this This consultation focuses on how more effective use of third party consultation: information can contribute to the transformation of the tax system, as set out in the Making Tax Digital Roadmap. Scope of this There are two parts to this consultation: we are looking for views on consultation: both...»

«Glossary of Mining Terminology After Damp Gasses resulting from underground combustion, normally carbon monoxide. This is a loose term implying any fatal gas in a mine after an explosion or fire. Air Shaft A vertical opening into a mine for the passage of air. Airway Any passage in a mine along which an air current moves. Some passages are driven solely for air. Other passages, such as a main level, are all purpose, to move air, men, coal, and materials. Anthracite Coal of the highest...»

«DEPARTMENT OF THE TREASURY Office of the Comptroller of the Currency [Docket ID OCC-2013-0005] Proposed Guidance on Deposit Advance Products; Withdrawal of Proposed Guidance on Deposit-Related Consumer Credit Products AGENCIES: Office of the Comptroller of the Currency, Treasury (OCC). ACTION: Proposed guidance with request for comment; withdrawal of proposed Guidance on Deposit-Related Consumer Credit Products. SUMMARY: The OCC is proposing guidance on safe and sound banking practices and...»

«Public Disclosure Authorized 27584 T his book was written as part of the work of the Public Expenditure and Financial Accountability (PEFA) Program, a partnership of the World Bank; the European Commission; the International Monetary Fund; the Strategic Partnership with Africa; and several bilateral donor agencies, Assessing including those of France, Norway, Switzerland, and the United Kingdom. This study compares and contrasts the various instruments and approaches used by these organizations...»

«THE PUBLISHING OF ELECTRONIC SCHOLARLY MONOGRAPHS AND TEXTBOOKS C J Armstrong Centre for Information Quality Management Information Automation Limited, Penbryn, Bronant, Aberystwyth SY23 4TJ lisqual@cix.compulink.co.uk Ray Lonsdale Department of Information and Library Studies, University of Wales Aberystwyth Aberystwyth SY23 3AS rel@aber.ac.uk April 1998 ABSTRACT This eLib Supporting Study was conceived to investigate the incidence and nature of the publishing of electronic scholarly...»

«Gesprächsforschung Online-Zeitschrift zur verbalen Interaktion (ISSN 1617-1837) Ausgabe 12 (2011), Seite 190-198 (www.gespraechsforschung-ozs.de) Bericht über die 15. Arbeitstagung zur Gesprächsforschung vom 30. März 1. April 2011 in Mannheim Silke Reineke Aufgrund des gewachsenen gesprächsforscherischen Interesses an Aspekten wie 'Wissen', 'Intention' und 'Wahrnehmung' lautete das diesjährige Rahmenthema der 15. Arbeitstagung zur Gesprächsforschung am Institut für Deutsche Sprache...»

«REVELATION THE DIVINE CONSPIRACY REDISCOVERING OUR HIDDEN LIFE IN GOD DALLAS WILLARD R. R. Brown Joe Henry Hankins John R. Rice Lee Roberson J. I. Willard “In those days there were giants in the land.” The kingdom of the heavens is similar to a bit of yeast which a woman took and hid in half a bushel of dough. After a while all the dough was pervaded by it. JESUS OF NAZARETH You must have often wondered why the enemy [God] does not make more use of his power to be sensibly present to human...»

«Official Newsletter of Rotary Club of Manila balita No. 3614, August 20, 2015 GUEST OF HONOR AND SPEAKER THE ROTARY CLUB OF MANILA BOARD OF DIRECTORS and Executive Officers 2015-2016 EBOT TAN President FRANK EVARISTO Immediate Past President TEDDY OCAMPO Vice President RAFAEL M. GARCIA, III SUSING PINEDA Past District Governor ISSAM ELDEBS Rotary International District 3800 AMADING VALDEZ BOBBY JOSEPH NING LOPEZ OSCAR DEL ROSARIO KABALITA Directors Beauty and charity have found a home in...»

«State of Affairs of Higher Education in Costa Rica Master, Sandra Palacios Palacios Universidad Nacional, Costa Rica samypalaces@yahoo.com San José, Costa Rica. Phone (506) 83484830 Master, Yalile Jiménez Olivares Universidad Nacional, Costa Rica yalilej@gmail.com San José, Costa Rica. Phone (506) 83430341 Abstract Higher education in Costa Rica is composed of two main subsystems: parauniversity and university. Parauniversity higher education focuses on short term careers of only two or...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.