Computability in Ordinal Ranks and Symbolic Dynamics

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 o1 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 pi2alpha+1-complete.;In the hierarchy defined by the transfinite process of Denjoy integration, the rank of a Denjoy-integrable function ƒ is defined as the ordinal alpha < o1 at which the process of integrating ƒ terminates. We show that the set of Turing indices of computable C[0; 1] functions of the form ∫ ƒ , where ƒ is Denjoy-integrable of rank 1, is pi3-complete; and that for any recursive ordinal alpha > 1, the set of indices of computable C[0; 1] functions of the form ∫ ƒ , where ƒ 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 0, the theorem provides a one-one reduction from O(2alpha) to the set of Turing indices of trees of limsup rank at most alpha, where O) is the canonical Sigmaalpha 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 [13, 25, 28, 32], 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 pi01, the subshifts we produce are pi011 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 [32], 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 [2].