Overview

Date: Saturday, April 2, 2016
Time: 9:45 am–4:15 pm
Place: Springfield College (Visitor information; there has been a lot of construction in the Springfield area recently, so check traffic conditions ahead of time.)

Schedule

9:45–10:15	Karen Lange (Wellesley College)	Undergrad Talk
10:15–10:45	Coffee
10:45–11:15	Marcia Groszek (Dartmouth College)	A One-Generic That Does Not Compute a Modulus for One-Genericity
11:45–1:15	Lunch (Cheney Hall)
1:15–2:15	Eric Astor (University of Connecticut)	Density and Computability
2:15–2:30	Coffee
2:30–3:00	Marie Nicholson (University of Connecticut)	Computable Categoricity, Linear Orders and Permitting
3:00–3:15	Coffee
3:15–4:15	Johanna Franklin (Hofstra University)	Randomness and Fourier series

Abstracts

Marcia Groszek

(Joint work with Theodore A. Slaman.) A function $g \in 2^\omega$ is $1$-generic if, for every recursively enumerable $W \subseteq 2^{< \omega}$, there is some $\sigma = g\hook n$ such that either $\sigma \in W$ or $\sigma$ has no extensions in $W$. That is, any possible $\Sigma^0_1$ property of $g$ is either forced to be true or forced to be false by some finite initial segment of $g$. A function $f \in \omega^\omega$ 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 $\Delta^0_2$-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.

Eric Astor

We develop & 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.

Marie Nicholson

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 $\Delta^0_2$-isomorphism $f$ such that $f: L \to R$ is an isomorphism. 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 $\Delta^0_2$ degrees.

Johanna Franklin

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.

Karen Lange

You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path. But can we actually *compute* a path, given that we can prove one exists? Answering this question requires us to carefully define the verb “to compute”. This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.