Classes of Grzegorczyk-computable real numbers

The theory of computable functions has given rise to the notion of computable real numbers. We may define computable reals by effectivizing classical definitions of real numbers. For example, we may define a computable real as the limit of a Cauchy sequence of rationals where both the sequence of rationals and the convergence of that sequence are computable. Alternatively, we may effectivize expansions to a base p, and Dedekind cuts. All of these classical definitions of reals effectivize to give the same definition of computable real.

From the viewpoint of computer science, the notion of general computability may be too broad. It is therefore desirable to examine restricted classes of computability. An approach which has been taken in the literature is the study of primitive recursive reals. The effectivizations of Cauchy reals, expansions to the base p, Dedekind cuts, and continued fractions when restricted to primitive recursive functions are not equivalent.

The restriction of computability to primitive recursion may still be too broad. In this thesis we look below primitive recursion in the study of the computability of reals within the Grzegorczyk hierarchy. The Grzegorczyk hierarchy is an infinite hierarchy such that the union of the Grzegorczyk classes is the class of primitive recursive functions. The interrelations of four definitions of real numbers effectivized within the Grzegorczyk classes are examined.