10 found
Order:
  1.  23
    Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  2.  21
    The Kolmogorov-Loveland Stochastic Sequences Are Not Closed Under Selecting Subsequences.Wolfgang Merkle - 2003 - Journal of Symbolic Logic 68 (4):1362-1376.
    It is shown that the class of Kolmogorov-Loveland stochastic sequences is not closed under selecting subsequences by monotonic computable selection rules. This result gives a strong negative answer to the question whether the Kolmogorov-Loveland stochastic sequences are closed under selecting sequences by Kolmogorov-Loveland selection rules, i.e., by not necessarily monotonic, partial computable selection rules. The following previously known results are obtained as corollaries. The Mises-Wald-Church stochastic sequences are not closed under computable permutations, hence in particular they form a strict superclass (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  3.  13
    Constructive Equivalence Relations on Computable Probability Measures.Laurent Bienvenu & Wolfgang Merkle - 2009 - Annals of Pure and Applied Logic 160 (3):238-254.
    A central object of study in the field of algorithmic randomness are notions of randomness for sequences, i.e., infinite sequences of zeros and ones. These notions are usually defined with respect to the uniform measure on the set of all sequences, but extend canonically to other computable probability measures. This way each notion of randomness induces an equivalence relation on the computable probability measures where two measures are equivalent if they have the same set of random sequences. In what follows, (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  4. On the Construction of Effectively Random Sets.Wolfgang Merkle & Nenad Mihailović - 2004 - Journal of Symbolic Logic 69 (3):862-878.
    We present a comparatively simple way to construct Martin-Löf random and rec-random sets with certain additional properties, which works by diagonalizing against appropriate martingales. Reviewing the result of Gács and Kučera, for any given set X we construct a Martin-Löf random set from which X can be decoded effectively. By a variant of the basic construction we obtain a rec-random set that is weak truth-table autoreducible and we observe that there are Martin-Löf random sets that are computably enumerable self-reducible. The (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  5.  11
    Conference on Computability, Complexity and Randomness, Isaac Newton Institute, Cambridge, UK, July 2–6, 2012.Elvira Mayordomo & Wolfgang Merkle - 2013 - Bulletin of Symbolic Logic 19 (1):135-136.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  10
    Being Low Along a Sequence and Elsewhere.Wolfgang Merkle & Liang Yu - 2019 - Journal of Symbolic Logic 84 (2):497-516.
    Let an oracle be called low for prefix-free complexity on a set in case access to the oracle improves the prefix-free complexities of the members of the set at most by an additive constant. Let an oracle be called weakly low for prefix-free complexity on a set in case the oracle is low for prefix-free complexity on an infinite subset of the given set. Furthermore, let an oracle be called low and weakly for prefix-free complexity along a sequence in case (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  18
    Conference on Computability, Complexity and Randomness: Isaac Newton Institute, Cambridge, Uk July 2-6, 2012.Elvira Mayordomo & Wolfgang Merkle - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    Elvira Mayordomo and Wolfgang Merkle The Bulletin of Symbolic Logic, Volume 19, Issue 1, Page 135-136, March 2013.
    Direct download  
     
    Export citation  
     
    Bookmark  
  8.  5
    Chaitin’s Ω as a Continuous Function.Rupert Hölzl, Wolfgang Merkle, Joseph Miller, Frank Stephan & Liang Yu - 2020 - Journal of Symbolic Logic 85 (1):486-510.
    We prove that the continuous function${\rm{\hat \Omega }}:2^\omega \to $ that is defined via$X \mapsto \mathop \sum \limits_n 2^{ - K\left} $ for all $X \in {2^\omega }$ is differentiable exactly at the Martin-Löf random reals with the derivative having value 0; that it is nowhere monotonic; and that $\mathop \smallint \nolimits _0^1{\rm{\hat{\Omega }}}\left\,{\rm{d}}X$ is a left-c.e. $wtt$-complete real having effective Hausdorff dimension ${1 / 2}$.We further investigate the algorithmic properties of ${\rm{\hat{\Omega }}}$. For example, we show that the maximal (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  10
    Exact Pairs for Abstract Bounded Reducibilities.Wolfgang Merkle - 1999 - Mathematical Logic Quarterly 45 (3):343-360.
    In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤r between subsets of the natural numbers, where ≤r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  6
    Generality’s Price: Inescapable Deficiencies in Machine-Learned Programs.John Case, Keh-Jiann Chen, Sanjay Jain, Wolfgang Merkle & James S. Royer - 2006 - Annals of Pure and Applied Logic 139 (1):303-326.
    This paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark