TITLE: Asymptotic Fixed Points, Part I.
ABSTRACT: By a standard exercise, a uniform contraction on a complete metric
space has a fixed point. Easy examples show that this fails if the
contraction is not uniform. I will discuss some recent results where the
uniform property is replaced by asymptotic conditions on the contraction.
These results are most easily framed and proved using methods from
nonstandard analysis, so I will also briefly brief review those methods. If
there is interest, I will actually prove some of the fixed-point results in
a second seminar (hence the “Part I.”)
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$.