UC Berkeley

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 Denjoy-integrable 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 well-founded 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 one-one 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: density-r subshifts, shifts of finite type, subshifts consisting of shift-complex 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 right-r.e. and the Medvedev degree is Pi^0_1, the subshifts we produce are Pi^0_1 in the one-dimensional case, and shifts of finite type in the two-dimensional 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 one-dimensional minimal subshift has a least element, and find the dimension spectrum of the minimal subshift from Bruin 2000.