2014 CMS Winter Meeting

McMaster University, December 5 - 8, 2014

Plenary, Prize and Public Lectures By session By speaker Posters

Computability Theory
Org: Peter Cholak (Notre Dame) and Barbara Csima (Waterloo)
[PDF]

ERIC ASTOR, The University of Chicago Asymptotic density, immunity, and randomness [PDF]

We investigate a computably-invariant restriction of asymptotic density, and observe that it has strong connections to both randomness and classical computability theory. In particular, we use it to define a new immunity property, recognize a new form of stochasticity, and find an unexpected connection to functions avoiding weak computable approximation. We also apply similar ideas to create computably-invariant restrictions of the generic-case computability defined by Jockusch and Schupp, and prove a generalization of Rice's Theorem as a lower bound on their strength.

DAVID BELANGER, Cornell University The jump of an ideal of degrees [PDF]

For each Turing degree $\mathbf{a}$, define $\mathrm{JB}(\mathbf{a}) = \{\mathbf{x}^\prime : \mathbf{x} \leq \mathbf{a}\}$. We show that not every r.e. $\mathbf{a}$ is uniquely determined by $\mathrm{JB}(\mathbf{a})$. The definition of $\mathrm{JB}$ is motivated by a possible attack on the rigidity problems for $\mathcal{R}$ and $\mathcal{D}$; our theorem thwarts one version of this attack. This is joint work with Richard Shore.

MINGZHONG CAI, Dartmouth College The join property and low$_2$ r.e.\ degrees [PDF]

A degree $\mathbf{d}$ has the \emph{join property} if for every nonzero degree $\mathbf{b}<\mathbf{d}$, there is a degree $\mathbf{c}<\mathbf{d}$ such that $\mathbf{b}\vee\mathbf{c}=\mathbf{d}$. In this talk I will present some recent progress on this topic. In particular, an r.e.\ degree is low$_2$ (i.e., its double jump equals $\mathbf{0}''$) if and only if there is a $\Delta^0_2$ degree above it which fails to satisfy the join property.

DOUGLAS CENZER, University of Florida Algorithmically random functions and effective capacity [PDF]

We continue the investigation of algorithmically random functions and closed sets, and in particular the connection with the notion of capacity. We introduce the notion of a partial Martin-L\"of random continuous function on $2^N$. We introduce a notion of a random online function F, where the value of y(n) for y=F(x) may be computed from the values of x(0),…,x(n). We show that random online functions are neither onto nor one-to-one. We examine the possible integrals of random online functions.These notions of randomness are studied with respect to Bernoulli and more general measures.

ELLEN CHIH, California - Berkeley Splittings and computably enumerable sets [PDF]

A split of a c.e. set $A$ is a pair of disjoint c.e. sets whose union is $A$. We discuss several properties of c.e. sets relating to lowness and show that these properties are not preserved under splits. We present properties such that there is a c.e. set with this property whose elements cannot be split into two sets preserving this property. Speedability is an example of such a property. A c.e. set is speedable if for every computable function, there exists a finite algorithm enumerating membership faster, by the desired computable factor, on infinitely many integers. We also present properties such that there is a c.e. set $A$ with this property but in any way that one non-trivially splits $A$, both sides of the split do not have this property. For example, being non-low is such a property.

DAMIR DZHAFAROV, University of Connecticut Computable, uniform, and strong reductions [PDF]

In reverse mathematics, one establishes connections between mathematical principles by proving implications over the base theory $RCA_0$. In practice, such implications are often due to the presence of considerably stronger computability-theoretic reducibilities holding between the principles, which are then merely formalized in second-order arithmetic. For instance, a typical implication $P \to Q$ of $\Pi^1_2$ principles is a formalized uniform reduction, meaning that there are functionals $\Phi$ and $\Psi$ such that, if $A$ is any instance of $P$, then $\Phi(A)$ is an instance of $Q$, and if $S$ is any solution to $\Phi(A)$, then $\Psi(A \oplus S)$ is a solution to $A$. The systematic study of this and related reducibilities in the specific context of $\Pi^1_2$ principles has recently emerged as a fruitful enterprise alongside traditional reverse mathematics. On the one hand, it offers a much finer way of calibrating the relative strength of mathematical propositions, and on the other, it sheds light on several open questions from the traditional analysis. This talk will present a summary of results and problems in this direction. In particular, I will discuss the longstanding open question of whether the stable form of Ramsey's theorem for pairs ($SRT^2_2$) implies the cohesive principle ($COH$) in standard models of $RCA_0$, and the growing number of recent results towards a negative answer.

VALENTINA HARIZANOV, George Washington University Interaction of computability theory and computable algebra [PDF]

Maximal sets and their complements, cohesive sets, play an important role in computability theory, especially in the study of the lattice of computably enumerable sets. Maximal sets are coatoms in its quotient lattice modulo finite sets. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces, introduced by Metakides and Nerode in the 1970s. We use cohesive sets to define specific powers of algebraic structures, in particular, of computable fields. These powers of structures may not be elementary equivalent to the structures. We investigate definability and isomorphism properties of these powers, using a recent result by Koenigsmann about definability of the integers in the rationals. Then we draw conclusions about the quotient lattice of computably enumerable vector spaces modulo finite dimension, and about its automorphisms. The question about the number of automorphisms of this lattice has been open for thirty years. This is joint work with R. Dimitrov, R. Miller, and J. Mourad.

MATTHEW HARRISON-TRAINOR, University of California, Berkeley Independence in computable algebra [PDF]

An old observation of Mal'cev is that there are two non-computably-isomorphic presentations of the infinite-dimensional vector space over $\mathbb{Q}$: the standard copy with a computable basis and a second copy with no computable basis. We will introduce the setting of an abstract r.i.c.e. pregeometry and give a sufficient conditions for an algebraic structure to have a computable presentation with a computable basis and a computable presentation with no computable basis. We will mention applications to particular algebraic structures such as differentially closed fields and real closed fields.

DENIS HIRSCHFELDT, University of Chicago Homogeneous sets for colorings of $\mathbb N$ [PDF]

I will discuss joint work with Carl Jockusch, in particular the result that there is a $3$-coloring $c$ of $\mathbb N$ such that every $2$-coloring of $\mathbb N$ has an infinite homogeneous set that does not compute an infinite homogeneous set for $c$. This result is related to a variation on the notion of infinite information reducibility introduced by Dzhafarov and Igusa, as well as to the project of comparing $\Pi^1_2$ principles via computability-theoretic notions of reduction.

GREGORY IGUSA, University of Notre Dame Cohen 1-generics and the finite intersection principle [PDF]

In 2012, Dzhafarov and Mummert discuss the proof-theoretic and computability-theoretic strength of a number of set-theoretic principles involving the axiom of choice. In particular, they discuss the content of the finite intersection principle: that given any set of sets, there is a subset that is maximal with respect to having the finite intersection property (every finite subset having nonempty intersection). We say that a Turing degree, ${\bf d}$, has FIP if given any computably presented set of computable reals $\lbrace X_i:i\in\omega\rbrace$, ${\bf d}$ can enumerate a set of indices $S$ such that $\lbrace X_i:i\in S\rbrace$ is a realization of the finite intersection principle for the first set.

In recent work, Diamondstone, Downey, Greenberg and Turetsky prove that a degree is FIP if it computes a Cohen 1-generic, and that the converse holds in the $\Delta^0_2$ case. We present a priority-free construction that directly ties 1-genericity to FIP, and that shows that the converse holds in general. This provides what might be the first instance of a classical theorem of mathematics whose computability theoretic strength aligns exactly with the ability to compute a 1-generic.

A more subtle priority argument also shows that the a priori weaker 2IP property is also equivalent to being able to compute a 1-generic, and hence to FIP.

ISKANDER KALIMULLIN, Kazan Federal University Index sets and enumerability of families [PDF]

I will study the connection between computably enumerable families and the complexity of related index sets. In particular, we will see that the non-low-2 degrees do not form a degree spectrum of a family of sets, while the non-low degrees do.

JULIA KNIGHT, University of Notre Dame Comparing two versions of the reals using computability [PDF]

I will speak on joint work with Gregory Igusa. There are two different structures to which we attach the name ``reals'': the ordered field of real numbers $\mathcal{R} = (\mathbb{R},+,\cdot,0,1,<)$, and $\mathcal{W} = (P(\omega)\cup\omega,P(\omega),\omega,\in,S)$, where $S$ is the successor function on $\omega$. Noah Schweber defined a reducibility that lets us compare uncountable structures according to the difficulty of building a copy (where the copies need not be completed unless we pass to a generic extension of the set theoretic universe in which the structures become countable). According to Schweber's definition, $\mathcal{A}\leq_w^*\mathcal{B}$ if in a generic extension of $V$ in which both $\mathcal{A}$ and $\mathcal{B}$ countable, every copy of $\mathcal{B}$ computes a copy of $\mathcal{A}$. It is not difficult to see that $\mathcal{W}\leq_w^*\mathcal{R}$. With some effort, we show that $\mathcal{R}\not\leq_w^*\mathcal{W}$. When the two structures become countable, they enumerate the same Scott set. There is a real closed field $\mathcal{R}^*$ such that $\mathcal{W}\equiv_w^* \mathcal{R}^*$. The extra computing power of $\mathcal{R}$ comes from the fact that it is Archimedean.

KAREN LANGE, Wellesley College Classifying $\mathcal{D}$-maximal sets [PDF]

In 1974, Soare proved that the maximal sets form an orbit under the automorphism group of $\mathcal{E}$, the set of computably enumerable sets under inclusion. In 1992, Downey and Stob showed that the hemimaximal sets, nontrivial splits of maximal sets, also form an orbit. Here, we examine the $\mathcal{D}$-maximal sets, a further generalization of the maximal sets that encompasses the hemimaximal sets as well. Let $\mathcal{D}(A)$ consist of the c.e. sets disjoint from $A$. A set is $\mathcal{D}$-maximal if the quotient $\mathcal{L}(A)/\mathcal{D}(A)$ is the two element boolean algebra. We develop a classification of the $\mathcal{D}$-maximal sets and show that they break into infinitely many orbits. This work is joint with Peter Cholak and Peter Gerdes.

STEFFEN LEMPP, University of Wisconsin-Madison Kalimullin pairs and definability in the enumeration degrees [PDF]

We study the distribution of Kalimullin pairs (K-pairs) in the global enumeration degrees, solving several open questions and obtaining as a corollary the solution to Rogers' 1967 question that the total enumeration degrees are indeed definable in the enumeration degrees.

ANDREW MARKS, Caltech Poly-time Turing reducibility is universal [PDF]

We show that Poly-time Turing reducibility is a universal locally countable Borel quasiorder.

ALEXANDER MELNIKOV, UC (Berkeley) and Massey (New Zealand) Torsion-free abelian groups and infinite divisibility [PDF]

In my talk I will survey several recent results in effective algebra that use special presentations of torsion-free abelian groups. In such presentations we first list a basis and then divisibility conditions upon the elements of the basis. Such a representation describes an isomorphism type of a torsion-free abelian group. Presentations via divisibility conditions have been rather useful in the study of degree spectra of torsion-free abelian groups and questions related to index sets and categoricity relative to an oracle.

KENG MENG (SELWYN) NG, Nanyang Technological University Diamond embeddings and minimal pairs in the r.e. truth table degrees [PDF]

We present some recent and old results on minimal pairs in the r.e. truth table degrees. Jockusch and Mohrherr showed that the diamond lattice {a,b,0,1} can be embedded in the r.e. truth table degrees preserving the top and bottom elements. We discuss related results about the possible degrees of a and b. We also discuss how to use the determinacy of finite games to construct minimal pairs in the r.e. truth table degrees.

CHRISTOPHER PORTER, University of Florida Initial segment complexity and randomness for computable measures [PDF]

According to the Levin-Schnorr theorem, a sequence $X\in 2^{\omega}$ is Martin-Löf random with respect to the Lebesgue measure if and only if $K(X\upharpoonright n)\geq n-O(1)$ for every $n$, where $K$ denotes prefix-free Kolmogorov complexity. It is well-known that this theorem can be extended to proper sequences, that is, sequences that are random with respect to some computable measure. However, one can show that there are proper sequences with slow-growing initial segment complexity (i.e., there is no computable lower bound for their initial segment complexity). I will discuss joint work with Rupert Hölzl and Wolfgang Merkle in which we study the various growth rates of the initial segment complexity of proper sequences. I will focus specifically on results concerning proper sequences that have sufficiently high initial segment complexity.

JAN REIMANN, Penn State University Algorithmically random point processes [PDF]

We develop a theory of algorithmically random point processes. Point processes are an important class of random closed sets important for the probabilistic modeling of geometric data. We study how the randomness of a point process as a whole is related to the algorithmic randomness of its points. We use these results to prove consistency results for fractal dimension estimators, based on Kolmogorov complexity.

NOAH SCHWEBER, UC-Berkeley Computability and structures in generic extensions [PDF]

Using set-theoretic forcing, many concepts of computable structure theory can be extended to structures of arbitrary cardinality in a natural way. For example, given two possibly uncountable structures $A$ and $B$, say $A$ is generically Muchnik reducible to $B$ if, whenever $V[G]$ is a forcing extension in which both $A$ and $B$ are countable, any copy of $B$ with domain $\omega$ in $V[G]$ Turing-computes a copy of $A$. Basic properties of forcing ensure that this translation is well-behaved. In particular, by Shoenfield's Absoluteness Theorem these notions are all independent of the choice of forcing extension, in a precise sense. Having defined generic Muchnik reducibility, it then becomes natural to see how it compares with other notions of relative complexity of uncountable objects - for example, relative constructibility: if $A$ is generically Muchnik reducibile to $B$, are copies of $A$ constructible relative to copies of $B$?

In this talk, we will introduce generic Muchnik reducibility, and examine the question mentioned above. We show that the answer to this question (when made precise) is in general "no," although the answer is "yes" if we assume that $B$ has cardinality at most $\aleph_1$. We will also show how these ideas lead to a new proof of a theorem of Harrington, that a counterexample to Vaught's conjecture must have models of cardinality $\aleph_1$ with Scott rank arbitrarily high below $\omega_2$.

This is joint work with Julia Knight and Antonio Montalban.

LINDA WESTRICK, University of Connecticut Comparing subshifts in $\mathbb{Z}$ and $\mathbb{Z}^2$ [PDF]

A subshift is a closed, shift-invariant subset of Cantor space. Also known as symbolic dynamical systems, subshifts were originally used to discretize information from continuous dynamical systems. The simplest kind of subshift is a shift of finite type (SFT), obtained by forbidding finitely many words (or in the two-dimensional case, finitely many $n\times n$ blocks) from occurring anywhere in an element of the subshift. SFTs have been extensively studied in both the one and two-dimensional cases, but the results have divergent characteristics. This difference often stems from the fact that two-dimensional SFTs can embed a Turing machine, while one-dimensional SFTs cannot. The distinction raises the question of whether some more computationally-powerful class of one-dimensional subshifts, such as $\Pi^0_1$ subshifts, could provide a better analogy to two-dimensional SFTs. For example, Durand, Romashchenko and Shen (2012), Hochman (2009), and others have described ways to embed one-dimensional $\Pi^0_1$ shifts into higher-dimensional SFTs. I will discuss the advantages and limitations of the analogy.

Sponsors