Search

For any class of total functions in the set of natural numbers, we define what it means for a real function to be conditionally computable with respect to this class. This notion extends a notion of relative uniform computability of real functions introduced in a previous paper co-authored by Andreas Weiermann. If the given class consists of recursive functions then the conditionally computable real functions are computable in the usual sense. Under certain weak assumptions about the class in question, we show that conditional computability is preserved by substitution, that all conditionally computable real functions are locally uniformly computable, and that the ones with compact domains are uniformly computable. All elementary functions of calculus turn out to be conditionally computable with respect to one of the small subrecursive classes.

Let Csc and Cwc be classes of the semi-computable and weakly computable real numbers, respectively, which are discussed by Weihrauch and Zheng [12]. In this paper we show that both Csc and Cwc are not closed under the total computable real functions of finite length on some closed interval, although such functions map always a semi-computable real numbers to a weakly computable one. On the other hand, their closures under general total computable real functions are the same and are in fact an algebraic field. This field can also be characterized by the limits of computable sequences of rational numbers with some special converging properties.

In the representation approach (TTE) to Computable Analysis those representations of an algebraic or topological structure are of interest, for which the basic predicates and functions become computable. There are, however, natural examples of predicates and functions, which are not computable, even not continuous, for any representations. All these results follow from a simple lemma. In this article we prove this lemma and apply it to a number of examples. In particular we prove that various predicates and functions on computable measure spaces are not continuous for any representations, that means "absolutely non-effective".

We consider two classical computability notions for functions mapping all computable real numbers to computable real numbers. It is clear that any function that is computable in the sense of Markov, i.e., computable with respect to a standard Godel numbering of the computable real numbers, is computable in the sense of Banach and Mazur, i.e., it maps any computable sequence of real numbers to a computable sequence of real numbers. We show that the converse is not true. This solves a long-standing open problem; see Kushner [9].

We present Mazur's continuity results for Banach-Mazur computable functions on computable real numbers in the slightly more general setting of metric spaces satisfying suitable computability conditions. Additionally, we prove that the image of a computable, computably convergent sequence under a Banach-Mazur computable function is again computably convergent.

In this paper we prove computable versions of Urysohn's lemma and the Tietze-Urysohn extension theorem for computable metric spaces. We use the TTE approach to computable analysis [KW85,Wei00] where objects are represented by finite or infinite sequences of symbols and computations transform sequences of symbols to sequences of symbols. The theorems hold for standard representations of the metric space, the set of real numbers, the set of closed subsets and the set of continuous functions. We show that there are computable procedures determining the continuous functions from the initial data (closed sets, continuous functions). The paper generalizes results by Yasugi, Mori and Tsujii [YMT99] in two ways: (1) The Tietze-Urysohn extension applies not only to "strictly effectively ?-compact co-r.e." sets but to all co-r.e. closed sets. (2) Not only computable functions exist for computable sets and functions, respectively, but there are computable procedures which determine continuous functions from arbitrary closed sets and continuous functions, respectively. These procedures, however, are not extensional on the names under consideration, and so they induce merely multi-valued computable functions on the objects.

In 1931 Kurt Godel [50, 51] proved a momentous theorem with far-reaching philosophical consequences: he showed that no reasonable formal proof sys-tern for number theory can prove all true sentences. This result set the logic community on its ear and left Hilbert’s formalist program in shambles. This result is widely regarded as one of the greatest intellectual achievements of twentieth-century mathematics.