Source author record

Christopher P. Porter

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO Logic in Computer Science

Catalog footprint

Research overview

10works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Randomness extraction in computability theory

In this article, we study a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We analyze several classes of extraction procedures: a first class that generalizes von Neumann's trick for extracting unbiased randomness from the tosses of a biased coin, a second class based on work of generating biased randomness from unbiased randomness by Knuth and Yao, and a third class independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For the first two classes of extraction procedures, we identify a level of algorithmic randomness for an input that guarantees that we attain the extraction rate along that input, while for the third class, we calculate the rate attained along sufficiently random input sequences.

preprint2021arXiv

The intersection of algorithmically random closed sets and effective dimension

In this article, we study several aspects of the intersections of algorithmically random closed sets. First, we answer a question of Cenzer and Weber, showing that the operation of intersecting relatively random closed sets (with respect to certain underlying measures induced by Bernoulli measures on the space of codes of closed sets), which preserves randomness, can be inverted: a random closed set of the appropriate type can be obtained as the intersection of two relatively random closed sets. We then extend the Cenzer/Weber analysis to the intersection of multiple random closed sets, identifying the Bernoulli measures with respect to which the intersection of relatively random closed sets can be non-empty. We lastly apply our analysis to provide a characterization of the effective Hausdorff dimension of sequences in terms of the degree of intersectability of random closed sets that contain them.

preprint2020arXiv

Key developments in algorithmic randomness

The goal of this introductory survey is to present the major developments of algorithmic randomness with an eye toward its historical development. While two highly comprehensive books and one thorough survey article have been written on the subject, our goal is to provide an introduction to algorithmic randomness that will be both useful for newcomers who want to develop a sense of the field quickly and interesting for researchers already in the field who would like to see these results presented in chronological order.

preprint2019arXiv

Rank and randomness

We show that for each computable ordinal $α>0$ it is possible to find in each Martin-Löf random $Δ^0_2$ degree a sequence $R$ of Cantor-Bendixson rank $α$ , while ensuring that the sequences that inductively witness $R$ 's rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.

preprint2016arXiv

Randomness for computable measures and initial segment complexity

We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on $2^ω$ , the so-called proper sequences. Our main results are as follows: (1) We show that the initial segment complexity of a proper sequence $X$ is bounded from below by a computable function (that is, $X$ is complex) if and only if $X$ is random with respect to some computable, continuous measure. (2) We prove that a uniform version of the previous result fails to hold: there is a family of complex sequences that are random with respect to a single computable measure such that for every computable, continuous measure $μ$ , some sequence in this family fails to be random with respect to $μ$ . (3) We show that there are proper sequences with extremely slow-growing initial segment complexity, that is, there is a proper sequence the initial segment complexity of which is infinitely often below every computable function, and even a proper sequence the initial segment complexity of which is dominated by all computable functions. (4) We prove various facts about the Turing degrees of such sequences and show that they are useful in the study of certain classes of pathological measures on $2^ω$ , namely diminutive measures and trivial measures.

preprint2016arXiv

The random members of a $Π^0_1$ class

We examine several notions of randomness for elements in a given $Π^0_1$ class $\mathcal{P}$ . Such an effectively closed subset $\mathcal{P}$ of $2^ω$ may be viewed as the set of infinite paths through the tree $T_{\mathcal{P}}$ of extendible nodes of $\mathcal{P}$ , i.e., those finite strings that extend to a member of $\mathcal{P}$ , so one approach to defining a random member of $\mathcal{P}$ is to randomly produce a path through $T_{\mathcal{P}}$ using a sufficiently random oracle for advice. In addition, this notion of randomness for elements of $\mathcal{P}$ may be induced by a map from $2^ω$ onto $\mathcal{P}$ that is computable relative to $T_{\mathcal{P}}$ , and the notion even has a characterization in term of Kolmogorov complexity. Another approach is to define a relative measure on $\mathcal{P}$ by conditionalizing the Lebesgue measure on $\mathcal{P}$ , which becomes interesting if $\mathcal{P}$ has Lebesgue measure 0. Lastly, one can alternatively define a notion of incompressibility for members of $\mathcal{P}$ in terms of the amount of branching at levels of $T_{\mathcal{P}}$ . We explore some notions of homogeneity for $Π^0_1$ classes, inspired by work of van Lambalgen. A key finding is that in a specific class of sufficiently homogeneous $Π^0_1$ classes $\mathcal{P}$ , each of these approaches coincides. We conclude with a discussion of random members of $Π^0_1$ classes of positive measure.

preprint2015arXiv

Algorithmically random functions and effective capacities

We continue the investigation of algorithmically random functions and closed sets, and in particular the connection with the notion of capacity. We study notions of random continuous functions given in terms of a family of computable measures called symmetric Bernoulli measures. We isolate one particular class of random functions that we refer to as online random functions $F$ , where the value of $y(n)$ for $y = F(x)$ may be computed from the values of $x(0),\dots,x(n)$ . We show that random online functions are neither onto nor one-to-one. We give a necessary condition on the members of the ranges of online random functions in terms of initial segment complexity and the associated computable capacity. Lastly, we introduce the notion of online \emph{partial} Martin-Löf random function on $2^ω$ and give a family of online partial random functions the ranges of which are precisely the random closed sets introduced by Barmpalias, Brodhead, Cenzer, Dashti, and Weber.

preprint2015arXiv

The interplay of classes of algorithmically random objects

We study algorithmically random closed subsets of $2^ω$ , algorithmically random continuous functions from $2^ω$ to $2^ω$ , and algorithmically random Borel probability measures on $2^ω$ , especially the interplay between these three classes of objects. Our main tools are preservation of randomness and its converse, the no randomness ex nihilo principle, which say together that given an almost-everywhere defined computable map between an effectively compact probability space and an effective Polish space, a real is Martin-Löf random for the pushforward measure if and only if its preimage is random with respect to the measure on the domain. These tools allow us to prove new facts, some of which answer previously open questions, and reprove some known results more simply. Our main results are the following. First we answer an open question of Barmapalias, Brodhead, Cenzer, Remmel, and Weber by showing that $\mathcal{X}\subseteq2^ω$ is a random closed set if and only if it is the set of zeros of a random continuous function on $2^ω$ . As a corollary we obtain the result that the collection of random continuous functions on $2^ω$ is not closed under composition. Next, we construct a computable measure $Q$ on the space of measures on $2^ω$ such that $\mathcal{X}\subseteq2^ω$ is a random closed set if and only if $\mathcal{X}$ is the support of a $Q$ -random measure. We also establish a correspondence between random closed sets and the random measures studied by Culver in previous work. Lastly, we study the ranges of random continuous functions, showing that the Lebesgue measure of the range of a random continuous function is always contained in $(0,1)$ .

preprint2015arXiv

Trivial measures are not so trivial

Although algorithmic randomness with respect to various non-uniform computable measures is well-studied, little attention has been paid to algorithmic randomness with respect to computable \emph{trivial} measures, where a measure $μ$ on $2^ω$ is trivial if the support of $μ$ consists of a countable collection of sequences. In this article, it is shown that there is much more structure to trivial computable measures than has been previously suspected.

preprint2014arXiv

Demuth's path to randomness

Osvald Demuth (1936--1988) studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later. In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on (i) Demuth's work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, (ii) Demuth's independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and (iii) the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth's work.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Christopher P. Porter

Research overview

Is this your work?

10 publications

Randomness extraction in computability theory

The intersection of algorithmically random closed sets and effective dimension

Key developments in algorithmic randomness

Rank and randomness

Randomness for computable measures and initial segment complexity

The random members of a $Π^0_1$ class

Algorithmically random functions and effective capacities

The interplay of classes of algorithmically random objects

Trivial measures are not so trivial

Demuth's path to randomness

See the researcher in context

Building this map preview

Christopher P. Porter

Research overview

Is this your work?

10 publications

Randomness extraction in computability theory

The intersection of algorithmically random closed sets and effective dimension

Key developments in algorithmic randomness

Rank and randomness

Randomness for computable measures and initial segment complexity

The random members of a Π10Π^0_1Π10​ class

Algorithmically random functions and effective capacities

The interplay of classes of algorithmically random objects

Trivial measures are not so trivial

Demuth's path to randomness

See the researcher in context

Building this map preview

The random members of a $Π^0_1$ class