检索结果-内蒙古大学图书馆

An early history of recursive functions and computability from Godel to Turing

学校读者我要写书评

暂无评论

HISTORY AND PHILOSOPHY OF LOGIC 2012年第2期33卷 191-191页

作者： Grattan-Guinness, I. Middlesex Univ Sch Business London NW4 4BT England

Click to increase image sizeClick to decrease image size

关键词： recursive functions HISTORY NONFICTION 20TH century

Resilience Modeling by Means of a Set of recursive functions

学校读者我要写书评

暂无评论

Resilience Modeling by Means of a Set of Recursive Functions

Annual IEEE/IFIP International Conference on Dependable Systems and Networks Workshops

作者： Maria Teresa Signes Pont Juan Manuel Garcia Chamizo Higinio Mora Mora Jeronimo Mora Pascual Departamento de Tecnologia Informatica y Computation Universidad de Alicante

ISBN: (纸本)9781479901807

This paper presents a computational framework to approach the resilience properties of the systems in many different domains. The proposal models elementary behaviors of the systems by means of a set of recursive functions defined by a few parameters. The parameter values determine wide intervals that characterize the behavioral patterns. The proposal provides a theoretical model of resilience related to the capability of a system to maintain its own pattern by displaying only minor changes when the parameter values of the model vary inside the intervals. This model lays out two powerful design principles for resilience issues, which are the parameterized form of the function and its recursive calculation. The model has been successfully applied to the study of well known system archetypes.

关键词： recursive functions Behavioral modeling Resilience design principles Complex systems System archetypes recursive functions Complex systems Resilience behavioral models recursive Set (Psychology) Economic Resources system behavior design theory

VDM recursive functions in Isabelle/HOL

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Freitas, Leo Larsen, Peter Gorm School of Computing Newcastle University United Kingdom DIGIT Aarhus University Department of Engineering Denmark

For recursive functions general principles of induction needs to be applied. Instead of verifying them directly using the Vienna Development Method Specification Language (VDM-SL), we suggest a translation to Isabelle/HOL. In this paper, the challenges of such a translation for recursive functions are presented. This is an extension of an existing translation and a VDM mathematical toolbox in Isabelle/HOL enabling support for recursive functions. © 2023, CC BY-SA.

关键词： recursive functions

Regression verification of unbalanced recursive functions with multiple calls (long version)

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Sayedoff, Chaked R.J. Strichman, Ofer IE Technion Haifa Israel

Given two programs p1 and p2, typically two versions of the same program, the goal of regression verification is to mark pairs of functions from p1 and p2 that are equivalent, given a definition of equivalence. The most common definition is that of partial equivalence, namely that the two functions emit the same output if they are fed with the same input and they both terminate. The strategy used by the Regression Verification Tool (RVT) is to progress bottom up on the call graphs of P1, P2, abstract those functions that were already proven to be equivalent with uninterpreted functions, turn loops into recursion, and abstract the recursive calls also with uninterpreted functions. This enables it to create verification conditions in the form of small programs that are loop- and recursion-free. This method works well for recursive functions as long as they are in sync, and typically fails otherwise. In this work we study the problem of proving equivalence when the two recursive functions are not in sync. Effectively we extend previous work that studied this problem for functions with a single recursive call site, to the general case. We also introduce a method for detecting automatically the unrolling that is necessary for making two recursive functions synchronize, when possible. We show examples of pairs of functions with multiple recursive calls that can now be proven equivalent with our method, but cannot be proven equivalent with any other automated verification system. © 2022, CC0.

关键词： recursive functions

Farey recursive functions

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Chesebro, Eric Emlen, Cory Ke, Kenton Lafontaine, Denise McKinnie, Kelly Rigby, Catherine

Extensible recursive functions, Algebraically

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hubers, Alex Ingle, Apoorv Marmaduke, Andrew Morris, J. Garrett Department of Computer Science The University of Iowa 14 MacLean Hall Iowa CityIA United States

We explore recursive programming with extensible data types. Row types make the structure of data types first class, and can express a variety of type system features from subtyping to modular combination of case branches. Our goal is the modular combination of recursive types and of recursive functions over them. The most significant challenge is in recursive function calls, which may need to account for new cases in a combined type. We introduce bounded algebras, Mendler-style descriptions of recursive functions in which recursive calls can happen at larger types, and show that they provide expressive recursion over extensible data types. We formalize our approach in Rωμ, a small extension of an existing row type theory with support for recursive terms and types, and mechanize the metatheory of Rωμ via an embedding in Agda. © 2024, CC BY.

关键词： recursive functions

The Undecidability of Pattern Matching in Calculi where Primitive recursive functions are Representable

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Dowek, Gilles INRIA France B.P. 105 Le Chesnay78153 Cedex France

We prove that the pattern matching problem is undecidable in polymorphic λ-calculi (as Girard's system F [8] [9]) and calculi supporting inductive types (as Gödel's system T [10] [9]) by reducing Hilbert's tenth problem to it. More generally pattern matching is undecidable in all the calculi in which primitive recursive functions can be fairly represented in a precised sense. Copyright © 2023, The Authors. All rights reserved.

关键词： recursive functions

Approximate Degree Composition for recursive functions

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chakraborty, Sourav Kayal, Chandrima Mittal, Rajat Paraashar, Manaswi Saurabh, Nitin Indian Statistical Institute Kolkata India Indian Institute of Technology Kanpur India University of Copenhagen Denmark Indian Institute of Technology Hyderabad India

Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have concentrated on proving that approximate degree composes for special types of inner and outer functions. An important and extensively studied class of functions are the recursive functions, i.e. functions obtained by composing a base function with itself a number of times. The main result of this work is to show that the approximate degree composes if either of the following conditions holds: • The outer function f : {0, 1}n → {0, 1} is a recursive function of the form hd, with h being any base function and d = Ω(log log n). • The inner function is a recursive function of the form hd, with h being any constant arity base function (other than AND and OR) and d = Ω(log log n), where n is the arity of the outer function. In terms of proof techniques, we first observe that the lower bound for composition can be obtained by introducing majority in between the inner and the outer functions. We then show that majority can be efficiently eliminated if the inner or outer function is a recursive function. © 2024, CC BY.

关键词： recursive functions

Theory of recursive functions and effective computability /

学校读者我要写书评

暂无评论

Theory of recursive functions and effective computability /