The elementary computable functions over the real numbers: applying two new techniques

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the real elementary computable functions; our result does not require the restriction to functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort.      

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.     

An open mapping theorem without continuity and linearity

We establish an open mapping theorem which is independent of continuity and linearity of concerned mappings. This is a substantial improvement of the classical version and its generalizations.     

Generalized Nevanlinna functions and multivalency

A new characterization of generalized Nevanlinna functions in terms of multivalency is established. By analyzing multivalent functions additional novel characterizations of (generalized) Nevanlinna functions are obtained. As a particular consequence of these investigations a function-theoretic proof of the factorization property of generalized Nevanlinna functions is obtained.     

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.     

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.     

Constrained open mapping theorem with applications

We prove a generalization of Graves? Open Mapping Theorem for a class of mappings which can be approximated at a reference point by a set-valued one having particular properties. The nonlinear mapping is restricted to a closed convex subset of a Banach space. We apply the results to derive necessary and sufficient conditions ensuring the existence of a differentiable selection for the inverse mapping. A slight generalization of a sufficient condition by J. Klamka on so-called constrained exact local controllability of nonlinear and semi-linear dynamic systems is also proved.     

Effective Borel degrees of some topological functions

The focus of this paper is the incomputability of some topological functions (with respect to certain representations) using the tools of Borel computability theory, as introduced by V. Brattka in [3] and [4]. First, we analyze some basic topological functions on closed subsets of ?ⁿ , like closure, border, intersection, and derivative, and we prove for such functions results of Σ⁰₂‐completeness and Σ⁰₃‐completeness in the effective Borel hierarchy. Then, following [13], we re‐consider two well‐known topological results: the lemmas of Urysohn and Urysohn‐Tietze for generic metric spaces (for the latter we refer to the proof given by Dieudonné). Both lemmas define Σ⁰₂‐computable functions which in some cases are even Σ⁰₂‐complete. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.)     

Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

The space of strong types and an open map theorem

We define a new topology on the space of strong types on a subsetA of a model of a given theory and prove that either . We also deduce an open map theorem.     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

On-line scheduling of small open shops

We investigate the problem of on-line scheduling open shops of two and three machines with an objective of minimizing the schedule makespan. We first propose a 1.848-competitive permutation algorithm for the non-preemptive scheduling problem of two machines and show that no permutation algorithm can be better than 1.754-competitive. Secondly, we develop a (27/19)-competitive algorithm for the preemptive scheduling problem of three machines, which is most competitive.     

On the (semi)lattices induced by continuous reducibilities

Continuous reducibilities are a proven tool in Computable Analysis, and have applications in other fields such as Constructive Mathematics or Reverse Mathematics. We study the order‐theoretic properties of several variants of the two most important definitions, and especially introduce suprema for them. The suprema are shown to commutate with several characteristic numbers (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some properties for quaternionic slice regular functions on domains without real points

The theory of slice regular functions over the quaternions, introduced by Gentili and Struppa in 2007, was born on balls centred in the origin and has been extended to more general domains that intersect the real axis in a work of 2009 in collaboration with Colombo and Sabadini. This hypothesis can be overcome using the theory of stem functions introduced by Ghiloni and Perotti in 2011, in the context of real alternative algebras. In this paper, I will recall the notion and the main properties of stem functions. After that I will introduce the class of slice regular functions induced by stem functions and, in this set, I will extend the identity principle, the maximum and minimum modulus principles and the open mapping theorem. Differences will be shown between the case when the domain does or does not intersect the real axis.     

A new heuristic for open shop total completion time problem

The m  -machine open shop problem to minimize the sum of the completion times is investigated in our paper. First, a heuristic algorithm, Shortest Processing Time Block, is presented to deal with problem _Om|n=km|∑_Cj$O_m|n=\mathit{km}|\sum C_j$, where k   is positive integer. And then, the heuristic is extended to solve the general problem _Om‖∑_Cj$O_m\Vert \sum C_j$. It is proved that the heuristic is asymptotically optimal when the job number goes to infinity. At the end of this paper, numerical experimentation results show the effectiveness of the heuristic algorithm.     

A note on feebly continuous functions

A function f from to is said to be feebly continuous at a point (x,y) if there exist sequences x_nx and y_ny with lim_n→∞lim_m→∞f(x_n,y_m)=f(x,y). Dales asked if every function has a point of feeble continuity. Our aim in this short note is to show that (assuming the Continuum Hypothesis) the answer is ‘no’. Dales also asked what happens for functions taking only two values: we show that in this case the answer is ‘yes’.     

Preservation theorems for bounded formulas

In this paper we naturally define when a theory has bounded quantifier elimination, or is bounded model complete. We give several equivalent conditions for a theory to have each of these properties. These results provide simple proofs for some known results in the model theory of the bounded arithmetic theories like CPV and PV₁. We use the mentioned results to obtain some independence results in the context of intuitionistic bounded arithmetic. We show that, if the intuitionistic theory of polynomial induction on strict formulas proves decidability of formulas, then P=NP. We also prove that, if the mentioned intuitionistic theory proves , then P=NP.     

On-line two-machine open shop scheduling with time lags

We analyze the performance of the greedy algorithm for the on-line two-machine open shop scheduling problem of minimizing makespan, in which time lags exist between the completion time of the first and the start time of the second operation of any job. The competitive ratio for the greedy algorithm is 2, and it can be reduced to 5/3 if the maximum time lag is less than the minimum positive processing time of any operation. These ratios are tight. We also prove that no on-line non-delay algorithm can have a better competitive ratio.