Search

We characterize the intrinsically recursive functions over the algebraic closure of a finite field in terms of Turing machine complexity classes and derive some structural properties about the family of such functions. In particular, we show that the domain of convergence of any partial recursive function is again recursive, and, under complexity-theoretic hypotheses, that the class of tail recursive functions is strictly smaller than the class of recursive functions (cf. Theorems 5.4, 5.2, and Section 8). Underlying these results is the “meta-result” that we can perform a limited amount of arithmetic inside the field itself, with no access to a separate sort of natural numbers.

We study which classes of recursive functions satisfy that their union with any other explanatorily learnable class of recursive functions is again explanatorily learnable. We provide sufficient criteria for classes of recursive functions to satisfy this property and also investigate its effective variants. Furthermore, we study the question which learners can be effectively extended to learn a larger class of functions. We solve an open problem by showing that there is no effective procedure which does this task on all learners which do not learn a dense class of recursive functions. However, we show that there are two effective extension procedures such that each learner is extended by one of them.

A new class of generalized convex functions called sub-b-s-convex functions is defined by modulating the definitions of s-convex functions and sub-b-convex functions. Similarly, a new class sub-bs-convex sets, which are generalizations of s-convex sets and sub-b-convex sets, is introduced. Furthermore, some basic properties of sub-b-s-convex functions in both general case and differentiable case are presented. In addition the sufficient conditions of optimality for both unconstrained and inequality constrained programming are established and proved under the sub-b-s-convexity.

A method for constructing quasi universal “simple form” functions in the class of word functions is proposed. The method is used to construct an explicit superposition basis in the class of functions that can be computed in polynomial time.

In this paper, a robust and as simple as possible concept of a Petri net (PN) computer is proposed. It has a similar structure and behavior to weak sound priority workflow nets. It is shown that all recursive functions are PN computable and, vice-versa, PN computable functions are recursive. This shows that the PN computers we have proposed have exactly the power of Turing machines. Complexity classes of PN computable functions are defined, and the relationship between them and similar complexity classes defined by counter machines is investigated. Finally, the close relationship between PN computers and weak sound (priority) workflow nets is investigated.

Cost functions provide a framework for constructions of sets Turing below the halting problem that are close to computable. We carry out a systematic study of cost functions. We relate their algebraic properties to their expressive strength. We show that the class of additive cost functions describes the K-trivial sets. We prove a cost function basis theorem, and give a general construction for building computably enumerable sets that are close to being Turing complete.

A widely used approach to computability of real functions is the one in Grzegorczyk’s style originating from [1]. This approach uses computable transformations of infinitistic names of real numbers, as well as general quantifiers over these names. Other approaches allow avoiding the use of such names at least in some cases. An approach of this other kind is, for instance, the one of Tent and Ziegler from [5]. In the present paper, the equivalence of a certain approach in Grzegorczyk’s spirit and one in the spirit of Tent and Ziegler is shown under some general assumptions.

The model of recursive functions in 1934–1936 was a deductive formal system. In 1936, Turing and in 1944, Post introduced more intuitive models of Turing machines and generational systems. When they both died prematurely in 1954, their informal approach was replaced again by the very formal Kleene T -predicate for another decade. By 1965, researchers could no longer read the papers. A second wave of intuition arose with the book by Rogers and Lachlan's revealing papers. A third wave of intuition has arisen from 1996 to the present with a return to the original meaning of computability in the sense of Turing and Gödel, and a return of ‘recursive’ to its original meaning of ‘inductive’ and the founding of Computability in Europe by Cooper and others.

In this paper we introduce the algebra of bicomplex numbers as a generalization of the field of complex numbers. We describe how to define elementary functions in such an algebra (polynomials, exponential functions, and trigonometric functions) as well as their inverse functions (roots, logarithms, inverse trigonometric functions). Our goal is to show that a function theory on bicomplex numbers is, in some sense, a better generalization of the theory of holomorphic functions of one variable, than the classical theory of holomorphic functions in two complex variables.

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore's class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230---265, 1936), Grzegorczyk (Fundam Math 42:168---202, 1955), and Lacombe (Compt Rend l'Acad Sci Paris 241:151---153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore's class and the relationships between them.

The functions of computable analysis are defined by enhancing normal Turing machines to deal with real number inputs. We consider characterizations of these functions using function algebras, known as real recursive functions. Since there are numerous incompatible models of computation over the reals, it is interesting to find that the two very different models we consider can be set up to yield exactly the same functions. Bournez and Hainry used a function algebra to characterize computable analysis, restricted to the twice continuously differentiable functions with compact domains. In our earlier paper, we found a different (and apparently more natural) function algebra that also yields computable analysis, with the same restriction. In this paper we improve earlier work, finding three function algebras characterizing computable analysis, removing the restriction to twice continuously differentiable functions and allowing unbounded domains. One of these function algebras is built upon the widely studied real primitive recursive functions. Furthermore, the proof of this paper uses our previously developed method of approximation, whose applicability is further evidenced by this paper.

In this paper we introduce new type of functions called pre-proper functions as generalization of proper functions. Also, we study the characterizations and basic properties of pre-proper and preclosed functions. Moreover we study the relation between the pre-proper functions and each of proper functions, pre-closed functions and closed functions respectively and we give an example when the converse may not be true.

We formalize the algorithms computing primitive recursive (PR) functions as the abstract state machines (ASMs) whose running length is computable by a PR function. Then we show that there exists a programming language (implementing only PR functions) by which it is possible to implement any one of the previously defined algorithms for the PR functions in such a way that their complexity is preserved.

The class of recursive functions over the reals, denoted by REC(R), was introduced by Cristopher Moore in his seminal paper written in 1995. Since then many subsequent investigations brought new results: the class REC(R) was put in relation with the class of functions generated by the General Purpose Analogue Computer of Claude Shannon; classical digital computation was embedded in several ways into the new model of computation; restrictions of REC(R) were proved to represent different classes of recursive functions, e.g., recursive, primitive recursive and elementary functions, and structures such as the Ritchie and the Grzergorczyk hierarchies. The class of real recursive functions was then stratified in a natural way, and REC(R) and the analytic hierarchy were recently recognised as two faces of the same mathematical concept. In this new article, we bring a strong foundational support to the Real Recursive Function Theory, rooted in Mathematical Analysis, in a way that the reader can easily recognise both its intrinsic mathematical beauty and its extreme simplicity. The new paradigm is now robust and smooth enough to be taught. To achieve such a result some concepts had to change and some new results were added.

This paper analyzes complexities of decision diagrams for elementary functions such as polynomial, trigonometric, logarithmic, square root, and reciprocal functions. These real functions are converted into integer-valued functions by using fixed-point representation. This paper presents the numbers of nodes in decision diagrams representing the integer-valued functions. First, complexities of decision diagrams for polynomial functions are analyzed, since elementary functions can be approximated by polynomial functions. A theoretical analysis shows that binary moment diagrams (BMDs) have low complexity for polynomial functions. Second, this paper analyzes complexity of edge-valued binary decision diagrams (EVBDDs) for monotone functions, since many common elementary functions are monotone. It introduces a new class of integer functions, Mp-monotone increasing function, and derives an upper bound on the number of nodes in an EVBDD for the Mp-monotone increasing function. A theoretical analysis shows that EVBDDs have low complexity for Mp-monotone increasing functions. This paper also presents the exact number of nodes in the smallest EVBDD for the n-bit multiplier function, and a variable order for the smallest EVBDD.

In recent years it has been convincingly argued that the Church-Turing thesis concerns the bounds of human computability: The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm. Thus the Thesis needs to be distinguished from the so-called Physical Church-Turing thesis (or Thesis M), according to which all physically computable functions are Turing computable. The latter is often claimed to be false, or, if true, contingently so. On all accounts, though, thesis M is not easy to give counterexamples to, but it is never asked why--how come that a thesis that transfers a notion from the strictly human domain to the general physical domain just happens to be so difficult to falsify (or even to be true). In this paper I articulate this question and consider several tentative answers to it.

We give a complete characterization of the class of functions that are the intensional behaviours of primitive recursive (PR) algorithms. This class is the set of primitive recursive functions that have a null basic case of recursion. This result is obtained using the property of ultimate unarity and a geometrical approach of sequential functions on N the set of positive integers.

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 \({\mathcal{C}}^2\)real elementary computable functions; our result does not require the restriction to \({\mathcal{C}}^2\) 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.

We study a countable class of real-valued functions inductively defined from a basic set of trivial functions by composition, solving first-order differential equations and the taking of infinite limits. This class is the analytical counterpart of Kleene's partial recursive functions. By counting the number of nested limits required to define a function, this class can be stratified by a potentially infinite hierarchy-a hierarchy of infinite limits. In the first meaningful level of the hierarchy, we have the extensions of classical primitive recursive functions. In the next level, we find partial recursive functions, and in the following level we find the solution to the halting problem. We use methods from numerical analysis to show that the hierarchy does not collapse, concluding that the taking of infinite limits can always produce new functions from functions in the previous levels of the hierarchy.

In the paper the relationship between quasi-orderings (i.e. transitive and reflexive relations) and multi-objective functions (i.e. functions being a finite vector of continuous value functions) is investigated. A characterization of quasi-orderings representable by multi-objective functions is given. Within the introduced theoretical framework it is, in particular, shown that preferences implied by a first order stochastic dominance relation cannot be represented by multi-objective functions.

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 a technique we call the method of approximation. We give the general development of this method, and apply it to obtain 2 theorems. First we connect the discrete operation of linear recursion (basically equivalent to the combination of bounded sums and bounded products) to linear differential equations, thus providing an alternative proof of the result from Campagnolo, Moore and Costa [M.L. Campagnolo, C. Moore and J. F. Costa, An analog characterization of the Grzegorczyk hierarchy, Journal of Complexity 18 (2002) 977–100]. Secondly, we extend this to prove a result similar to that of Bournez and Hainry [O. Bournez and E. Hainry, Elementarily computable functions over the real numbers and R-sub-recursive functions, Theoretical Computer Science 348 (2005) 130–147], providing a function algebra for the real functions computable in elementary time. 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 Kalmar elementary computable functions to a result on the reals. While we do not claim that our result is necessarily an improvement (perhaps just different), we do want to make the point that our two techniques appear readily applicable to other problems of this sort.

We introduced and studied some new classes of functions called (e*, s)-continuous functions, (e, s)-continuous functions and (a, s)-continuous functions. These new notions of functions generalize the class of almost contra-super-continuous functions. Some properties and several characterizations of these types of functions are obtained. We investigate the relationships between these classes of functions and other classes of non-continuous functions. .

We study the monoid of primitive recursive functions and investigate a onestep construction of a kind of exact completion, which resembles that of the familiar category of modest sets, except that the partial equivalence relations which serve as objects are recursively enumerable. As usual, these constructions involve the splitting of symmetric idempotents.

Regarding effectivity of functions on the reals, there have been several proposed models of analog, continuous-time computation, as opposed to the digital, discrete nature of the type-2 computability. We study one of them, Moore's real (primitive) recursive functions, whose definition mimics the classical characterization of recursive functions on N by the closure properties. We show that the class of type-2 computable real functions falls between Moore's classes of primitive recursive and 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.

A theorem published by A. Grzegorczyk in 1955 states a certain kind of effective uniform continuity of computable functionals whose values are natural numbers and whose arguments range over the total functions in the set of the natural numbers and over the natural numbers. Namely, for any such functional a computable functional with one function-argument and the same number-arguments exists such that the values of the first of the functionals at functions dominated by a given one are completely determined by their restrictions to numbers not exceeding the corresponding values of the second functional at the given function. We prove versions of this theorem for the class of the primitive recursive functionals and for the class of the elementary recursive ones. Analogous results can be proved for many other subrecursive classes of functionals. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f ∈ [0,1] computes a non-computable subset of ℕ there is a non-total degree between Turing degrees a

In this paper we show that Shannon's general purpose analog computer (GPAC) is equivalent to a particular class of recursive functions over the reals with the flavour of Kleene's classical recursive function theory.We first consider the GPAC and several of its extensions to show that all these models have drawbacks and we introduce an alternative continuous-time model of computation that solves these problems. We also show that this new model preserves all the significant relations involving the previous models (namely, the equivalence with the differentially algebraic functions).We then continue with the topic of recursive functions over the reals, and we show full connections between functions generated by the model introduced so far and a particular class of recursive functions over the reals.

The theory of generalized functions is the foundation of the modern theory of partial differential equations (PDE). As computers are playing an ever-larger role in solving PDEs, it is important to know those operations involving generalized functions in analysis and PDE that can be computed on digital computers. In this article, we introduce natural concepts of computability on test functions and generalized functions, as well as computability on Schwartz test functions and tempered distributions. Type-2 Turing machines are used as the machine model [Weihrauch 2000]. It is shown here that differentiation and integration on distributions are computable operators, and various types of Fourier transforms and convolutions are also computable operators. As an application, it is shown that the solution operator of the distributional inhomogeneous three dimensional wave equation is computable.

We establish linear lower bounds for the complexity of non-trivial, primitive recursive algorithms from piecewise linear given functions. The main corollary is that logtime algorithms for the greatest common divisor from such givens (such as Stein’s) cannot be matched in efficiency by primitive recursive algorithms from the same given functions. The question is left open for the Euclidean algorithm, which assumes the remainder function.

The transition from studying calculus in schools to studying mathematical analysis at university is notoriously difficult. In this third edition of Numbers and Functions, Professor Burn invites the student reader to tackle each of the key concepts in turn, progressing from experience through a structured sequence of more than 800 problems to concepts, definitions and proofs of classical real analysis. The sequence of problems, of which most are supplied with brief answers, draws students into constructing definitions and theorems for themselves. This natural development is informed and complemented by historical insight. Carefully corrected and updated throughout, this new edition also includes extra questions on integration and an introduction to convergence. The novel approach to rigorous analysis offered here is designed to enable students to grow in confidence and skill and thus overcome the traditional difficulties.

We introduce the safe recursive set functions based on a Bellantoni–Cook style subclass of the primitive recursive set functions. We show that the functions computed by safe recursive set functions under a list encoding of finite strings by hereditarily finite sets are exactly the polynomial growth rate functions computed by alternating exponential time Turing machines with polynomially many alternations. We also show that the functions computed by safe recursive set functions under a more efficient binary tree encoding of finite strings by hereditarily finite sets are exactly the quasipolynomial growth rate functions computed by alternating quasipolynomial time Turing machines with polylogarithmic many alternations.We characterize the safe recursive set functions on arbitrary sets in definability-theoretic terms. In its strongest form, we show that a function on arbitrary sets is safe recursive if and only if it is uniformly definable in some polynomial level of a refinement of Jensen's J-hierarchy, relativized to the transitive closure of the function's arguments.We observe that safe recursive set functions on infinite binary strings are equivalent to functions computed by infinite-time Turing machines in time less than ωω. We also give a machine model for safe recursive set functions which is based on set-indexed parallel processors and the natural bound on running times.

Given a class ℱ oft otal functions in the set oft he natural numbers, one could study the real numbers that have arbitrarily close rational approximations explicitly expressible by means of functions from ℱ. We do this for classes ℱsatisfying certain closedness conditions. The conditions in question are satisfied for example by the class of all recursive functions, by the class of the primitive recursive ones, by any of the Grzegorczyk classes ℰnwith n ≥ 2, by the class of all functions recursive in a given function and by the class of the functions primitive recursive in it, as well as by the class of all total functions in the set of the natural numbers.

The free-spectrum and g-spectrum functions of a variety V are defined as fV(n) = “the size of the free algebra on n generators in V” and gV(n) = “the number of non-isomorphic algebras in V generated by n or fewer elements”, for any positive integer n. Thus V is locally finite iff for each positive integer n, fV(n) is a positive integer (and consequently gV(n) is a positive integer). If V is locally finite, then we have

Based on standard notions of classical recursion theory, a natural model of approximate computability for partial functions between effective metric spaces is presented. It generalizes the Ko–Friedman approach to computability of real functions by means of oracle Turing machines, follows the main ideas of Weihrauch's type 2 theory of effectivity, but it avoids the explicit use of representations. The topological arithmetical hierarchy is introduced and shown to be strict if the underlying space contains an effectively discrete sequence. The domains of computable functions are exactly the Π2-sets of this hierarchy if the space admits a finitary stratification. Finally, this framework is used to investigate and characterize the standard representations of the real numbers. They are just those functions from the name space onto the reals which have both computable extensions and inversions that are computable as relations.

The complexity of index sets of families of general recursive functions is evaluated in the Kleene–Mostowski arithmetic hierarchy.

International audience; We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of polytime sampleable distributions, a key concept in average-case complexity and cryptography.

In this paper we introduce the notion of relative computability for continuous real valued functions. It combines the notion of relative recursiveness for number theoretic functions with the theory of computability for continuous real valued functions. Most of the space is devoted to investigating the degrees of unsolvability of those mathematical operations which lead from the computable to the noncomputable. The paper concludes with Theorem 5, which asserts that the derivatives of computable C1 functions on compact intervals are at most semi-computable.

Infinite time Turing machines with only one tape are in many respects fully as powerful as their multi-tape cousins. In particular, the two models of machine give rise to the same class of decidable sets, the same degree structure and, at least for functions f:R-->N, the same class of computable functions. Nevertheless, there are infinite time computable functions f:R-->R that are not one-tape computable, and so the two models of supertask computation are not equivalent. Surprisingly, the class of one-tape computable functions is not closed under composition; but closing it under composition yields the full class of all infinite time computable functions. Finally, every ordinal which is clockable by an infinite time Turing machine is clockable by a one-tape machine, except certain isolated ordinals that end gaps in the clockable ordinals., 21 pages, 4 figures

This paper deals with the computability in analysis within the framework of Grzegorczyk's hierarchy, which is in the number 1 of addendum of open problems in Pour-El and Richards ([5], Computability in Analysis and Physics, Springer, Berlin, 1989). We combine two concepts, computability for sequences of real-valued functions and Grzegorczyk's hierarchy for recursive number theoretic functions, together and examine the computability in analysis restricted to primitive recursion and below. The notions of ( E r ) primitive computability structures on Banach space, in particular, for sequences of reals and real-valued functions are introduced; relations between ( E r ) primitive computability structures are proved; some basic properties are studied.

We consider the Ko–Friedman notion of (non-uniform) time complexity for real functions approximately computable in the generalized sense defined earlier. It turns out that, beside the Ko–Friedman theory, also the classical theory of time complexity for discrete functions over N is naturally embedded in our setting. The real functions computable with total recursive time bounds are characterized to be just those approximately computable functions which have recursively closed domains.

We observe that the computational inefficiency of branched recursive functions was not appropriately covered in almost all textbooks for computer science courses in the first three years of the curriculum. Fibonacci numbers and binomial coefficients were frequently used as examples of branched recursive functions. However, their exponential time complexity was rarely claimed and never completely proved in the textbooks. Alternative linear time iterative solutions were rarely mentioned. We give very simple proofs that these recursive functions have exponential time complexity. The proofs are appropriate for coverage in the first computer science course.

In this paper we continue our work of Kalantari and Welch (1998). There we introduced machinery to produce a point-free approach to points and functions on topological spaces and found conditions for both which lend themselves to effectivization. While we studied recursive points in that paper, here, we present two useful classes of recursive functions on topological spaces, apply them to the reals, and find precise accounting for the nature of the properties of some examples that exist in the literature. We end with a construction of a recursive function on a small subset of the unit interval which is strongly nonextendible.

Intuitively, a real number is recursive if we can get as accurate an approximation as we like, using a mechanical procedure such as a Turing machine. A real function is recursive if its value at a point x in its domain can be approximated effectively given an approximation to x . However, since there are only countably many Turing machines, there must be uncountably many non-recursive reals and functions. In this paper, we study some of these non-recursive reals and functions using a more recursion theoretic approach, via the degree of unsolvability. In particular, we are interested in reals and real functions that are relatively recursive in ∅′, where ∅′ is the jump of the recursive degree ∅′. Inspired by the Shoenfield Limit Lemma, we show that a real is ∅′-recursive if and only if it is the limit of a recursive sequence of rationals. We then give three characterizations of a ∅′-recursive function which are stated in terms of Turing machine, uniform convergence, and sequential computability with uniform continuity. A proof of their equivalence using a finite injury priority argument is given. With the new definitions, we can now give an upper bound to the difficulty of some uncomputable analysis operator such as differentiations and root findings.

Let K be a countable field. Then a weak presentation of K is an isomorphism of K onto a field whose elements are natural numbers, such that all the field operations are extendible to total recursive functions. Given a pair of two non-finitely generated countable fields contained in some overfield, we investigate under what circumstances the overfield has a weak presentation under which the given fields have images of arbitrary Turing degrees or, in other words, we investigate Turing separability of various pairs of non-finitely generated fields.

We describe a nonconstructive extension to primitive recursive arithmetic, both abstractly and as implemented on the Boyer-Moore prover. Abstractly, this extension is obtained by adding the unbounded µ operator applied to primitive recursive functions; doing so, one can define the Ackermann function and prove the consistency of primitive recursive arithmetic. The implementation does not mention the µ operator explicitly but has the strength to define the µ operator through the built-in functions EVALd and VC.