The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhib...
详细信息
The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete iff both its topological structure is highly complex while its algorithmic structure is easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally". (C) 2003 Elsevier Science (USA). All rights reserved.
The generation of some classes of recursive functions by superpositions of simple arithmetic functions is discussed. A finite basis in the class FFOM under superposition is constructed. The constructions use simple ar...
详细信息
The generation of some classes of recursive functions by superpositions of simple arithmetic functions is discussed. A finite basis in the class FFOM under superposition is constructed. The constructions use simple arithmetic functions and function standard for the majority of programming languages. Finite bases can be constructed in the hierarchy classes under certain constraints on the superpositions. The class of functions elementary in the sense of Skolem is defined as the set of all functions obtained from the functions 0, x+1, and x-y by using the operations of superposition and restricted summation. The class FFOM is the set of all functions defined everywhere on the set bounded above by the functions.
Functional programming languages, since their early days, have been regarded as the holy grail of parallelism. And, in fact, the absence of race conditions, coupled with algorithmic skeletons such as map and reduce, h...
详细信息
Functional programming languages, since their early days, have been regarded as the holy grail of parallelism. And, in fact, the absence of race conditions, coupled with algorithmic skeletons such as map and reduce, have given developers the opportunity to write many different techniques aimed at the automatic parallelization of programs. However, there are many functional programs that are still difficult to parallelize. This difficulty stems from many factors, including the complex syntax of recursive functions. This paper provides new equipment to deal with this problem. Such instrument consists of an insight, plus a code transformation that is enabled by this insight Concerning the first contribution, we demonstrate that many recursive functions can be rewritten as a combination of associative operations. We group such functions into two categories, which involve monoid and semiring operations. Each of these categories admits a parallel implementation. To demonstrate the effectiveness of this idea, we have implemented an automatic code rewriting tool for Haskell, and have used it to convert six well-known recursive functions to algorithms that run in parallel. Our tool is totally automatic, and it is able to deliver non-trivial speedups upon the sequential version of the programs that it receives. In particular, the automatically generated parallel code delivers good scalability when varying the number of threads or the input size. (C) 2018 Elsevier B.V. All rights reserved.
Under consideration are the algebras of unary functions with supports in countable primitively recursively closed classes and composition operation. Each algebra of this type is proved to have continuum many maximal s...
详细信息
Abstract: The underlying question considered in this paper is whether or not the purposeful introduction of random elements, effectively governed by a probability distribution, into a calculation may lead to c...
详细信息
Abstract: The underlying question considered in this paper is whether or not the purposeful introduction of random elements, effectively governed by a probability distribution, into a calculation may lead to constructions of number-theoretic functions that are not available by deterministic means. A methodology for treating this question is developed, using an effective mapping of the space of infinite sequences over a finite alphabet into itself. The distribution characterizing the random elements, under the mapping, induces a new distribution. The property of a distribution being recursive is defined. The fundamental theorem states that recursive distributions induce only recursive distributions. A function calculated by any probabilistic means is called $\psi$-calculable. For a class of such calculations, these functions are recursive. Relative to Church’s thesis, this leads to an extension of that thesis: Every $\psi$-effectively calculable function is recursive. In further development, a partial order on distributions is defined through the concept of “inducing.” It is seen that a recursive atom-free distribution induces any recursive distribution. Also, there exist distributions that induce, but are not induced by, any recursive distribution. Some open questions are mentioned.
We prove that every sufficiently slow-growing diagonally non-recursive (DNR) function computes a real with effective Hausdorff dimension 1. We then show that, for any recursive unbounded and non-decreasing function j,...
详细信息
We prove that every sufficiently slow-growing diagonally non-recursive (DNR) function computes a real with effective Hausdorff dimension 1. We then show that, for any recursive unbounded and non-decreasing function j, there is a DNR function bounded by j that does not compute a Martin-Lof random real. Hence, there is a real of effective Hausdorff dimension 1 that does not compute a Martin- Lof random real. This answers a question of Reimann and Terwijn.
This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Ind...
详细信息
This work addresses the problem of verifying imperative programs that manipulate data structures, e.g., Rust programs. Data structures are usually modeled by Algebraic Data Types (ADTs) in verification conditions. Inductive invariants of such programs often require recursively defined functions (RDFs) to represent abstractions of data structures. From the logic perspective, this reduces to solving Constrained Horn Clauses (CHCs) modulo both ADT and RDF. The underlying logic with RDFs is undecidable. Thus, even verifying a candidate inductive invariant is undecidable. Similarly, IC3-based algorithms for solving CHCs lose their progress guarantee: they may not find counterexamples when the program is unsafe. We propose a novel IC3-inspired algorithm Racer for solving CHCs modulo ADT and RDF (i.e., automatically synthesizing inductive invariants, as opposed to only verifying them as is done in deductive verification). Racer ensures progress despite the undecidability of the underlying theory, and is guaranteed to terminate with a counterexample for unsafe programs. It works with a general class of RDFs over ADTs called catamorphisms. The key idea is to represent catamorphisms as both CHCs, via relationification, and RDFs, using novel abstractions. Encoding catamorphisms as CHCs allows learning inductive properties of catamorphisms, as well as preserving unsatisfiabilty of the original CHCs despite the use of RDF abstractions, whereas encoding catamorphisms as RDFs allows unfolding the recursive definition, and relying on it in solutions. Abstractions ensure that the underlying theory remains decidable. We implement our approach in Z3 and show that it works well in practice.
Raphael Robinson showed that all primitive recursive functions, depending on one argument, and only they could be obtained from two functions s(x) = x + 1 and q(x) = x divided by [root x](2) by using the operations of...
详细信息
Raphael Robinson showed that all primitive recursive functions, depending on one argument, and only they could be obtained from two functions s(x) = x + 1 and q(x) = x divided by [root x](2) by using the operations of addition+, superposition*, and iteration i. Julia Robinson proved that, starting from the same two functions and using the operations of addition+, superposition*, and the operation(-1) of function inversion, one could obtain all general recursive functions (under a certain condition on the inversion operation) and all partial recursive functions. On the basis of these results, A.I. Mal'tsev introduced into consideration Raphael Robinson algebra of all unary primitive recursive functions and two of Julia Robinson's algebras: namely, the partial algebra of all unary general recursive functions and the algebra of all unary partial recursive functions, and proposed to study the properties of these algebras, including the existence of finite bases of identities in these algebras. In this paper, we show that there is no finite basis of identities in any of the above algebras.
暂无评论