Blog Archives

Topic Archive: computability

Notre Dame University
Dan Turetsky received his doctorate from the University of Wisconsin-Madison in 2010, under the supervision of Steffen Lempp, and has since held positions at Victoria University in Wellington, the Kurt Gödel Research Center in Vienna, and (currently) Notre Dame University. He studies many aspects of computability theory.
CUNY Logic WorkshopFriday, February 10, 20172:00 pmGC 6417

Russell Miller

Functors and infinitary interpretations of structures

City University of New York

It has long been recognized that the existence of an interpretation of one countable structure B in another one A yields a homomorphism from the automorphism group Aut(A) into Aut(B). Indeed, it yields a functor from the category Iso(A) of all isomorphic copies of A (under isomorphisms) into the category Iso(B). In traditional model theory, the converse is false. However, when we extend the concept of interpretation to allow interpretations by Lω1ω formulas, we find that now the converse essentially holds: every Borel functor arises from an infinitary interpretation of B in A, and likewise every Borel-measurable homomorphism from Aut(A) into Aut(B) arises from such an interpretation. Moreover, the complexity of an interpretation matches the complexities of the corresponding functor and homomorphism. We will discuss the concepts and the forcing necessary to prove these results and other corollaries.

University of Wisconsin
Noah Schweber received his doctorate from the University of California-Berkeley in 2016, under the supervision of Antonio Montalban. He now holds a postdoctoral position at the University of Wisconsin.
NERDS: New England Recursion & Definability SeminarSunday, November 6, 20162:50 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

Rose Weisshaar

Comparing notions of effective genericity

Notre Dame University

In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for n ≥ 3, every Mathias n-generic computes a Cohen n-generic. It is natural to wonder how other types of generic objects compare to one another. We consider generics for an effective version of Hechler forcing. Adapting a method developed by Cholak, Dzhafarov, and Soskova, we show that for n ≥ 3, every Mathias n-generic computes a Hechler n-generic, and every Hechler n-generic computes a Mathias n-generic. Finally, we explore the (open) question of whether, for n ≥ 3, the Mathias n-generics and the Hechler n-generics occupy exactly the same Turing degrees.

Rose Weisshaar
Notre Dame University
Rose Weisshaar is a doctoral student at Notre Dame University, under the supervision of Peter Cholak.
NERDS: New England Recursion & Definability SeminarSunday, November 6, 20163:30 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

Linda Brown Westrick

Uncountable free abelian groups via κ-computability

University of Connecticut

One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ01 definable (with parameters, in the language of set theory) over Lκ provides the notion of κ-computability. We may also quantify over subsets of Lκ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ11-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 20161:40 pmScience Center, Room E104​, Wellesley College, Wellesley, MA

Andre Nies

Structure within the class of K-trivial sets

University of Auckland

The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.

Initially the class looked amorphous. More recently, internal structure has been found. Bienvenu et al (JEMS, 2016) showed that there is a “smart” K-trivial set, in the sense that any ML-random computing it must compute all K-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches via cost functions.

Rachel Stahl
University of Connecticut
Shelley Stahl is a doctoral student at the University of Connecticut, working on a dissertation under the supervision of Reed Solomon.
NERDS: New England Recursion & Definability SeminarSunday, November 6, 201611:40 amScience Center, Room E104​, Wellesley College, Wellesley, MA

Rachel Stahl

Recursion theoretic results for the game of Cops and Robbers on graphs

University of Connecticut

Cops and Robbers is a vertex-pursuit game played on a connected graph wherein two players, a cop and a robber, begin on a pair of vertices and alternate turns moving to adjacent vertices. A graph is cop-win if, from any pair of starting vertices, the cop can occupy the same vertex as the robber after finitely many rounds. In this talk, preliminary computability-theoretic and reverse-math results about the game of cops and robbers on infinite computable graphs will be discussed. We will consider several characterizations of infinite cop-win trees and graphs, and explore the complexity of winning strategies for both players.

Cornell University
Richard Shore is the Goldwin Smith Professor of Mathematics at Cornell University, and is a past president of the Association for Symbolic Logic. He received his doctorate from the Massachusetts Institute of Technology in 1972, under the supervision of Gerald Sacks. At Cornell he has directed 16 doctoral theses and mentored a dozen postdoctoral scholars.
Wednesday, November 9, 20165:00 pmGerald D. Fischbach Auditorium, Simons Foundation, 160 Fifth Avenue, 2nd floorTo attend this talk, you need to register here.

Avi Wigderson


Institute for Advanced Study

Is the universe inherently deterministic or probabilistic? Perhaps more importantly – can we tell the difference between the two?

Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling and more. Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from “unpredictable” phenomena like the weather or the stock market?

A computational theory of randomness, developed in the past three decades, reveals (perhaps counterintuitively) that very little is lost in such deterministic or weakly random worlds. In the talk, Dr. Wigderson will explain the main ideas and results of this theory.

CUNY Logic WorkshopFriday, December 2, 20162:00 pmGC 6417

Reed Solomon

Weihrauch reducibility and Ramsey theorems

University of Connecticut

Weihrauch reducibility is a common tool in computable analysis for understanding and comparing the computational content of theorems. In recent years, variations of Weihrauch reducibility have been used to study Ramsey type theorems in the context of reverse mathematics where they give a finer analysis than implications in RCA0 and they allow comparisons of computably true principles. In this talk, we will give examples of recent results and techniques in this area.

Model theory seminarFriday, September 9, 201612:30 pmGC 6417

David Marker

The logical complexity of Schanuel’s Conjecture

University of Illinois at Chicago

In its most natural form Schanuel’s Conjecture is a $\Pi_1^1$-statement. We will show that there is an equivalent $\Pi^0_3$-statement. They key idea is a result of Jonathan Kirby showing that, if Schanuel’s Conjecture is false, then there are canonical counterexamples. Most of my lecture will describe Kirby’s work.

NERDS: New England Recursion & Definability SeminarSunday, November 6, 2016

Autumn 2016 NERDS at Wellesley College

Wellesley College

The Autumn 2016 meeting of NERDS, the New England Recursion and Definability Seminar, will take place on Sunday, November 6 at Wellesley College, in Wellesley, MA. Details are available from the NERDS website, and talks are also posted here on

CUNY Logic WorkshopFriday, November 11, 20162:00 pmGC 6417

Andre Nies

Describing finite groups by short first-order sentences

University of Auckland

We say that a class of finite structures for a finite first-order signature is R-compressible for an unbounded function R on the natural numbers if each structure G in the class has a first-order description of size at most O(R(|G|)). We show that the class of finite simple groups is log-compressible, and the class of all finite groups is log-cubed compressible.

The results rely on the classification of finite simple groups, the bi-interpretability of the twisted Ree groups with finite difference fields, the existence of profinite presentations with few relators for finite groups, and group cohomology. We also indicate why the results are close to optimal.

This is joint work with Katrin Tent, to appear in IJM, available here.

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20163:15 pmLocklin Hall, Room 232, Springfield College

Johanna Franklin

Randomness and Fourier series

Hofstra University

Carleson’s Theorem states that the Fourier series of certain integrable functions converge almost everywhere. I will consider this theorem in the context of computable analysis and show that the points that satisfy Carleson’s Theorem are precisely the Schnorr random points. This work is joint with Timothy H. McNicholl and Jason Rute.

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20161:15 pmLocklin Hall, Room 232, Springfield College

Eric Astor

Density and computability

University of Connecticut

We develop and discuss some of the theory relating asymptotic density and computability, with attention to the inherent complexity of sets with density invariant under computable permutation. We will make a brief excursion into reverse mathematics on the way, pointing out that a key equivalence of Kjos-Hanssen, Merkle, and Stephan holds over RCA0.

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 201610:45 amLocklin Hall, Room 232, Springfield College

A one-generic that does not compute a modulus for one-genericity

Dartmouth College

A function g ∈ 2ω is 1-generic if, for every recursively enumerable W⊂ 2< ω, there is some σ⊂ g such that either σ∈W or σ has no extensions in W. That is, any possible Σ01 property of g is either forced to be true or forced to be false by some finite initial segment of g. A function f∈ωω is a modulus for 1-genericity if, whenever h pointwise dominates f, then h computes some 1-generic. If g is 1-generic and either Δ02-definable or 2-generic, then g computes a modulus for 1-genericity. We give a priority argument to produce a 1-generic g that does not compute a modulus for 1-genericity.

(Joint work with Theodore A. Slaman.)

NERDS: New England Recursion & Definability SeminarSaturday, April 2, 20162:30 pmLocklin Hall, Room 232, Springfield College

Marie Nicholson

Computable categoricity, linear orders and permitting

University of Connecticut

Remmel showed that a computable linear order L is computably categorical if and only if the order type of L has only a finite number of successivities. As part of the proof, Remmel assumes that L has infinitely many successivities and constructs another computable linear order R, which is not computably isomorphic to L, and a Δ02-isomorphism f such that f is an isomorphism from L onto R. Hence showing that L is not computably categorical. In this talk I will discuss the conditions under which we can use permitting arguments to construct f below certain types of Δ02 degrees.