A Real Number Structure that is Effectively Categorical

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers.     

图灵机计算实数函数的稳定性

定义在全体实数上的可计算函数是一个很重要的概念．在这以前定义可计算的实数函数有两个途径．第一个途径是首先要定义可计算实数的指标．想要确定实数函数y=f（x）是不是可以计算就要看是否存在一个自然数的（部分）递归函数将可计算实数x的指标对应到可计算实数y的指标．这样一来对实数函数的研究依赖于对自然数函数的研究．第二个定义可计算的实数函数的途径是以逼近为基础的．一个实数函数是可以计算的如果它既是序列可计算的同时也是一致连续的．用这个途径来定义可计算实数函数使用的条件过强以至于很多有用的实数函数成为不可计算的实数函数．例如“〈”和“=”的命题函数就是不可以计算的因为它们是不连续的命题函数．本文讨论了图灵机的稳定性并且给出了一个基于稳定图灵机的可计算实数函数的定义．我们的定义不需要用到自然数的（部分）递归函数．根据我们的定义很多常用实数函数特别是一些不连续的常用实数函数都是可以计算的．用我们的定义来讨论可计算实数函数的性质比原来的定义要方便得多．     

A sequentially computable function that is not effectively continuous at any point

P. Hertling [Lecture Notes in Computer Science, vol. 2380, Springer, Berlin, 2002, pp. 962–972; Ann. Pure Appl. Logic 132 (2005) 227–246] showed that there exists a sequentially computable function mapping all computable real numbers to computable real numbers that is not effectively continuous. Here, that result is strengthened: a sequentially computable function on the computable real numbers is constructed that is not effectively continuous at any point.     

Stability of representations of effective partial algebras

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 (theorems of Moschovakis and Hertling). 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     

Computability of Minimizers and Separating Hyperplanes

We prove in recursive analysis an existence theorem for computable minimizers of convex computable continuous real-valued functions, and a computable separation theorem for convex sets in ?^m. Mathematics Subject Classification: 03F60, 52A40.     

Recursive analysis of singular ordinary differential equations

We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the recursively enumerable sets using Fourier coefficients of recursive analytic functions that are generated by differential equations and elementary operations.     

Recursive analysis of singular ordinary differential equations

We investigate systems of ordinary differential equations with a parameter. We show that under suitable assumptions on the systems the solutions are computable in the sense of recursive analysis. As an application we give a complete characterization of the recursively enumerable sets using Fourier coefficients of recursive analytic functions that are generated by differential equations and elementary operations.     

Isomorphism of the Index Sets of Discrete Families of General Recursive Functions

We establish isomorphism between the index set of an arbitrary computable family of general recursive functions and the index set of a certain computable discrete family of general recursive functions.     

Continuous optimization problems and a polynomial hierarchy of real functions

The close connection between the maximization operation and nondeterministic computation has been observed in many different forms. We examine this relationship on real functions and give a characterization of NP-time computable real functions by the maximization operation. A natural extension of NP-time computable real functions to a polynomial hierarchy of real functions has a characterization by alternating operations of maximization and minimization. Although syntactically this hierarchy of real functions can be treated as a polynomial hierarchy of operators, the well-known Baker-Gill-Solovay separation result does not apply to this hierarchy. This phenomenon is explained by the inherent structural properties of real functions, and is compared with recent studies on positive relativization.     

The Arithmetical Hierarchy of Real Numbers

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left (right) computable iff it is the supremum (infimum) of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable (multiple) sequences of rational numbers we introduce a non‐collapsing hierarchy {Σ_n, Π_n, Δ_n : n ∈ ℕ} of real numbers. We characterize the classes Σ₂, Π₂ and Δ₂ in various ways and give several interesting examples.     

Computability of measurable sets via effective topologies

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces constructed. The authors are supported by grants of NSFC and DFG.     

Effective Structures

The connection between some special properties of the computable functions in an abstract structure and the existence of a recursive and semi-recursive representation of the structure is studied. The considerations are based on the notion of computability on many-sorted abstract structures.     

<Emphasis Type="Italic">e</Emphasis>-Principal numberings

We prove the existence of the computable families of finite sets and general recursive functions with no e-principal numbering. We give a series of examples of e-degrees such that the p-degrees of their computable numberings include no top p-degree.     

h‐monotonically computable real numbers

Let h : ? → ? be a computable function. A real number x is called h‐monotonically computable (h‐mc, for short) if there is a computable sequence (x_s) of rational numbers which converges to x h‐monotonically in the sense that h(n)|x – x_n| ≥ |x – x_m| for all n andm > n. In this paper we investigate classes h‐ MC of h‐mc real numbers for different computable functions h. Especially, for computable functions h : ? → (0, 1)_?, we show that the class h‐ MC coincides with the classes of computable and semi‐computable real numbers if and only if Σ_i∈?(1 – h(i)) = ∞and the sum Σ_i∈?(1 – h(i)) is a computable real number, respectively. On the other hand, if h(n) ≥ 1 and h converges to 1, then h‐ MC = SC (the class of semi‐computable reals) no matter how fast h converges to 1. Furthermore, for any constant c > 1, if h is increasing and converges to c, then h‐ MC = c‐ MC . Finally, if h is monotone and unbounded, then h‐ MC contains all ω‐mc real numbers which are g‐mc for some computable function g. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

集合上的递归函数

本文在Ｊｅｎｓｅｎ和Ｋａｒｐ工作的基础上引进了集合上的递归函数的概念．研究了递归集函数的初步性质，讨论了递归集函数与Ｊｅｎｓｅｎ和Ｋａｒｐ定义的原始递归集函数及递归数论函数之间的关系，并给出了ＺＦＣ的可定义集模型上递归集函数的范式定理．     

由有理数Cauchy列定义的实数的无限十进小数展开

讨论了有理数Cauchy列定义的实数系的一种等价形式———无限十进小数展开,定义了其上的算术运算与顺序并证明了它们和已有的定义一致.     

On the operations of bounded suffix summation and multiplication

The operations of bounded suffix summation and bounded suffix multiplication are introduced. Using these operations, we define the class BSSM of polynomially computable functions. It is proved that the class BSSMcontains the class BPC defined by the operation of bounded prefix concatenation and has finite basis under superposition.     

Teaching of real numbers by using the Archimedes–Cantor approach and computer algebra systems

Computer technologies and especially computer algebra systems (CAS) allow students to overcome some of the difficulties they encounter in the study of real numbers. The teaching of calculus can be considerably more effective with the use of CAS provided the didactics of the discipline makes it possible to reveal the full computational potential of CAS. In the case of real numbers, the Archimedes–Cantor approach satisfies this requirement. The name of Archimedes brings back the exhaustion method. Cantor's name reminds us of the use of Cauchy rational sequences to represent real numbers. The usage of CAS with the Archimedes–Cantor approach enables the discussion of various representations of real numbers such as graphical, decimal, approximate decimal with precision estimates, and representation as points on a straight line. Exercises with numbers such as e, π, the golden ratio ?, and algebraic irrational numbers can help students better understand the real numbers. The Archimedes–Cantor approach also reveals a deep and close relationship between real numbers and continuity, in particular the continuity of functions.     

Effective Borel measurability and reducibility of functions

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single‐valued as well as for multi‐valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya‐Srivastava in order to prove a generalization of the Representation Theorem of Kreitz‐Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach‐Hausdorff‐Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On local non‐compactness in recursive mathematics

A metric space is said to be locally non‐compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non‐compact iff it is without isolated points. The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a computable sequence that is eventually computably bounded away from every computable element of the space. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)