Truth‐table Schnorr randomness and truth‐table reducible randomness

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth‐table Schnorr randomness (defined in 6 too only by martingales) and truth‐table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth‐table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth‐table Schnorr randomness. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

On measures ergodic with respect to an analytic equivalence relation

In this paper, we prove that the set of probability measures which are ergodic with respect to an analytic equivalence relation is an analytic set. This is obtained by approximating analytic equivalence relations by measures, and is used to give an elementary proof of an ergodic decomposition theorem of Kechris.

     

Conditional computability of real functions with respect to a class of operators

For any class of operators which transform unary total functions in the set of natural numbers into functions of the same kind, we define what it means for a real function to be uniformly computable or conditionally computable with respect to this class. These two computability notions are natural generalizations of certain notions introduced in a previous paper co-authored by Andreas Weiermann and in another previous paper by the same authors, respectively. Under certain weak assumptions about the class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. The introduced notions have some similarity with the uniform computability and its non-uniform extension considered by Katrin Tent and Martin Ziegler, however, there are also essential differences between the conditional computability and the non-uniform computability in question.     

Algorithmic randomness over general spaces

The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT₃ is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition.     

Computable randomness and betting for computable probability spaces

Unlike Martin‐Löf randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting “bit‐wise” definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness—endomorphism randomness—which the author hopes will shed light on the open question of whether Kolmogorov‐Loveland randomness is equivalent to Martin‐Löf randomness. The last section contains ideas for future research.     

Orthogonal measures and ergodicity

Burgess-Mauldin have proven the Ramsey-theoretic result that continuous sequences \({\left( {{\mu _c}} \right)_{c \in {2^\mathbb{N}}}}\) of pairwise orthogonal Borel probability measures admit continuous orthogonal subsequences. We establish an analogous result for sequences indexed by 2^N/E⁰, the next Borel cardinal. As a corollary, we obtain a strengthening of the Harrington-Kechris-Louveau E₀ dichotomy for restrictions of measure equivalence. We then use this to characterize the family of countable Borel equivalence relations which are non-hyperfinite with respect to an ergodic Borel probability measure which is not strongly ergodic.     

How much randomness is needed for statistics?

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle (which we call the “classical approach”). The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ (we call this approach “Hippocratic”). While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

Effectiveness in RPL, with applications to continuous logic

In this paper, we introduce a foundation for computable model theory of rational Pavelka logic (an extension of ?ukasiewicz logic) and continuous logic, and prove effective versions of some related theorems in model theory. We show how to reduce continuous logic to rational Pavelka logic. We also define notions of computability and decidability of a model for logics with computable, but uncountable, set of truth values; we show that provability degree of a formula with respect to a linear theory is computable, and use this to carry out an effective Henkin construction. Therefore, for any effectively given consistent linear theory in continuous logic, we effectively produce its decidable model. This is the best possible, since we show that the computable model theory of continuous logic is an extension of computable model theory of classical logic. We conclude with noting that the unique separable model of a separably categorical and computably axiomatizable theory (such as that of a probability space or an L^p Banach lattice) is decidable.     

Weakly precomplete computably enumerable equivalence relations

Using computable reducibility ? on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ₃‐complete, whereas the index set of the weakly precomplete ceers is Π₃‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ₃‐complete.     

Logic and probabilistic systems

Following some ideas of Roberto Magari, we propose trial and error probabilistic functions, i.e. probability measures on the sentences of arithmetic that evolve in time by trial and error. The set of the sentences that get limit probability 1 is a theory, in fact can be a complete set. We prove incompleteness results for this setting, by showing for instance that for every there are true sentences that get limit probability less than . No set as above can contain the set of all true sentences, although we exhibit some containing all the true sentences. We also consider an approach based on the notions of inner probability and outer probability, and we compare this approach with the one based on trial and error probabilistic functions. Although the two approaches are shown to be different, we single out an important case in which they are equivalent. Received March 20, 1995     

Algorithmic tests and randomness with respect to a class of measures

This paper offers some new results on randomness with respect to classes of measures, along with a didactic exposition of their context based on results that appeared elsewhere. We start with the reformulation of the Martin-Löf definition of randomness (with respect to computable measures) in terms of randomness deficiency functions. A formula that expresses the randomness deficiency in terms of prefix complexity is given (in two forms). Some approaches that go in another direction (from deficiency to complexity) are considered. The notion of Bernoulli randomness (independent coin tosses for an asymmetric coin with some probability p of head) is defined. It is shown that a sequence is Bernoulli if it is random with respect to some Bernoulli measure B _p . A notion of “uniform test” for Bernoulli sequences is introduced which allows a quantitative strengthening of this result. Uniform tests are then generalized to arbitrary measures. Bernoulli measures B _p have the important property that p can be recovered from each random sequence of B _p . The paper studies some important consequences of this orthogonality property (as well as most other questions mentioned above) also in the more general setting of constructive metric spaces.     

Fuzzy Optimization Problems Based on Ordering Cones

The solution concepts of the fuzzy optimization problems using ordering cone (convex cone) are proposed in this paper. We introduce an equivalence relation to partition the set of all fuzzy numbers into the equivalence classes. We then prove that this set of equivalence classes turns into a real vector space under the settings of vector addition and scalar multiplication. The notions of ordering cone and partial ordering on a vector space are essentially equivalent. Therefore, the optimality notions in the set of equivalence classes (in fact, a real vector space) can be naturally elicited by using the similar concept of Pareto optimal solution in vector optimization problems. Given an optimization problem with fuzzy coefficients, we introduce its corresponding (usual) optimization problem. Finally, we prove that the optimal solutions of its corresponding optimization problem are the Pareto optimal solutions of the original optimization problem with fuzzy coefficients.     

Is the Mandelbrot set computable?

This work is concerned with the question whether the Mandelbrot set is computable. The computability notions that we consider are studied in computable analysis and will be introduced and discussed. We show that the exterior of the Mandelbrot set, the boundary of the Mandelbrot set, and the hyperbolic components satisfy certain natural computability conditions. We conclude that the two‐sided distance function of the Mandelbrot set is computable if the famous hyperbolicity conjecture is true. We also formulate the question whether the distance function of the Mandelbrot set is computable in terms of the escape time. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Urbanik generalized convolutions in the non-commutative probability and a forgotten method of constructing generalized convolution

The paper deals with the notions of weak stability and weak generalized convolution with respect to a generalized convolution, introduced by Kucharczak and Urbanik. We study properties of such objects and give examples of weakly stable measures with respect to the Kendall convolution. Moreover, we show that in the context of non-commutative probability, two operations: the q-convolution and the (q,1)-convolution satisfy the Urbanik??s conditions for a generalized convolution, interpreted on the set of moment sequences. The weak stability reveals the relation between two operations.     

Relations on words

In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation.In the second part, we mainly focus on abelian equivalence, $k$-abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and $M$-equivalence. In particular, some new refinements of abelian equivalence are introduced.     

Paradox,programming, and learning probability: A case study in a connected mathematics framework

Formal methods abound in the teaching of probability and statistics. In the Connected Probability project, we explore ways for learners to develop their intuitive conceptions of core probabilistic concepts. This article presents a case study of a learner engaged with a probability paradox. Through engaging with this paradoxical problem, she develops stronger intuitions about notions of randomness and distribution and the connections between them. The case illustrates a Connected Mathematics approach: that primary obstacles to learning probability are conceptual and epistemological; that engagement with paradox can be a powerful means of motivating learners to overcome these obstacles; that overcoming these obstacles involves learners making mathematics—not learning a “received” mathematics and that, through programming computational models, learners can more powerfully express and refine their mathematical understandings.     

Randomness notions and partial relativization

We study the computational complexity of an oracle set using a number of notions of randomness that lie between Martin-L?f randomness and 2-randomness in terms of strength. These notions are weak 2-randomness, weak randomness relative to ???, Demuth randomness and Schnorr randomness relative to ???. We characterize the oracles A such that ML[A] ? C, where C is such a randomness notion and ML[A] denotes the Martin-L?f random reals relative to A, using a new meta-concept called partial relativization. We study the reducibility associated with weak 2-randomness and relate it with LR-reducibility.     

Rings Defined by Extensions

In this article, we study subrings of the Ext-algebra of a graded module over a graded ring R. We show these subrings can be defined by equivalence relations on exact sequences over the ring. In particular, the shriek ring, R ^!, and the even part of an Ext-algebra of a d-Koszul algebra can be defined by equivalence relations on exact sequences.