A theory of approximation to measurable sets and measurable functions based on the concepts of recursion theory and discrete complexity theory is developed. The approximation method uses a model of oracle Turing machines, and so the computational complexity may be defined in a natural way. This complexity measure may be viewed as a formulation of the average-case complexity of real functions—in contrast to the more restrictive worst-case complexity. The relationship between these two complexity measures is further studied and compared with (...) the notion of the distribution-free probabilistic computation. The computational complexity of the Lebesgue integral of polynomial-time approximable functions is studied and related to the question “FP = ♯P?”. (shrink)

In this paper we develop a point-free approach to the study of topological spaces and functions on them, establish platforms for both and present some findings on recursive points. In the first sections of the paper, we obtain conditions under which our approach leads to the generation of ideal objects with which mathematicians work. Next, we apply the effective version of our approach to the real numbers, and make exact connections to the classical approach to recursive reals. In the succeeding (...) sections of the paper, we introduce machinery to produce functions on topological spaces and find succinct conditions which will be effectivized in our sequel. (shrink)

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings . To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of (...) a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We introduce the notion of a convex tree. We show that the binary expansion for real numbers in the unit interval ) is equivalent to weak König lemma ) for trees having at most two nodes at each level, and we prove that the intermediate value theorem is equivalent to \ for convex trees, in the framework of constructive reverse mathematics.