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

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

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.     

Lp-Computability

In this paper we investigate conditions for L^p-computability which are in accordance with the classical Grzegorczyk notion of computability for a continuous function. For a given computable real number p ≥ 1 and a compact computable rectangle I ? ?^q, we show that an L^p function f ∈ L^p(I) is L^P-computable if and only if (i) f is sequentially computable as a linear functional and (ii) the L^p-modulus function of f is effectively continuous at the origin of ?^q.     

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.     

A hierarchy of Turing degrees of divergence bounded computable real numbers

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2^-n. f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ>1 such that, for any constant c, f(nγ)+n+cg(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8–15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005, Springer, Berlin, pp. 418–428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.     

Order-free Recursion on the Real Numbers

We investigate operations, computable in the sense of Recursive Analysis, which can be generated recursively from the arithmetic operations and the limit operation without using any tests on the real numbers. These functions, called order-free recursive, can be shown to include a large class of computable functions. As main tools we provide an effective version of the Stone-Weierstraß Approximation Theorem, as well as recursive partitions of unity.     

Approaches to Effective Semi-Continuity of Real Functions

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo(f) is recursively enumerably open in dom(f) × ?; we call f lower semi-computable of type two, if its closed epigraph Epi(f) is recursively enumerably closed in dom(f) × ?; we call f lower semi-computable of type three, if Epi(f) is recursively closed in dom(f) × ?. We show that type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable.     

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.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

Towards computability of elliptic boundary value problems in variational formulation

We present computable versions of the Fréchet–Riesz Representation Theorem and the Lax–Milgram Theorem. The classical versions of these theorems play important roles in various problems of mathematical analysis, including boundary value problems of elliptic equations. We demonstrate how their computable versions yield computable solutions of the Neumann and Dirichlet boundary value problems for a simple non-symmetric elliptic differential equation in the one-dimensional case. For the discussion of these elementary boundary value problems, we also provide a computable version of the Theorem of Schauder, which shows that the adjoint of a computably compact operator on Hilbert spaces is computably compact again.     

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)     

Derivatives of Computable Functions

As is well known the derivative of a computable and C¹ function may not be computable. For a computable and C∞ function f, the sequence {f⁽ⁿ⁾} of its derivatives may fail to be computable as a sequence, even though its derivative of any order is computable. In this paper we present a necessary and sufficient condition for the sequence {f⁽ⁿ⁾} of derivatives of a computable and C^∞ function f to be computable. We also give a sharp regularity condition on an initial computable function f which insures the computability of its derivative f′.     

When series of computable functions with varying domains are computable

In this paper we study the behavior of computable series of computable partial functions with varying domains (but each domain containing all computable points), and prove that the sum of the series exists and is computable exactly on the intersection of the domains when a certain computable Cauchyness criterion is met. In our point‐free approach, we name points via nested sequences of basic open sets, and thus our functions from a topological space into the reals are generated by functions from basic open sets to basic open sets. The construction of a function that produces the sum of a series requires working with an infinite array of pairs of basic open sets, and reconciling the varying domains. We introduce a general technique for using such an array to produce a set function that generates a well‐defined point function and apply the technique to a series to establish our main result. Finally, we use the main finding to construct a computable, and thus continuous, function whose domain is of Lebesgue measure zero and which is nonextendible to a continuous function whose domain properly includes the original domain. (We had established existence of such functions with domains of measure less than ε for any , in an earlier paper.)     

Minimal numerations of positively computable families

It is proved that among computable numerations that are limit-equivalent to some positive numeration of a computable family of recursively enumerable sets, either there exists one least numeration, or there are countably many nonequivalent, minimal numerations. In particular, semilattices of computable numerations for computable families of finite sets and of weakly effectively discrete families of recursively enumerable sets either have a least element or possess countably many minimal elements.Translated fromAlgebra i Logika, Vol. 33, No. 3, pp. 233–254, May–June, 1994.     

Weakly Computable Real Numbers

A real number x is recursively approximable if it is a limit of a computable sequence of rational numbers. If, moreover, the sequence is increasing (decreasing or simply monotonic), then x is called left computable (right computable or semi-computable). x is called weakly computable if it is a difference of two left computable real numbers. We show that a real number is weakly computable if and only if there is a computable sequence (x_s)_s of rational numbers which converges to x weakly effectively, namely the sum of jumps of the sequence is bounded. It is also shown that the class of weakly computable real numbers extends properly the class of semi-computable real numbers and the class of recursively approximable real numbers extends properly the class of weakly computable real numbers.     

Monotonically Computable Real Numbers

Area number x is called k‐monotonically computable (k‐mc), for constant k > 0, if there is a computable sequence (x_n)_{n ∈ ℕ} of rational numbers which converges to x such that the convergence is k‐monotonic in the sense that k · |x — x_n| ≥ |x — x_m| for any m > n and x is monotonically computable (mc) if it is k‐mc for some k > 0. x is weakly computable if there is a computable sequence (x_s)_{s ∈ ℕ} of rational numbers converging to x such that the sum $\sum _{s \in \mathbb{N}}$|x_s — x_{s + 1}| is finite. In this paper we show that a mc real numbers are weakly computable but the converse fails. Furthermore, we show also an infinite hierarchy of mc real numbers.     

On Computability Theoretic Properties of Structures and Their Cartesian Products

In this paper we show that for any set X ⊆ ω there exists a structure 𝒜 that has no presentation computable in X such that 𝒜² has a computable presentation. We also show that there exists a structure 𝒜 with infinitely many computable isomorphism types such that 𝒜² has exactly one computable isomorphism type.     

Feasible Real Random Access Machines

We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <_kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time (t) can be computed on a Turing machine in time (t²·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time (t) are computable on a RAM in time (t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers.     

Polynomial differential equations compute all real computable functions on computable compact intervals

In the last decade, there have been several attempts to understand the relations between the many models of analog computation. Unfortunately, most models are not equivalent. Euler's Gamma function, which is computable according to computable analysis, but that cannot be generated by Shannon's General Purpose Analog Computer (GPAC), has often been used to argue that the GPAC is less powerful than digital computation. However, when computability with GPACs is not restricted to real-time generation of functions, it has been shown recently that Gamma becomes computable by a GPAC. Here we extend this result by showing that, in an appropriate framework, the GPAC and computable analysis are actually equivalent from the computability point of view, at least in compact intervals. Since GPACs are equivalent to systems of polynomial differential equations then we show that all real computable functions over compact intervals can be defined by such models.