Keller 303

Introduction for grad students and other beginners, as a prequel to Thursday’s talk.

Speaker: André Nies (University of Auckland), Fellow of the Royal Society of New Zealand

Title: Structure within the class of $K$-trivial sets

Abstract: 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 quite 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 using cost functions.

The talk gives an overview and ends with open questions (of which there remain many).

Location: Keller Hall 303

TITLE: Asymptotic Fixed Points, Part II

ABSTRACT: Continuing the earlier seminar, I will give nonstandard proofs for

one or more (depending on time) results like the

one below (which consolidates and generalizes a number of recent results in

the area).

Suppose

$(X,d)$ is a complete metric space,

$T:Xto X$ is continuous,

$phi, phi_n:[0,infty)to[0,infty)$, and

$phi_n$ converges to $phi$ uniformly on the range of $d$,

$phi$ is semicontinuous and satisfies $phi(s)~~0$,~~

$d(T^nx,T^ny)lephi_n(d(x,y))$ for all $x,yin X$ and $ninmathbb N$.

Moreover, suppose that for any $x,y$, $phi(t)lesssim t$ on infinite

elements of

$${^*d(T^nx,T^my) : m, n text{ hyperintegers}}.$$

Then $T$ has a unique fixed point $x_infty$, and for every $xin X, limlimits_{ntoinfty}T^n(x)=x_infty$. Moreover, this convergence is

uniform on bounded subsets of $X$.

The Sporadic Logic Seminar returns this week at a new place and time

(Fridays, 2:30, K404). This week Mushfeq Khan will speak:

Title: “The Homogeneity Conjecture”

Abstract: It is often said that the theorems and methods of recursion theory

relativize. One might go as far as to say that much of its analytical power

derives from this feature. However, this power is accompanied by definite

drawbacks: There are important examples of theorems and open questions

whose statements are non-relativizing, i.e., they have been shown to be

true relative to some oracles, and false relative to others. It follows

that these questions cannot be settled purely through relativizing methods.

A famous example of such a negative result is Baker, Gill, and Solovay’s

theorem on the P vs. NP question.

The observation that techniques based on diagonalization, effective

numbering, and simulation relativize led some recursion theorists (notably

Hartley Rogers, Jr) to formulate what became known as the “Homogeneity

Conjecture”. It said that for any Turing degree d, the partial order of

degrees that are above d is isomorphic to the entire partial order of the

Turing degrees. In 1979, Richard Shore refuted it in an elegant, one-page

article which will be the subject of this talk.

Title: Some applications of logic to additive number theory

Abstract: I will review the Loeb measure construction; I will

assume some exposure to nonstandard analysis, or at least 1st order logic,

comparable to the review I gave last semester in my seminars on fixed

points. Time permitting I will give the Loeb-measure proof of Szemeredi’s

Theorem.

Logic seminar: David Ross

Title: Some applications of logic to additive number theory (cont.)

Room: Keller 404.

Abstract:

I will continue with some examples of results about sets of positive upper Banach density proved using Loeb measures.