 Main
Computability in Ordinal Ranks and Symbolic Dynamics
 Author(s): Westrick, Linda Brown;
 Advisor(s): Slaman, Theodore;
 et al.
Abstract
Part 1: Computability in Ordinal Ranks
We analyze the computable part of three classical hierarchies from analysis and set theory. All results are expressed in the notation of Ash and Knight.
In the differentiability hierarchy
defined by Kechris and Woodin, the rank of a
differentiable function is an ordinal less than omega_1 which
measures how complex it is to verify differentiability for that
function. We show that for each recursive ordinal alpha>0, the
set of Turing indices of computable C[0,1] functions that are differentiable with rank at most alpha is Pi_{2alpha+1}complete.
In the hierarchy defined by the transfinite process of Denjoy integration, the rank of a Denjoyintegrable function f is defined as the ordinal alpha1, the set of indices of computable C[0,1] functions of the form int f, where f has rank at most alpha, is Sigma_{2alpha}complete.
Finally, we give a new proof that for any recursive ordinal alpha>1, the set of indices for computable trees in 2^{
The major contribution of Part 1 is a general theorem which lies at the core of all three results. We introduce the limsup rank which assigns an ordinal to each wellfounded tree in Baire space. Trees of limsup rank alpha are seen to correspond in a computable way to objects of rank alpha in each of the three contexts discussed above. For each recursive ordinal alpha>0, the theorem provides a oneone reduction from emptyset_{(2 alpha)} to the set of Turing indices of trees of limsup rank at most alpha, where emptyset_{(alpha)} is the canonical Sigma_alpha complete set.
Part 2: Computability in Symbolic Dynamics
We consider various questions in the intersection of computability theory as applied to subshifts. In particular, we consider three subshift invariants: entropy, Medvedev degree, and effective dimension spectrum. The last one is a new invariant. We explore these invariants in the context of important examples of subshifts: densityr subshifts, shifts of finite type, subshifts consisting of shiftcomplex sequences, and Medvedev subshifts.
Building on the work of Hochman & Meyerovitch, Myers, Robinson and Simpson, we show that the entropy and the Medevedev degree are independent invariants. To do this we construct subshifts with every combination of entropy and Medvedev degree that is not immediately prohibited, in both one and two dimensions. When the entropy is rightr.e. and the Medvedev degree is Pi^0_1, the subshifts we produce are Pi^0_1 in the onedimensional case, and shifts of finite type in the twodimensional case. When the entropy is in [0,1), we accomplish this using an alphabet with only two symbols.
We introduce the dimension spectrum of a subshift X as {dim(x) : x in X}, where dim is the effective dimension, and work towards a characterization of the possible dimension spectra. By a result of Simpson, every dimension spectrum has a top element. Conditions are given under which the dimension spectrum of X is the interval [0,ent(X)], and examples are given where the dimension spectrum is bounded away from 0.
We show that the dimension spectrum of a onedimensional minimal subshift has a least element, and find the dimension spectrum of the minimal subshift from Bruin 2000.
Main Content
Enter the password to open this PDF file:













